On Fri, 2006-31-03 at 17:15 -0700, Wiggins d'Anconia wrote: > 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....
Benchmarking, ah, yes. Been here, got the tee-shirt. Given an input of order n: sort takes O( n * log2( n )) This would be this time taken by your suggestion. Comparing each as it came in: O(n) That would be faster. I said the algorithm would fail early, so this is a good estimate. In other words, pre-sorting your input is a bad idea. Yes, my algorithm is maintaining a sorted list. But the list length is shorter than the demand for output, which comes at the end. My algorithm is optimized to fail early if it's going to fail; but if it's going to succeed, it's going to succeed early. The best of both worlds. -- __END__ Just my 0.00000002 million dollars worth, --- Shawn "For the things we have to learn before we can do them, we learn by doing them." Aristotle * Perl tutorials at http://perlmonks.org/?node=Tutorials * A searchable perldoc is at http://perldoc.perl.org/ -- To unsubscribe, e-mail: [EMAIL PROTECTED] For additional commands, e-mail: [EMAIL PROTECTED] <http://learn.perl.org/> <http://learn.perl.org/first-response>
