title: Single pass algorithm for finding the topX percent of items
body: <p>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.</p>
  
  <p>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 <code>bisect_left</code> to find the insertion point if needed.</p>
  
  <p>Below is the algorithm I have so far:</p>
  
  <pre><code>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) &gt; len(top_nums):
              top_nums.insert(0,None)
          newind = bisect_left(top_nums, val)
          if newind &gt; 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]
  </code></pre>
  
  <p>In the real case the data does not come from any standard distribution (otherwise I could use some statistics knowledge).</p>
  
  <p>Any suggestions would be appreciated.</p>