[almost OT now ! Just talkin' and talkin' ...]
From: Jeff 'japhy' Pinyan <[EMAIL PROTECTED]>
> On Nov 8, shirley said:
>
> >Is it possible read in the data then extract the Max value and
> >Minimum value out of that data set using perl ?
>
> Sorting a list of numbers is NOT the best approach to take to find the
> max and min values. Why? Because sorting (even the sorting that Perl
> does internally) take order N * log[2] N time. What does that mean?
> Well if you're sorting 16 items, then you're doing 16 * log[2] 16 = 16
> * 4 = 64 "operations". Some bad sorting routines take N**2 time, so
> sorting 16 items requires 256 "operations".
It should be pointed out though that each of the algorithms has
three possibly different complexities (sorry if using bad terms, I've
been taught these things in Czech and are lazy to look up the right
English terms).
Minimum, average and maximum. Plus they tend to behave very
differently on almost sorted, reversed lists etc.
quicksort (that's used by Perl) has all those N*log[2]N.
boublesort has the maximum N^2, but (I believe) average is
N*log[2]N as well and if the list is sorted already it only takes N.
Plus for almost sorted lists its at worst X*N (X being the number of
incorrectly inserted items). So sometimes the bad algorithm may
actually be better! (Don't come to me with benchmarks comparing
builtin sort and a boublesort implemented in Perl, keep in mind that
the builtin is heavily optimised!)
Not that it matters here of course.
> Finding the max and min of a list can be done in order N time -- that
> means that if we want to find the max and min, we can just go through
> the list ONCE. We'll end up actually doing 2*N operations, but this
> is still a much faster time than you'd get from sorting. It's also
> helpful to know different algorithms (especially efficient ones).
>
> Here's the algorithm in pseudo-code:
>
> min = max = list[0]; # default value, first element of the list
> for x in list {
> if (x < min) { min = x } # the new min value
> if (x > max) { max = x } # the new max value
> }
If you change it like this
for x in list {
if (x < min) { min = x } # the new min value
else if (x > max) { max = x } # the new max value
}
you'll only use 1.5*N on average. Plus if the list is almost sorted
(ascending) and you reverse the order of tests then you are only
going to make N+X tests. :-)
Jenda
=========== [EMAIL PROTECTED] == http://Jenda.Krynicky.cz ==========
There is a reason for living. There must be. I've seen it somewhere.
It's just that in the mess on my table ... and in my brain.
I can't find it.
--- me
--
To unsubscribe, e-mail: [EMAIL PROTECTED]
For additional commands, e-mail: [EMAIL PROTECTED]
