heapq.nsmallest 如何工作

Question

我试图确定基于字典中最小的 k 个键获取 k （键，值）对的最快运行时间。即：对于

mynahs = {40:(1,3),5:(5,6),11:(9,2),2:(6,3),300:(4,4),15:(2,8)}

smallestK(mynahs,3)

会返回：

[(2,(6,3)),(5,(5,6)),(11,(9,2))]

我见过几种不同的方法来做到这一点：
1。

mylist = list(mynahs.keys())
mylist.sort
mylist = mylist[:k]
return [(k, mynahs[k]) for k in mylist]

但每个人似乎都认为 heapq 是最快的

cheap = heapq.nsmallest(3, mynahs)
return [(k, mynahs[k]) for k in cheap]

heapq.nsmallest 如何工作以及为什么它是最快的？我看过这个问题，但我 仍然不明白。heapq 是否使用 minheap 来获取 n 最小的值？这是如何运作的？我还听说过一种名为“快速选择”的算法，它就是使用的吗？

它的运行时间是多少？如果字典不断变化/更新，每次需要 nsmallest 时调用 heapq.nsmallest 是最快的方法吗？

Answer 1

heapq.py 的代码位于https://svn.python.org/projects/python/trunk/Lib/heapq.py

nsmallest使用两种算法之一。如果要返回的项目数超过堆中项目总数的 10%，则它会复制列表，对其进行排序，并返回前 k 个项目。

如果 k 小于 n/10，则使用堆选择算法：

Make a copy of the first k items, and sort it
for each remaining item in the original heap
    if the item is smaller than the largest item in the new list
        replace the largest item with the new item
        re-sort the new list

写这篇文章的人使用了如此低效的算法有点令人惊讶。至少从理论上来说，快速选择是一种 O(n) 算法，应该比排序更快，并且比选择 n/10 项的“优化”算法快得多。

我不是 Python 爱好者，所以我不能肯定地说，但我使用其他语言的经验表明，上述内容也适用于 Python。

更新

https://github.com/python/cpython/blob/master/Lib/heapq.py#L395的实现工作方式有些不同。

如果 k 大于或等于列表中的项目数，则返回包含所有元素的排序列表。否则，它使用标准堆选择算法：

create a max heap from the first k items
for each remaining item
    if the item is smaller than the largest item on the heap
        remove the largest item from the heap
        add the new item to the heap
sort the resulting heap and return

删除/添加合并到一个名为 heap_replace 的函数中。

如果键是 ，则有一个优化来使用标准比较器None，但它使用相同的基本堆选择算法。

这种实现比我描述的另一种实现要高效得多，尽管我预计它在一般情况下会比 Quickselect 慢。