Front page | perl.beginners |
Postings from February 2002
Re: finding max value
Thread Previous
|
Thread Next
From:
Tagore Smith
Date:
February 13, 2002 11:51
Subject:
Re: finding max value
Message ID:
019501c1b4c1$ce3a4e60$0300a8c0@optonline.net
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.
Thread Previous
|
Thread Next