Velocity Reviews > Perl > Lowest array value given index

# Lowest array value given index

Jim
Guest
Posts: n/a

 10-15-2004
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

Guest
Posts: n/a

 10-15-2004
Jim <(E-Mail Removed)> wrote:

> 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...

--
http://www.velocityreviews.com/forums/(E-Mail Removed) Perl programming
Fort Worth, Texas

A. Sinan Unur
Guest
Posts: n/a

 10-15-2004
(E-Mail Removed) (Jim) wrote in news:3966ee66.0410151008.3b38007

> 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.

Guest
Posts: n/a

 10-15-2004
Jim wrote:
> 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.

--
Email: http://www.gunnar.cc/cgi-bin/contact.pl

Guest
Posts: n/a

 10-15-2004
On 2004-10-15, Jim <(E-Mail Removed)> wrote:
> 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

--
David H. Adler - <(E-Mail Removed)> - http://www.panix.com/~dha/
The Teletubbies are coming to America.
They must be stopped!

Clyde Ingram
Guest
Posts: n/a

 10-15-2004
Jim,

"Jim" <(E-Mail Removed)> wrote in message
news:(E-Mail Removed) m...
> 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..
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
Guest
Posts: n/a

 10-16-2004
Jim wrote:
> 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

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

jue

Anno Siegel
Guest
Posts: n/a

 10-18-2004
Jim <(E-Mail Removed)> wrote in comp.lang.perl.misc:
> 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...

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
Guest
Posts: n/a

 10-18-2004
>>>>> "j" == Jim <(E-Mail Removed)> writes:

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

--
cwilbur at chromatico dot net
cwilbur at mac dot com

Eric Bohlman
Guest
Posts: n/a

 10-19-2004
"David H. Adler" <(E-Mail Removed)> wrote in
news:(E-Mail Removed):

> 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).