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

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: <%-{-{-{-<

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

Replies are listed 'Best First'.
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]

Replies are listed 'Best First'.

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: