python - 您如何迭代并保持前 10 名的最大值？Python

Question

我有一个需要从函数计算的数字列表。我需要计算 200 万次。我本可以这样做，但有没有更简单的方法：

def funcx(): 
  return random.random() # for simplicity we use random

top10 = [] # max len = 10
for i in range(2000000):
  j = funcx()
  top10.append(j)
  top10 = sorted(top10, reverse=True)[:10]

Answer 1

更新：2013-me 充其量是困惑的，这是不正确的。请参阅https://stackoverflow.com/a/68587827/1126841。

---

使用固定大小的堆而不是每次都对列表​​进行排序：

import heapq
top10=[]
for i in range(2000000):
    heapq.heappush(top10, funcx())
    top10 = top10[:10]

渐近地，运行时间是相同的，但应该有更少的开销。

另一种选择是使用以下nsmallest功能：

heapq.nsmallest(10, (funcx() for i in range(2000000)) )

这比简单地对列表进行排序并返回前 10 个项目效率低，但它应该（即，我没有检查）使用更少的内存。

Answer 2

我想使用固定大小的堆显示正确的解决方案（接受的答案不正确）。假设您想要 10 个最小的元素。然后您可以使用最大堆并在每次推送后执行弹出。pop 将删除最大的元素，留下 10 个最小元素的数组。运行平稳高效heapq.heappushpop。10 个最小元素的代码如下所示：

import heapq
top10 = []
for i in range(2000000):
    # Heapq implements min heap, so we need to negate the numbers
    heapq.heappushpop(top10, -funcx())
print(top10)

无论如何，这段代码与实现基本相同heapq.nsmallest（它处理一些额外的极端情况，例如n == 1），所以你最好使用它：

heapq.nsmallest(10, (funcx() for i in range(2000000)))

或heap.nlargestn 个最大元素。

Answer 3

正如另一位用户指出的那样，我还建议实施插入排序。但是，正如您目前拥有的那样。您可以简单地查找最大值并将其从列表中删除，然后重复 10 次。

>>> x = [1,2,3,4,5]
>>> max(x)
5
>>> x.remove(5)
>>> max(x)
4