Front page | perl.beginners | Postings from February 2002

## Re: finding max value

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.

```