从Python列表中获取N Min或Max元素的快速方法 [英] Fast way to get N Min or Max elements from a list in Python

问题描述

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

I currently have a long list which is being sorted using a lambda function f. I then choose a random element from the first five elements. Something like:

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

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

This is a bottleneck in my program, according to the profiler. How can I speed things up? Is there a fast, inbuilt way to retrieve the elements I want (in theory shouldn't need to sort the whole list). Thanks.

推荐答案

使用 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)更快.

This will take O(N+KlogN) time (where K is the number of elements returned, and N is the list size), which is faster than O(NlogN) for normal sort when K is small relative to N.

这篇关于从Python列表中获取N Min或Max元素的快速方法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！