我需要在Python中获得较少的n个列表.我需要这个非常快,因为它是性能的关键部分,需要重复很多次.
n通常不大于10,列表通常有大约20000个元素.每次调用该函数时,列表总是不同的.无法进行排序.
最初,我写了这个函数:
def mins(items, n):
mins = [float('inf')]*n
for item in items:
for i, min in enumerate(mins):
if item < min:
mins.insert(i, item)
mins.pop()
break
return mins
但是这个函数无法击败对整个列表进行排序的简单排序(项目)[:n].这是我的测试:
from random import randint, random
import time
test_data = [randint(10, 50) + random() for i in range(20000)]
init = time.time()
mins = mins(test_data, 8)
print 'mins(items, n):', time.time() - init
init = time.time()
mins = sorted(test_data)[:8]
print 'sorted(items)[:n]:', time.time() - init
结果:
mins(items, n): 0.0632939338684
sorted(items)[:n]: 0.0231449604034
sorted()[:n]快三倍.我相信这是因为:
有没有办法击败sorted()[:n]？我应该使用C扩展,Pyrex或Psyco或类似的东西吗？ …
我有一个浮点值数组,想要值,更重要的是想要最多四个值的位置.
我最初构建系统是为了遍历数组并通过将当前位置的值与记录的最大值进行比较来找到最常用的方法,并在最大远程变化时更新位置变量.这很好用,一个非常简单的O(n)算法.我后来才知道,我不仅需要保持最高价值,还要保持前三或者前四名.我扩展了相同的程序并将最大程度的复杂化为四个最大化的数组,现在代码很难看.
它仍然有效并且仍然足够快,因为只有少量的计算被添加到过程中.它仍然有效地遍历数组并检查每个值一次.
我在MATLAB中使用sort函数执行此操作,该函数返回两个数组,排序列表和随附的原始位置列表.通过查看前几个值,我确切地知道我需要什么.我正在将此功能复制到C#.NET 2.0程序中.
我知道我可以用List对象做类似的事情,并且List对象有一个内置的排序例程,但我不相信它能告诉我原来的位置,而那些真的是我追求的.
它一直运作良好,但现在我发现自己想要第五个最大值并且看到重写最大的远程检查器,这是目前丑陋的if语句只会使丑陋复杂化.它会工作得很好并且添加第五级也不会慢,但我想询问SO社区是否有更好的方法.
对整个列表进行排序需要比我当前的方法多得多的计算,但我不认为这会是一个问题,因为列表"只有"一两千个浮点数; 因此,如果存在可以回馈原始位置的排序例程,那将是理想的.
作为背景,此数组是对千字节波形文件进行傅里叶变换的结果,因此最大值的位置对应于样本数据的峰值频率.我一直对前四名感到满意,但看到需要真正收集前五或者六,以便更准确地进行样本分类.