Keeping track of the N largest values

[Duncan Booth]

Roy Smith <roy at panix.com> wrote:

> 
> I'm processing a stream of N numbers and want to keep track of the K 
> largest.  There's too many numbers in the stream (i.e. N is too large)
> to keep in memory at once.  K is small (100 would be typical).
> ... 
> Is there a better way to do this, either from a theoretical running
> time point of view, or just a nicer way to code this in Python?

How about:

  from heapq import nlargest
  top = nlargest(K, input())

It uses a heap so avoids completely resorting each time.

-- 
Duncan Booth http://kupuguy.blogspot.com