从非常大的未排序列表中获取最大X数字的最快方法？

Question

我试图从我的程序生成的分数列表中获得最高分100分.不幸的是,这个列表非常庞大(大约数百万到数十亿),因此排序是该计划的一个时间密集型部分.

什么是进行排序以获得前100名得分的最佳方式？

到目前为止,我能想到的唯一两种方法是首先将所有分数生成一个大型数组,然后对其进行排序并取得前100名.或者第二,生成X个分数,对其进行排序并截断前100个分数然后继续生成更多分数,将它们添加到截断列表中,然后再次对其进行排序.

无论哪种方式我都这样做,它仍然需要比我想要更多的时间,任何关于如何以更有效的方式做到这一点的想法？(我以前从未参加过编程课程,也许那些有comp sci学位的人都知道有效的算法来做到这一点,至少那是我所希望的).

最后,c ++中标准sort()函数使用的排序算法是什么？

谢谢,

-Faken

编辑:只为好奇的人...

我在之前和之后进行了几次试验,结果如下:

旧程序(每次外循环迭代后的预先排序):

top 100 scores: 147 seconds
top  10 scores: 147 seconds
top   1 scores: 146 seconds
Sorting disabled: 55 seconds

新程序(仅实现对最高分的跟踪并使用默认排序功能):

top 100 scores: 350 seconds <-- hmm...worse than before
top  10 scores: 103 seconds 
top   1 scores:  69 seconds 
Sorting disabled: 51 seconds

新的重写(存储数据的优化,手写排序算法):

top 100 scores: 71 seconds <-- Very nice!
top  10 scores: 52 seconds
top   1 scores: 51 seconds
Sorting disabled: 50 seconds

完成核心2,1.6 GHz ...我不能等到我的核心i7 860到来......

还有很多其他更积极的优化让我能够解决(主要是在减少我运行的迭代次数的领域),但是就目前而言,速度已经足够好了,我甚至可能都懒得去算出那些算法优化.

感谢eveyrone的投入!

Answer 1

1. 取前100个分数,并在数组中对它们进行排序.
2. 获取下一个分数,并将其插入到数组中(从"小"端开始)
3. 降低第101个值
4. 继续下一个值,为2,直到完成

随着时间的推移,列表将越来越类似于100个最大值,因此更常见的是,您发现插入排序会立即中止,发现新值小于前100个候选项的最小值.

Answer 2

您可以在O(n)时间内执行此操作,无需使用堆进行任何排序:

#!/usr/bin/python

import heapq

def top_n(l, n):
    top_n = []

    smallest = None

    for elem in l:
        if len(top_n) < n:
            top_n.append(elem)
            if len(top_n) == n:
                heapq.heapify(top_n)
                smallest = heapq.nsmallest(1, top_n)[0]
        else:
            if elem > smallest:
                heapq.heapreplace(top_n, elem)
                smallest = heapq.nsmallest(1, top_n)[0]

    return sorted(top_n)


def random_ints(n):
    import random
    for i in range(0, n):
        yield random.randint(0, 10000)

print top_n(random_ints(1000000), 100)

在我的机器上的时间(Core2 Q6600,Linux,Python 2.6,用bash time内置测量):

• 100000个元素:.29秒
• 1000000元素:2.8秒
• 10000000元素:25.2秒

编辑/添加:在C++中,您可以使用std::priority_queue与heapq此处使用Python 模块的方式非常相似的方式.您将要使用std::greater排序而不是默认排序std::less,以便top()成员函数返回最小元素而不是最大元素.C++的优先级队列没有等效的heapreplace,用新的替换顶部元素,所以你需要pop顶部(最小)元素,然后push是新看到的值.除此之外,算法从Python到C++的转换非常干净.

Answer 3

这是执行此操作的'自然'C++方法:

std::vector<Score> v;
// fill in v
std::partial_sort(v.begin(), v.begin() + 100, v.end(), std::greater<Score>());
std::sort(v.begin(), v.begin() + 100);

这是分数的线性.

std :: sort使用的算法不是由标准规定的,但是libstdc ++(由g ++使用)使用"自适应内向",这实际上是一个3中间快速入口到一定水平,然后插入分类.