jeudi 27 mai 2010

Extract the N largest floating point numbers from a large file of floating point numbers

General idea; We use a sorted list to store the N largest numbers and we insert new items as we go. If we need to insert and the list size has reached N, we also delete the lowest value


Lsize=0
while f in stream:
if L = None
L = new List
L.val = f
L.next = NULL
Lsize++
elsif L.val >= f
continue
else // L.val < f
current = L
while current
if current.val > f:
next = current.val.next
current.next = new List
current.next.next = next
current.next.val = f
if Lsize = N
L = L.next
current = current.next

Aucun commentaire:

Enregistrer un commentaire