相关疑难解决方法(0)

我需要在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]快三倍.我相信这是因为:

1. insert()操作成本很高,因为Python列表不是链表.
2. sorted()是一个优化的c函数,我的是纯python.

有没有办法击败sorted()[:n]？我应该使用C扩展,Pyrex或Psyco或类似的东西吗？ …