为什么这些算法的执行时间不同？

Question

关于leetcode'Top K frequency Elements'https://leetcode.com/problems/top-k-frequent-elements/submissions/的问题

有一个解决方案可以在88毫秒内完成任务，我的解决方案可以在124毫秒内完成任务，我认为这是一个很大的区别

我试图理解为什么buy docs不提供我所使用的函数的实现方式，这是最常见的（），如果我想深入了解这样的细节，这样我就可以编写在将来运行得如此之快的算法，我应该读什么（具体的书？或任何其他资源？）

我的代码（124毫秒）

def topKFrequent(self, nums, k):
        if k ==len(nums):
            return nums
        c=Counter(nums)
        return [ t[0] for t in c.most_common(k) ]

其他（88毫秒）（更及时）

def topKFrequent(self, nums, k):
        if k == len(nums):
            return nums
        count = Counter(nums)   
        return heapq.nlargest(k, count.keys(), key=count.get) 

两者占用的内存量几乎相同，所以这里没有区别

Answer 1

@trincot似乎已经回答了这个问题，但如果有人正在寻找一种更快的方法，那么就使用Numpy，前提是nums可以存储为np.array：

def topKFrequent_numpy(nums, k):
    unique, counts = np.unique(nums, return_counts=True)
    return unique[np.argsort(-counts)[:k]]

单速试验

nums_array = np.random.randint(1000, size=1000000)
nums_list = list(nums_array)

%timeit topKFrequent_Counter(nums_list, 500)
# 116 ms ± 4.18 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)
%timeit topKFrequent_heapq(nums_list, 500)
# 117 ms ± 3.35 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)
%timeit topKFrequent_numpy(nums_array, 500)
# 39.2 ms ± 185 µs per loop (mean ± std. dev. of 7 runs, 10 loops each)

（对于其他输入值，速度可能会显著不同）

Answer 2

{}的{a1} 也使用heapq.nlargest，但它使用count.items()而不是count.keys()调用它。这将使它稍微慢一点，并且还需要创建新列表的开销，以便从most_common()返回的列表中的每个元素中提取[0]值

heapq.nlargest版本只是避免了这种额外的开销，并将count.keys()作为第二个参数传递，因此它不需要再次迭代该结果以将片段提取到新列表中