> > > IMHO sorting a list to find the max and min
> > > element is not a good idea. The sort is of
^^^^^^^^^^^^^^^
> > > O(nlgn) and the usual run through the list
> > > to find the max element is O(n).
> >
> > In general, it's not.
>
> I am not sure what you mean by this, sorting
> is still O(nlgn) even if it is implemented in
> machine code.
>
The underlined bit was the bit I was referring to.
Big Oh tells you the behaviour as the input dataset
increases in size, but tells you little about the
runtime. To find runtime, you need to figure out
what the constants are.
E.g.
Standard = 100N
Sort = 10N Log 20N
then for a value of N=20:
Standard = 2000 units
Sort = 200 * Log_2(400) = ~520 units
(letting Log_10 = Log_2 cause I'm lazy)
So, if this was representative of the actual
constants, then a sort is faster. AFAIK it is
representative of Perl's behaviour when comparing
my/your algorithm against a sort.
For maximum speed, you'd look at the number of
elements and then choose which algorithm is
faster. Sort for small datasets, standard for
large datasets.
> The point I was trying to make is, it is not
> intuitive to sort a list to find the max and
> min element.
Hey, it is intuitive if you are programming it...
I've come up with this solution myself for top 5
numbers etc.
> I remember it being mentioned in this list that
> perl's sort implementation is a mixture of
> merge and quick sort (I apologize if this is not
> true). Can you point me to the file in which sort
> has been implemented.
AFAIK it's a Mergesort, I have no idea where you'd
find that in the source.
> > However, you if you cared for speed you'd use the
> > Math modules on CPAN for this... or Perl Data
> > Language (PDL).
>
> I guess the module you are mentioning here is
> List::Util. It also uses a method similar to
> what you have mentioned below.
That'd be the one ;-)
Speed matters? PDL = VERY FAST (written in C or
ASM, probably the former).
Jonathan Paton
__________________________________________________
Do You Yahoo!?
Everything you'll ever need on one web page
from News and Sport to Email and Music Charts
http://uk.my.yahoo.com
--
To unsubscribe, e-mail: [EMAIL PROTECTED]
For additional commands, e-mail: [EMAIL PROTECTED]
