Lowest array value given index

[Jim]

I'm trying to find an efficient way of finding the lowest value of an
array but starting at a given index. For example:

@array = (0, 0, 1, 2, 0, 1, 1, 1);
$index = 0;

I want to stay on the 1st element.


@array = (0, 0, 1, 2, 0, 1, 1, 1);
$index = 2;

I want to end up on the 5th element.


@array = (0, 0, 1, 2, 0, 1, 1, 1);
$index = 5;

I want to end up on the 1st element.


Any suggestions on an efficient way to do this? Thanks...
Jim

 

[Tad McClellan]

I'm trying to find an efficient way of finding the lowest value of an
array but starting at a given index.

(sort @array[$index .. $#array])[0]

@array = (0, 0, 1, 2, 0, 1, 1, 1);
$index = 0;

I want to stay on the 1st element.

Now you have changed the problem.

Above you said you want the lowest _value_, now it appears that
you want the _index_ of the lowest value.

Which is it?

@array = (0, 0, 1, 2, 0, 1, 1, 1);
$index = 5;

I want to end up on the 1st element.

Huh?

I would have thought that you wanted the 5th element there...

Any suggestions on an efficient way to do this?

My suggestion above is not efficient with respect to time complexity,
but it is efficient with respect to development time.

You did not say what it was exactly that you mean to optimize...

 

[A. Sinan Unur]

(e-mail address removed) (Jim) wrote in @posting.google.com:

Any suggestions on an efficient way to do this? Thanks...

Jim:

Try to explain what you want to achieve. Your examples do not make much
sense and your problem statement can be iterpreted in many different ways.

You will see that if you actually spend effort stating your problem, it
will be easier to solve.

Sinan.

 

[Gunnar Hjalmarsson]

I'm trying to find an efficient way of finding the lowest value of
an array but starting at a given index. For example:

@array = (0, 0, 1, 2, 0, 1, 1, 1);
$index = 0;

I want to stay on the 1st element.


@array = (0, 0, 1, 2, 0, 1, 1, 1);
$index = 2;

I want to end up on the 5th element.


@array = (0, 0, 1, 2, 0, 1, 1, 1);
$index = 5;

I want to end up on the 1st element.

Show us one or two ways you have done it so far, and somebody will
probably comment on the efficiency of the method(s) you are using.

 

[David H. Adler]

I'm trying to find an efficient way of finding the lowest value of an
array but starting at a given index. For example:

@array = (0, 0, 1, 2, 0, 1, 1, 1);
$index = 0;

I want to stay on the 1st element.


@array = (0, 0, 1, 2, 0, 1, 1, 1);
$index = 2;

I want to end up on the 5th element.

Something along the lines of

$result = find_lowest_element(@array[$index..$#array])

should solve part of your problem.

[benchmarks]

Holy moley!

Benchmark: timing 500000 iterations of slice, splice...
slice: 351 wallclock secs (183.32 usr + 1.25 sys = 184.57 CPU)
@ 2709.00/s (n=500000)

splice: 2 wallclock secs ( 0.37 usr + 0.02 sys = 0.39 CPU) @
1282051.28/s (n=500000)

Ok, *don't* do that.

$result = find_lowest_element(splice @array, $index);

dha

 

[Clyde Ingram]

Jim,

I'm trying to find an efficient way of finding the lowest value of an
array but starting at a given index. For example:

@array = (0, 0, 1, 2, 0, 1, 1, 1);

<SNIP>

My attempt outputs this:

Scan from element 1 (index 0)
[1,2,3,4,5,6,7,8][]
[0,0,1,2,0,1,1,1][]
Lowest value is 0
at element 1

Scan from element 3 (index 2)
[3,4,5,6,7,8][1,2]
[1,2,0,1,1,1][0,0]
Lowest value is 0
at element 5

Scan from element 6 (index 5)
[6,7,8][1,2,3,4,5]
[1,1,1][0,0,1,2,0]
Lowest value is 0
at element 1

That gets the answers you want.

Any suggestions on an efficient way to do this? Thanks...

"Efficient" compared with what?
It is conventional for you to show us what you have tried.
Otherwise, respondents cannot compare efficiency of their algorithms with
yours.
(And there is the lurking suspicion that you might have tried nothing at
all.
Such a case is often described as a "homework question".)

I used "splice", "push", and a "for"-loop, which are simple enough, but I
make no claims for great efficiency.
How many elements might you encounter in the array in your production
program?
FWIW, my code is below. (Excuse the length of this posting, people.)

Regards,
Clyde

#!/bin/perl -w
use strict;
use Data:umper;
local $Data:umper::Terse = 1;
local $Data:umper::Indent = 0;

my @array = ( 0, 0, 1, 2, 0, 1, 1, 1 );
my @indices = ( 0, 2, 5 );

for my $index ( @indices ) {

# We are going to skip the leading elements of the array, and
# start our scan from the given index.
# $index numbers from 0 (e.g.: 5)
# $element_nr numbers from 1 (e.g.: 6)

my $element_nr = $index+1;
print "\nScan from element $element_nr (index $index)\n";

my @arr = @array; # Copy array, before splicing it

if ( ($index < 0) or ($index > $#arr) ) {
warn "$index: index out of range 0..$#arr. Ignoring\n\n";
next;
}

# Remember ranges of element numbers in skipping and starting portions
# e.g.: (1..5) and (6..8)
my @skipping_element_nrs = ( 1 .. ($element_nr - 1) );
my @starting_element_nrs = ( $element_nr .. (scalar @arr ) );

# Remove the leading $index elements of @arr, into new array @skip
# e.g.: for index 5, we will skip elements (1..5)
my @skip = splice( @arr, 0, $index );

# Print out 2 arrays of element numbers, one from the starting element
# to the end, the second for the element numbers we skipped.
# e.g.: [6,7,8][1,2,3,4,5]
print Data:umper->Dump( [
\@starting_element_nrs, \@skipping_element_nrs ] ) . "\n";

# Then print corresponding 2 arrays of elements
# e.g.: [1,1,1][0,0,1,2,0]
print Data:umper->Dump( [\@arr, \@skip] ) . "\n";

# Push the skipped elements onto the end of @arr
push( @arr, @skip );

# Scan the re-formed array @arr for the lowest value and its index
my $new_index_of_lowest = 0;

for my $i (1 .. $#arr) {

$new_index_of_lowest = $i if ($arr[$i] <
$arr[$new_index_of_lowest]);
}

# Work out element nr of lowest, with respect to original array,
# remembering that search wraps around the end of the array
my $old_element_nr_of_lowest = ($new_index_of_lowest+$index)%(scalar
@arr)+1;

print "Lowest value is $arr[$new_index_of_lowest]\n";
print "at element $old_element_nr_of_lowest\n";
}

(End of response)

 

[Jürgen Exner]

I'm trying to find an efficient way of finding the lowest value of an
array but starting at a given index.

Well, you have to look at every single value between your start index and
the end of the array at least once anyway. In other words obviously your
algorithm cannot become better then O(n).
Therefore the straight-forward, linear approach is probably very close to
optimal already:

my $min = $array[$i]; # $i be the given starting index
for (@array[$i..$#array]) {
if ($min > $_) { $min = $_;}
}
print $min;

jue

 

[Anno Siegel]

I'm trying to find an efficient way of finding the lowest value of an

No. Apparently, you are looking for the *index* of the lowest value.

array but starting at a given index. For example:

@array = (0, 0, 1, 2, 0, 1, 1, 1);
$index = 0;

I want to stay on the 1st element.


@array = (0, 0, 1, 2, 0, 1, 1, 1);
$index = 2;

I want to end up on the 5th element.


@array = (0, 0, 1, 2, 0, 1, 1, 1);
$index = 5;

I want to end up on the 1st element.


Any suggestions on an efficient way to do this? Thanks...

Your problem description is contradictory and insufficient.

I'll suppose you want to walk the array cyclically, starting at
a given index, and record the first occurrence of the minimal array
value.

my @array = (0, 0, 1, 2, 0, 1, 1, 1);

for my $i ( 0, 2, 5) {
my ( $min, $imin) = ( $array[ $i], $i);
$min > $array[ $_] and ( $min, $imin) = ( $array[ $_], $_) for
map $_ % @array, $i .. $i + $#array;
print "$i -> $imin\n";
}


Anno

 

[Charlton Wilbur]

j> I'm trying to find an efficient way of finding the lowest value
j> of an array but starting at a given index.

This one is clear code; you need to examine every element to determine
that you have the lowest one. Anything more efficient than this will
probably require arcane knowledge of perl internals which are likely
to change from version to version.

my $low_index = $index;
for ($index .. $#array, 0 .. $index - 1)
{
$low_index = $_
if $array[$_] < $array[$low_index];
}

print "low element is at index $low_index\n";



Charlton

 

[Eric Bohlman]

Something along the lines of

$result = find_lowest_element(@array[$index..$#array])

should solve part of your problem.

[benchmarks]

Holy moley!

Benchmark: timing 500000 iterations of slice, splice...
slice: 351 wallclock secs (183.32 usr + 1.25 sys = 184.57 CPU)
@ 2709.00/s (n=500000)

splice: 2 wallclock secs ( 0.37 usr + 0.02 sys = 0.39 CPU) @
1282051.28/s (n=500000)

Ok, *don't* do that.

$result = find_lowest_element(splice @array, $index);

Er, I think the reason it's running so fast is that it isn't doing what it
ought to. That's the equivalent of:

@array=@array[0..$index-1];
$result=find_lowest_element(@array);

So you're looking only at elements *before* $index, contrary to the OP's
spec, *and* you're truncating @array to the number of elements given by the
smallest value of $index, which was probably one of the first ones used (if
your test code was refreshing @array on each iteration, then ignore my
second clause).

 

[David H. Adler]

Something along the lines of

$result = find_lowest_element(@array[$index..$#array])

should solve part of your problem.

[benchmarks]

Holy moley!

Benchmark: timing 500000 iterations of slice, splice...
slice: 351 wallclock secs (183.32 usr + 1.25 sys = 184.57 CPU)
@ 2709.00/s (n=500000)

splice: 2 wallclock secs ( 0.37 usr + 0.02 sys = 0.39 CPU) @
1282051.28/s (n=500000)

Ok, *don't* do that.

$result = find_lowest_element(splice @array, $index);

Er, I think the reason it's running so fast is that it isn't doing what it
ought to. That's the equivalent of:

@array=@array[0..$index-1];
$result=find_lowest_element(@array);

So you're looking only at elements *before* $index, contrary to the OP's
spec, *and* you're truncating @array to the number of elements given by the
smallest value of $index, which was probably one of the first ones used (if
your test code was refreshing @array on each iteration, then ignore my
second clause).

Hm. Perhaps I'm confused, but how do you get that?

My code for those benchmarks was:

my @init = (1..1000);

timethese( shift || 10000,
{ slice => sub {my @array = @init[30..1000];},
splice => sub {my @array = splice @init, 30;}
});

So I'm not sure how you're getting a range of [0..$index-1];

In any case, I just noticed a slight oddity. if I change the slice code
to

sub {my @array = @init[30..-1];}

we get this benchmark:

Benchmark: timing 1000000 iterations of slice, splice...
slice: 1 wallclock secs ( 0.64 usr + 0.03 sys = 0.67 CPU)
@ 1492537.31/s (n=1000000)
splice: 0 wallclock secs ( 0.70 usr + 0.01 sys = 0.71 CPU)
@ 1408450.70/s (n=1000000)

Is it me or is that just odd?

dha

 

[Eric Bohlman]

So you're looking only at elements *before* $index, contrary to the
OP's spec, *and* you're truncating @array to the number of elements
given by the smallest value of $index, which was probably one of the
first ones used (if your test code was refreshing @array on each
iteration, then ignore my second clause).

Hm. Perhaps I'm confused, but how do you get that?

My code for those benchmarks was:

my @init = (1..1000);

timethese( shift || 10000,
{ slice => sub {my @array = @init[30..1000];},
splice => sub {my @array = splice @init, 30;}
});

So I'm not sure how you're getting a range of [0..$index-1];

I had forgotten that splice() returns the *removed* elements rather than
the remaining ones (actually *reading*, rather than *skimming*, the docs
for splice() cleared that up). However, there's still a problem. After
the first iteration, splice() will have truncated @init to 30 elements and
will return an empty list on subsequent iterations.

 

[Anno Siegel]

Something along the lines of

$result = find_lowest_element(@array[$index..$#array])

should solve part of your problem.

[benchmarks]

Holy moley!

Benchmark: timing 500000 iterations of slice, splice...
slice: 351 wallclock secs (183.32 usr + 1.25 sys = 184.57 CPU)
@ 2709.00/s (n=500000)

splice: 2 wallclock secs ( 0.37 usr + 0.02 sys = 0.39 CPU) @
1282051.28/s (n=500000)

Ok, *don't* do that.

$result = find_lowest_element(splice @array, $index);

Er, I think the reason it's running so fast is that it isn't doing what it
ought to. That's the equivalent of:

@array=@array[0..$index-1];
$result=find_lowest_element(@array);

So you're looking only at elements *before* $index, contrary to the OP's
spec, *and* you're truncating @array to the number of elements given by the
smallest value of $index, which was probably one of the first ones used (if
your test code was refreshing @array on each iteration, then ignore my
second clause).

Hm. Perhaps I'm confused, but how do you get that?

My code for those benchmarks was:

my @init = (1..1000);

timethese( shift || 10000,
{ slice => sub {my @array = @init[30..1000];},
splice => sub {my @array = splice @init, 30;}
});

So I'm not sure how you're getting a range of [0..$index-1];

No, but splice will consume @init after a few rounds and do nothing
after that. Depending on which will run first, slice will see an
empty array or not.

In any case, I just noticed a slight oddity. if I change the slice code
to

sub {my @array = @init[30..-1];}

Well, that makes sure that slice doesn't do nothing in either case.
I think you want "@init[30 .. $#init]".

For a real benchmark one would have to reset @init before each run
(Results slightly edited):

my @supply = (1..1000);

timethese( shift || -3, {
slice => sub {my @init = @supply; my @array = @init[30..-1];},
splice => sub {my @init = @supply; my @array = splice @init, 30;},
null => sub { my @init = @supply },
},
);

Benchmark: running null, slice, splice for at least 3 CPU seconds...
null: 3 wallclock secs ( 3.19 CPU) @ 181.82/s (n=580)
slice: 3 wallclock secs ( 3.20 CPU) @ 177.81/s (n=569)
splice: 4 wallclock secs ( 3.17 CPU) @ 85.80/s (n=272)

That is as expected, but the results for "null" show that most of
the time in slice is spent in the array assignment.

Anno

 

[David H. Adler]

David H. Adler ([email protected]) wrote on MMMMLXVII September MCMXCIII in

[snip lots of benchmarking in odd directions]

## Is it me or is that just odd?


It's you ;-)

Yes. Yes it is. Time for sleep I think.

dha

 

[Jim]

Jim,

I'm trying to find an efficient way of finding the lowest value of an
array but starting at a given index. For example:

@array = (0, 0, 1, 2, 0, 1, 1, 1);

<SNIP>

My attempt outputs this:

Scan from element 1 (index 0)
[1,2,3,4,5,6,7,8][]
[0,0,1,2,0,1,1,1][]
Lowest value is 0
at element 1

Scan from element 3 (index 2)
[3,4,5,6,7,8][1,2]
[1,2,0,1,1,1][0,0]
Lowest value is 0
at element 5

Scan from element 6 (index 5)
[6,7,8][1,2,3,4,5]
[1,1,1][0,0,1,2,0]
Lowest value is 0
at element 1

That gets the answers you want.

Any suggestions on an efficient way to do this? Thanks...

"Efficient" compared with what?
It is conventional for you to show us what you have tried.
Otherwise, respondents cannot compare efficiency of their algorithms with
yours.
(And there is the lurking suspicion that you might have tried nothing at
all.
Such a case is often described as a "homework question".)

I used "splice", "push", and a "for"-loop, which are simple enough, but I
make no claims for great efficiency.
How many elements might you encounter in the array in your production
program?
FWIW, my code is below. (Excuse the length of this posting, people.)

Regards,
Clyde

#!/bin/perl -w
use strict;
use Data:umper;
local $Data:umper::Terse = 1;
local $Data:umper::Indent = 0;

my @array = ( 0, 0, 1, 2, 0, 1, 1, 1 );
my @indices = ( 0, 2, 5 );

for my $index ( @indices ) {

# We are going to skip the leading elements of the array, and
# start our scan from the given index.
# $index numbers from 0 (e.g.: 5)
# $element_nr numbers from 1 (e.g.: 6)

my $element_nr = $index+1;
print "\nScan from element $element_nr (index $index)\n";

my @arr = @array; # Copy array, before splicing it

if ( ($index < 0) or ($index > $#arr) ) {
warn "$index: index out of range 0..$#arr. Ignoring\n\n";
next;
}

# Remember ranges of element numbers in skipping and starting portions
# e.g.: (1..5) and (6..8)
my @skipping_element_nrs = ( 1 .. ($element_nr - 1) );
my @starting_element_nrs = ( $element_nr .. (scalar @arr ) );

# Remove the leading $index elements of @arr, into new array @skip
# e.g.: for index 5, we will skip elements (1..5)
my @skip = splice( @arr, 0, $index );

# Print out 2 arrays of element numbers, one from the starting element
# to the end, the second for the element numbers we skipped.
# e.g.: [6,7,8][1,2,3,4,5]
print Data:umper->Dump( [
\@starting_element_nrs, \@skipping_element_nrs ] ) . "\n";

# Then print corresponding 2 arrays of elements
# e.g.: [1,1,1][0,0,1,2,0]
print Data:umper->Dump( [\@arr, \@skip] ) . "\n";

# Push the skipped elements onto the end of @arr
push( @arr, @skip );

# Scan the re-formed array @arr for the lowest value and its index
my $new_index_of_lowest = 0;

for my $i (1 .. $#arr) {

$new_index_of_lowest = $i if ($arr[$i] <
$arr[$new_index_of_lowest]);
}

# Work out element nr of lowest, with respect to original array,
# remembering that search wraps around the end of the array
my $old_element_nr_of_lowest = ($new_index_of_lowest+$index)%(scalar
@arr)+1;

print "Lowest value is $arr[$new_index_of_lowest]\n";
print "at element $old_element_nr_of_lowest\n";
}

(End of response)

Sorry I didn't post my code earlier. This is how I "solved" my
problem. And yes, I was looking for the index of the lowest value.


my $min = $dept[$index_critical][$SEV1];
for my $i ($index_critical .. $#dept) {
if ($dept[$i][$SEV1] < $min) {
$min = $dept[$i][$SEV1];
$index_dept = $i;
}
}
for my $i (0 .. $index_critical) {
if ($dept[$i][$SEV1]) {
$min = $dept[$i][$SEV1];
$index_dept = $i;
}
}

Basically, I start at my starting index and go to the end to see if
there is a lower value. Then, I start at the beginning and go to the
starting index to see if there is a lower value. This way I get the
index of the lowest value starting at my index. It works, I just
don't particularly like the 2 for loops.

Thanks for all the responses (even those that I apparently confused
the requirements of, sorry) and any future responses on improving
this.

Jim

 

[Jim]

I'm trying to find an efficient way of finding the lowest value of an
array but starting at a given index.

Well, you have to look at every single value between your start index and
the end of the array at least once anyway. In other words obviously your
algorithm cannot become better then O(n).
Therefore the straight-forward, linear approach is probably very close to
optimal already:

my $min = $array[$i]; # $i be the given starting index
for (@array[$i..$#array]) {
if ($min > $_) { $min = $_;}
}
print $min;

jue

Except this doesn't conform to the requirement of starting at a
specified index in the array. If I want to start at index 5 with a
value of 1 and both index 1 and index 7 have values of 0, I want to
get back index 7, not index 1.

Thanks... Jim

 

[Jim]

j> I'm trying to find an efficient way of finding the lowest value
j> of an array but starting at a given index.

This one is clear code; you need to examine every element to determine
that you have the lowest one. Anything more efficient than this will
probably require arcane knowledge of perl internals which are likely
to change from version to version.

my $low_index = $index;
for ($index .. $#array, 0 .. $index - 1)
{
$low_index = $_
if $array[$_] < $array[$low_index];
}

print "low element is at index $low_index\n";



Charlton

This looks good! This looks like it performs the exact same thing I
coded but in less "lines"..

my $min = $dept[$index_critical][$SEV1];
for my $i ($index_critical .. $#dept) {
if ($dept[$i][$SEV1] < $min) {
$min = $dept[$i][$SEV1];
$index_dept = $i;
}
}
for my $i (0 .. $#dept) {
if ($dept[$i][$SEV1] < $min) {
$min = $dept[$i][$SEV1];
$index_dept = $i;
}
}

should be able to become

my $index_dept = $index_critical;
for ($index_critical .. $#dept, 0 .. $index_critical - 1) {
$index_dept = $_ if ($dept[$_][$SEV1] <
$dept[$index_dept][$SEV1]);
}

I'll give it a shot.. Thanks!

Jim

 

[Jürgen Exner]

I'm trying to find an efficient way of finding the lowest value of
an array but starting at a given index.

Well, you have to look at every single value between your start
index and the end of the array at least once anyway. In other words
obviously your algorithm cannot become better then O(n).
Therefore the straight-forward, linear approach is probably very
close to optimal already:

my $min = $array[$i]; # $i be the given starting index
for (@array[$i..$#array]) {
if ($min > $_) { $min = $_;}
}
print $min;

Except this doesn't conform to the requirement of starting at a
specified index in the array. If I want to start at index 5 with a
value of 1 and both index 1 and index 7 have values of 0, I want to
get back index 7, not index 1.

Did you try it?
I guess you didn't notice that the loop _starts_ at the given start index
(as it says "be $i the starting index"). Therefore it cannot return the
unwanted index 1 because it is not part of the search space to begin with.

jue