Re^2: Why does my get_max_index function return zero? (High Water Mark Algorithm)

my ($i) = map { $_->[0] } sort { $b->[1] <=> $a->[1] } map { [ $_ , $arr[$_] ] } 0..$#arr-1;

I don't understand the 0..$#arr-1 expression in the quoted statement. Did you mean 0..$#arr or 0..@arr-1 instead?

c:\@Work\Perl\monks>perl -wMstrict -le
"my @arr = (1,2,3,5,10,3,4,300,1,2,-2);
 my ($i) = map { $_->[0] } sort { $b->[1] <=> $a->[1] } map { [ $_ , $
+arr[$_] ] } 0..$#arr-1;
 print qq{i of largest == $i (\@arr[$i] == $arr[$i])};
"
i of largest == 7 (@arr[7] == 300)

c:\@Work\Perl\monks>perl -wMstrict -le
"my @arr = (1,2,3,5,10,3,4,300,1,2,-2, 999);
 my ($i) = map { $_->[0] } sort { $b->[1] <=> $a->[1] } map { [ $_ , $
+arr[$_] ] } 0..$#arr-1;
 print qq{i of largest == $i (\@arr[$i] == $arr[$i])};
"
i of largest == 7 (@arr[7] == 300)
[download]

(I'll pass over the propriety of using an O(n log n) sort operation for what is essentially an O(n) task :)

Give a man a fish: <%-{-{-{-<

Comment on Re^2: Why does my get_max_index function return zero? (High Water Mark Algorithm) Select or Download Code

Replies are listed 'Best First'.
Re^3: Why does my get_max_index function return zero? (High Water Mark Algorithm) by bliako (Abbot) on Jun 03, 2019 at 23:41 UTC
thanks fixed that to `$#arr` (I'll pass over the propriety of using an O(n log n) sort operation for what is essentially an O(n) task :) very good point	[reply] [d/l]
Re^4: Why does my get_max_index function return zero? (High Water Mark Algorithm) by AnomalousMonk (Archbishop) on Jun 04, 2019 at 02:36 UTC
FWIW, here's a GRT (decorate-sort-undecorate) approach, but still O(n log n): c:\@Work\Perl\monks>perl -wMstrict -le "use Test::More 'no_plan'; use Test::NoWarnings; ;; use List::Util qw(shuffle); ;; use constant RA => shuffle -4 .. 4; use constant RA_MAX_I => $#{[ RA ]}; ;; for my $i_ins (0 .. RA_MAX_I+1) { my @rb = ((RA)[ 0 .. $i_ins-1 ], 99, (RA)[ $i_ins .. RA_MAX_I ]); my ($i_max) = map unpack('x[N] N', $_), reverse sort map pack('N N', 0x7fff_ffff+$rb[$_], $_), 0 .. $#rb ; ok $i_ins == $i_max, qq{largest at (@rb)[$i_ins]}; } ;; done_testing; " ok 1 - largest at (99 -1 -2 4 1 -3 2 3 0 -4)[0] ok 2 - largest at (-1 99 -2 4 1 -3 2 3 0 -4)[1] ok 3 - largest at (-1 -2 99 4 1 -3 2 3 0 -4)[2] ok 4 - largest at (-1 -2 4 99 1 -3 2 3 0 -4)[3] ok 5 - largest at (-1 -2 4 1 99 -3 2 3 0 -4)[4] ok 6 - largest at (-1 -2 4 1 -3 99 2 3 0 -4)[5] ok 7 - largest at (-1 -2 4 1 -3 2 99 3 0 -4)[6] ok 8 - largest at (-1 -2 4 1 -3 2 3 99 0 -4)[7] ok 9 - largest at (-1 -2 4 1 -3 2 3 0 99 -4)[8] ok 10 - largest at (-1 -2 4 1 -3 2 3 0 -4 99)[9] 1..10 ok 11 - no warnings 1..11 [download] Give a man a fish: `<%-{-{-{-<`	[reply] [d/l] [select]
Re^5: Why does my get_max_index function return zero? (High Water Mark Algorithm) by bliako (Abbot) on Jun 04, 2019 at 11:47 UTC
I like to plant binary trees: Edit: for inserting it does a lot more comparisons than a linear search does for searching. For finding min and max there are no comparisons, just traversal. It's use is when one wants to search repeatedly the tree. I have added a `search()` to the code (30min after). Edit: after 8hrs, fixed synopsis' testing of min/max, there was a comparator mishap (`[0]<=>[1] instead of [1]<=>[0])`)! use My::Bintree; my $T = My::Bintree->new(3, sub { return $_[0] <=> $_[1] }); $T->add(5); $T->add(2); $T->add(8); $T->add(8); $T->add(8); print "maxi: ".join(",",$T->maxi())."\nmini: ".join(",",$T->mini())."\ +n"; print "searched for number 8: ".join(",", $T->search(8))."\n"; # maxi: 8 8 8 # mini: 2 # searched for number 8: 8,8,8 # or add complex data, e.g. (x,y) points and compare their distance fr +om origin $T = My::Bintree->new( # a first point: [1,2], # the comparator: sub { return $_[0]->[0]2 + $_[0]->[1]2 <=> $_[1]->[0]2 + $_[ +1]->[1]2 } ); $T->add([3,8]); $T->add([5,5]); $T->add([3,4]); $T->add([3,2]); $T->add([3,6]); $T->add([2,3]); $T->add([3,2]); $T->add([2,1]); print "furthest point(s): ".join(',', map { '(x: '.$_->[0].', y: '.$_- +>[1].')' } $T->maxi())."\n"; print "nearest point(s): ".join(',', map { '(x: '.$_->[0].', y: '.$_- +>[1].')' } $T->mini())."\n"; print "searched for points with same distance from origin as point (2, +3): ".join(',', map { '(x: '.$_->[0].', y: '.$_->[1].')' } $T->search +([2,3]))."\n"; # furthest point(s): (x: 3, y: 8) # nearest point(s): (x: 1, y: 2),(x: 2, y: 1) # searched for points with same distance from origin as point (2,3): ( +x: 3, y: 2),(x: 2, y: 3),(x: 3, y: 2) # here is how you find the max index (and value) of an array # even if there are several max/min values my @arr = (3,4,5,100,4,5,100,100, 0, 1, 2); # the comparator must return -1 if 1st arg < 2nd arg!!! (re: edit abov +e) $T = My::Bintree->new([0, shift @arr], sub { $_[0]->[1] <=> $_[1]->[1] + }); $T->add([$_,$arr[$_]]) for 0..$#arr; print "max: ".join(',', map { '(index: '.$_->[0].', value: '.$_->[1].' +)' } $T->maxi())."\n"; print "min: ".join(',', map { '(index: '.$_->[0].', value: '.$_->[1].' +)' } $T->mini())."\n"; print "searched for value of 5: ".join(',', map { '(index: '.$_->[0].' +, value: '.$_->[1].')' } $T->search([undef,5]))."\n"; # max: (index: 2, value: 100),(index: 5, value: 100),(index: 6, value: + 100) # min: (index: 7, value: 0) # searched for value of 5: (index: 1, value: 5),(index: 4, value: 5) [download] The package and tests: Read more... (13 kB) bw, bliako	[reply] [d/l] [select]