Jeremy Vinding wrote: > duh... thx > of course, the results still favor sort: > > Benchmark: timing 1000000 iterations of for 10_000 elems, for 20 elems, sort > 10_000 elems, sort 20 elems... > for 10_000 elems: 7 wallclock secs ( 5.11 usr + 0.02 sys = 5.13 CPU) @ > 194931.77/s (n=1000000) > for 20 elems: 8 wallclock secs ( 5.44 usr + 0.01 sys = 5.45 CPU) @ > 183486.24/s (n=1000000) > sort 10_000 elems: 4 wallclock secs ( 2.99 usr + -0.02 sys = 2.97 CPU) @ > 336700.34/s (n=1000000) > sort 20 elems: 3 wallclock secs ( 3.22 usr + -0.04 sys = 3.18 CPU) @ > 314465.41/s (n=1000000)
An O(n log n) algorithm doesn't grow _that_ much faster than one that's O(n) (log n grows much less quickly than n). I'm not that experienced with Perl, but I assume that the sort built-in is a fast n log n routine written in C (quicksort?). The C implementation may be enough faster that it overwhelms the difference in complexity for n < some large number (or there may still be something weird with your benchmark). Of course an O(n) algorithm will always beat an O(n log n) algorithm if you pick n large enough. My experience programming in another interpreted language similar to Perl (in architecture) has shown me that using built-ins can be dramatically faster than crunching stuff yourself. -- To unsubscribe, e-mail: [EMAIL PROTECTED] For additional commands, e-mail: [EMAIL PROTECTED]
