Single pass algorithm for finding the topX percent of items

Question

I'm looking for a single-pass algorithm for finding the topX percent of floats in a stream where I do not know the total number ahead of time ... but its on the order of 5-30 million floats. It needs to be single-pass since the data is generated on the fly and recreate the exact stream a second time.

The algorithm I have so far is to keep a sorted list of the topX items that I've seen so far. As the stream continues I enlarge the list as needed. Then I use bisect_left to find the insertion point if needed.

Below is the algorithm I have so far:

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]

In the real case the data does not come from any standard distribution (otherwise I could use some statistics knowledge).

Any suggestions would be appreciated.

Answer 1

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

There is no reason to make a list out of it before you sort it.

for ind, val in enumerate(iterable, len(top_nums))

I dislike abbreviations. I think it makes it harder to figure out what ind and val are doing.

   all_data = sorted(data_gen(num))

Why are you sorting your test data?

As I understand your problem, your code is wrong. It only works in your test case because you sort the incoming data.

Your algorithm regularly increases the size of the list of values. But when it does so, there have been previous numbers which have been thrown away which may greater then the value you insert at that point. As a result, you cannot be sure you've actually ended up with with the top 1%.

How should you fix it? If you can upper bound the size of your input, then you can start with a list of sufficient size and then scale back at the end. Otherwise I don't think you can do it. The problem being that you cannot throw away any values because there is no way to be sure you won't need them later.

You might consider using a heap. Python has a heapq module including a function heapq.nlargest which does pretty much what you are doing, (but uses a count rather then a percentage) A heap is pretty much a semi-sorted list and lets you do things like find/remove/replace the lowest value without the overhead of actually sorting.

Answer 2

This can't work unless you stipulate a specific size for the partition and do not grow it.

You can't discard any value from the input sequence or you won't get the actual maximum. The fact that you're popping a value means that you may be discarding a proper part of the solution subset.

Consider a slightly contrived example where X = 0.25. The initial state is to process 1/X items (4 in this case) of which 1 is maximum and 3 are discarded. The values were 100, 99, 98 and 97. You keep 100 as the 25% maximum and discard 99, 98, 97.

(You could try to keep all 4 or even the first 25 values. It doesn't matter how many you keep initially, the logic problem will still arise as soon as you pop a value. I think the contrived example makes the logic flaw easier to see.)

At some point, you've seen 7 values. The maxima subset has 1 value (100); the remaining values (99, 98, 96, 95, 94 and 93) have been discarded as not part of the maxima set.

You get value 8, it's 92. You need to append this to the top set. Yet, sadly, you discarded a value larger than this.

When you get to value 12, you again need to expand the maxima subset. However, you will have discarded values that may be larger than the 12th value in the sequence.

You cannot do a pop() from the maxima subset unless you can prove the value being popped must be less than all future values which may arrive.