mbond has asked for the wisdom of the Perl Monks concerning the following question:
MY task is to recursivly find the min and max of an array.
I am using hte following program, but it isn't nearly working
properly. the size of the array could be anysize, but for
testing i am using a size of 10.
it should print out the values 1 and 65 .. but it prints 12 and 65.
Any Ideas would as to whats wrong would be great.
#!/usr/bin/perl
sub Partition {
($A, $lower, $upper, $min, $max) = @_;
if ($upper <= "1") {
return ($min, $max);
}
$mid = int(($upper - $lower) / 2);
if ($$A$mid < "$min") {
$min = $$A$mid;
}
elsif ($$A$mid > "$max") {
$max = $$A$mid;
}
&Partition($A,$l,$mid,$min,$max);
&Partition($A,$mid + 1,$upper,$min,$max);
}
@A = (53, 30, 12, 34, 65, 23, 21, 1, 23, 19);
$mid = int(10/2);
$min = $A$mid;
$max = $A$mid;
($min, $max) = Partition(\@A,1,$mid,$min,$max);
($min, $max) = Partition(\@A,$mid + 1,10,$min,$max);
print "$min, $max \n\n";
--
Michael Bond
mbond@eudoramail.com
Re: finding min and max of array recursivly
by t0mas (Priest) on Sep 28, 2000 at 17:07 UTC
|
use List::Util qw(min max);
@A = (53, 30, 12, 34, 65, 23, 21, 1, 23, 19);
$min=&min(@A);
$max=&max(@A);
print "$min, $max \n\n";
/brother t0mas
| [reply] [d/l] |
Re: finding min and max of array recursivly
by ChOas (Curate) on Sep 28, 2000 at 18:21 UTC
|
I'm sorry, I couldn't let this one go:
my ($Min,$Max)=(sort @A)[0,-1];
Would this be slow ?
*voice in my head* Very slow!, now go away...
| [reply] [d/l] |
|
Yes, for larger datasets.
My first gut-level feel for "speed of algorithms" comes from my "how much
entropy did you undo with that calculation?". In this case, besides knowing
the minimum and maximum, you also knew (at one point, before you threw
it away) the second-smallest, third-smallest, on up to the second-largest.
It must have taken time to calculate those, so you've wasted time to calculate
things that don't affect the outcome.
Note that this is just for "back of the thumbnail" calculations. I've been wrong
using this method, but I'm not a theoretical mathematician... I'm a hacker. {grin}
-- Randal L. Schwartz, Perl hacker
| [reply] |
Solving Homeworks
by fundflow (Chaplain) on Sep 28, 2000 at 23:23 UTC
|
(This belongs more to the Discussions sections)
Should PM really be used for solving people's homework?
If the intent of PM is to help people improve their perl skills,
this probably doesn't.
(just a thought)
| [reply] |
|
| [reply] |
Re: finding min and max of array recursivly
by japhy (Canon) on Sep 28, 2000 at 17:23 UTC
|
One problem is that you're using 1 as your lower index bound
and arrays start at 0. Why do you have to do this recursively?
sub min_max (\@) {
my $min = my $max = $_[0][0];
for (@{ $_[0] }[1 .. $#{ $_} ]) {
$_ < $min and $min = $_, next;
$_ > $max and $max = $_;
}
return ($min,$max);
}
I'm taking a data structures and algorithms class -- if I'm
correct, I believe your recursive code is O(n log n), whereas
mine is O(n).
$_="goto+F.print+chop;\n=yhpaj";F1:eval | [reply] [d/l] |
|
Actually mine is (3n/2)+2, BUT doing this recursivly is a poor choice ..
It is an assignment for class ...
I have a algorithum almost identical to yours, that i use
for production at work ... but that isn't a luxury right now.
thanks for pointing out the 1 ... using too many different
languages right now and getting cnfused :)
although it still prints out the same results ... I don't
think it is recursing properly to all values of the array.
| [reply] |
|
Hmm, upon further inspection your algorithm is the following:
sub divide {
my $mid = @_/2;
$ITER++;
return if @_ == 1;
divide(@_[0 .. $mid - 1]);
divide(@_[$mid .. $#_]);
}
for (10 .. 30) {
$ITER = 0;
divide(1 .. $_);
printf "%2d %2d\n", $_, $ITER;
}
The order of this is N, really. Specifically, it's
2*N-1. T(N) is the time it takes to call
divide() for a list of N values:
T(1) = 1
T(2) = 1 + 2*T(1)
T(4) = 1 + 2*T(2)
...
T(N) = 1 + 2*T(N/2)
We can then expand backwards from the generality:
T(N) = 1 + 2*T(N/2)
= 1 + 2*(1 + 2*T(N/4))
= 1 + 2 + 4*T(N/4)
--> = 3 + 4*T(N/4)
= 3 + 4*(1 + 2*T(N/8))
= 3 + 4 + 8*T(N/8)
--> = 7 + 8*T(N/8)
= 7 + 8*(1 + 2*T(N/16))
= 7 + 8 + 16*T(N/16)
--> = 15 + 16*T(N/16)
The general equation here is
T(N) = 2^k - 1 + 2^k * T(N / 2^k). We will make
the following substitution: k = log(N) (base 2).
We now have:
T(N) = 2^k - 1 + 2^k * T(N / 2^k)
= 2^(log N) - 1 + 2^(log N) * T(N / 2^log(N))
= N - 1 + N * T(N/N)
= N - 1 + N * 1
= 2*N - 1
$_="goto+F.print+chop;\n=yhpaj";F1:eval | [reply] [d/l] [select] |
|
|
Re: finding min and max of array recursivly
by Anonymous Monk on Sep 28, 2000 at 19:55 UTC
|
Solved ... Slightly Round about .. but good enough for my
class. I relise that this is very sloppy, scope wise and
the way variables are being passed, but it works :)
thanks all who provided help.
sub Partition {
($A, $lower, $upper, my $min, my $max, $from) = @_;
$n = $upper - $lower + 1;
if ($n == "2") {
if ($$A$lower < "$$A$upper") {
$min = $$A$lower if $$A$lower < $min;
$max = $$A$upper if $$A$upper > $max;
$counter++;
}
elsif ($$A$upper < "$$A$lower") {
$min = $$A$upper if $$A$upper < $min;
$max = $$A$lower if $$A$lower > $max;
$counter++;
}
return ($min,$max);
}
if ($upper <= "$lower") {
return ($min, $max);
}
$mid = int(($upper - $lower) / 2) + $lower;
if ($$A$mid < "$min") {
$min = $$A$mid;
$counter++;
}
elsif ($$A$mid > "$max") {
$max = $$A$mid;
$counter++;
}
($min, $max) = Partition($A,$lower,$mid,$min,$max,"part_1");
($min, $max) = Partition($A,$mid + 1,$upper2,$min,$max,"part_2");
return($min,$max);
}
@A = (153, 1, 12, 65, 60, 214, 5, 21, 23, 19);
$length = @A - 1;
$mid = 4;
$min = $A$mid;
$max = $A$mid;
$min1 = $min;
$max1 = $max;
$mid1 = $mid;
$upper2 = $mid;
$counter = 0;
($min2, $max2) = Partition(\@A,0,$mid1,$min,$max,"main_1");
$upper2 = $length;
($min3, $max3) = Partition(\@A,$mid1 + 1,$length,$min1,$max1,"main_2");
if ($min2 < $min3) {
$min = $min2;
}
else {
$min = $min3;
}
if ($max2 > $max3) {
$max = $max2;
}
else {
$max = $max3;
}
| [reply] |
|
|