python - Python 中的惰性排序

Question

我有一个巨大的列表，想要获取前 n 个元素。快。

在其他语言中，我们可以使用带有 take 的惰性求值和插入排序或类似的方法在线性时间内检索这些元素。然而，Python 的 sort 和 sorted 函数总是对整个列表进行排序，这将花费很长时间。

是否有使用内置函数的快速解决方案，或者我真的必须为此任务编写自己的生成器吗？

Answer 1

是的，您可以使用 heapq 包对列表进行堆化。这发生在线性时间内。然后您可以在对数时间内从该堆中提取元素。如果需要拉取的数量不多，会比先对整个列表进行排序效率更高。

这是一个简短的说明:

import heapq

lst = [5,2,6,8,3,4,9,2,1,0,11,0,7]

heapq.heapify(lst)  # O(n)

while lst:
    print(heapq.heappop(lst))  # O(logn)

如果您预先知道需要多少个值，那么您可以在一次调用中获取它们，而无需显式调用 heapify。假设您需要 4:

import heapq

lst = [5,2,6,8,3,4,9,2,1,0,11,0,7]
print(*heapq.nsmallest(4, lst))

请注意，这不会改变 lst。