python - 从 Python 列表中获取 N Min 或 Max 元素的快速方法

Question

我目前有一个长列表，正在使用 lambda 函数 f 进行排序。然后我从前五个元素中选择一个随机元素。像这样的东西:

f = lambda x: some_function_of(x, local_variable)
my_list.sort(key=f)
foo = choice(my_list[:4])

根据分析器，这是我程序中的瓶颈。我怎样才能加快速度？是否有一种快速的内置方法来检索我想要的元素(理论上不需要对整个列表进行排序)。谢谢。

Answer 1

使用heapq.nlargest或 heapq.nsmallest .

例如:

import heapq

elements = heapq.nsmallest(4, my_list, key=f)
foo = choice(elements)

这将花费 O(N+KlogN) 时间(其中 K 是返回元素的数量，N 是列表大小)，当 K 相对于 N 较小时，这比普通排序的 O(NlogN) 更快。