3
\$\begingroup\$

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.

\$\endgroup\$
4
\$\begingroup\$
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.

\$\endgroup\$
  • 2
    \$\begingroup\$ Actually. Only a heap can possibly work. Consider the case where all the incoming data is in strictly descending order. No value can be discarded because the top X percent is always the first arrived items in descending order. Until the entire stream has been seen, no value can be discarded as the number of slots comprising X percent grows. \$\endgroup\$ – S.Lott Jul 18 '11 at 23:05
  • \$\begingroup\$ @S. Lott, I'm not seeing the connection between "only a heap can possibly work" and the rest of your comment. At the very least, I'd think a sorted list can do the same things a heap can, (with more computational cost) \$\endgroup\$ – Winston Ewert Jul 19 '11 at 6:59
  • \$\begingroup\$ True. A sorted list and lots of other expensive and bad ideas for keeping the data will "work". Since they'll be more costly, they aren't very good ideas are they? The heap, however, is a very good idea. I think it belongs up higher in your answer, because it's a very good ideas. The theoretical possibility of other less good ideas didn't seem very relevant. \$\endgroup\$ – S.Lott Jul 19 '11 at 9:47
  • \$\begingroup\$ @S.Lott, you said that only a heap could possibly work. If we are considering what could possibly work the efficiency doesn't matter. A heap is better, although I'm not sure how much. If I recall correctly, I have O(log n) insertion for both a sorted list and a heap. The heap is at the end because I thought it more important to point out that the code doesn't work then how to optimize it. \$\endgroup\$ – Winston Ewert Jul 19 '11 at 13:03
  • \$\begingroup\$ Your distinction between bad algorithms which may work eventually and a good algorithm is getting too subtle for me. I'm sure it's an important hair, but I can't understand splitting it. The algorithm as presented is fundamentally flawed -- as you noted. Further, the whole thing can be simplified to just a heap and nothing more. There's little more to say than you pointed out both flaws. Feel, free, however, to continue to split whatever hair you need to in your already complete answer. \$\endgroup\$ – S.Lott Jul 19 '11 at 13:10
1
\$\begingroup\$

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.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.