单通道算法,用于查找topX百分比的项目

Question

我正在寻找一种单程算法,用于在流中查找浮点数的topX百分比,其中我不知道提前的总数...但它大约有5到3千万个浮点数.它需要单次传递,因为数据是在运行中生成的,并且第二次重新创建精确的流.

到目前为止,我所拥有的算法是保存到目前为止我见过的topX项目的排序列表.随着流的继续,我根据需要扩大列表.然后我用它bisect_left来找到插入点,如果需要的话.

以下是我到目前为止的算法:

from bisect import bisect_left
from random import uniform
from itertools import islice


def data_gen(num):
    for _ in xrange(num):
        yield uniform(0,1)

def get_top_X_percent(iterable, percent = 0.01, min_guess = 1000):

    top_nums = sorted(list(islice(iterable, int(percent*min_guess)))) #get an initial guess

    for ind, val in enumerate(iterable, len(top_nums)):
        if int(percent*ind) > len(top_nums):
            top_nums.insert(0,None)
        newind = bisect_left(top_nums, val)
        if newind > 0:
            top_nums.insert(newind, val)
            top_nums.pop(0)

    return top_nums

if __name__ == '__main__':

    num = 1000000
    all_data = sorted(data_gen(num))
    result = get_top_X_percent(all_data)
    assert result[0] == all_data[-int(num*0.01)], 'Too far off, lowest num:%f' % result[0] 
    print result[0]

在实际情况下,数据不是来自任何标准分布(否则我可以使用一些统计知识).

任何建议,将不胜感激.

Answer 1

我不确定有没有办法真正可靠地做到这一点,因为当你看到更多元素时,"顶部X%"所表示的范围会不可预测地增长.考虑以下输入:

 101 102 103 104 105 106 107 108 109 110 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0...

如果你想要前25%的元素,你最终会从前十个元素中选择101和102,但是在那之后看到足够的零后你最终必须选择所有前10个元素.同样的模式可以扩展到任何足够大的流 - 它总是可能最终被外观误导,并丢弃你实际应该保留的元素.因此,除非您提前知道流的确切长度,否则我认为这是不可能的(在您到达流的末尾之前,不要将每个元素保留在内存中).