Mr. Shawn H. Corey wrote: > On Fri, 2006-31-03 at 15:45 -0800, Tom Phoenix wrote: > >>You should loop over the input, pushing each item on to an array. If >>at any time you have 2000 items in the array, sort them and discard >>any you don't want to keep. >> >> $#data = 999 if $#data > 999; # OBperl: one way to discard elements >> >>When you finish looping, sort-and-discard again. You'll never need >>more than 2N items in memory at any given time. Does that algorithm >>work for your needs? > > > Sorting is not necessary. If he keeps an array of the best, that means > lowest, records then all he has to do is compare every new entry with > the highest. This is called "fail early." This means, if it's going to > fail, it should at the earliest opportunity. If it succeeds then it > searches down thru the list, to find its place. This is called "succeed > early." Given that the procedure can flip between these two methods, it > is faster than any sort. > >
Unless the sort optimizes out the need to loop through so many elements, and/or is written at a lower level. If each new item that is entered goes in the last place then you have to loop over every element of the list every time. But a sort might be optimized not to have to do that. Your algorithm is essentially maintaining a sorted list, but doesn't really have an optimization applied to determine the new place. Only real way to tell would be benchmarking, but either should be a very good step in the right direction.... http://danconia.org -- To unsubscribe, e-mail: [EMAIL PROTECTED] For additional commands, e-mail: [EMAIL PROTECTED] <http://learn.perl.org/> <http://learn.perl.org/first-response>
