Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > Perl > Perl Misc > Lowest array value given index

Reply
Thread Tools

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
 
Reply With Quote
 
 
 
 
Tad McClellan
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...


--
Tad McClellan SGML consulting
http://www.velocityreviews.com/forums/(E-Mail Removed) Perl programming
Fort Worth, Texas
 
Reply With Quote
 
 
 
 
A. Sinan Unur
Guest
Posts: n/a
 
      10-15-2004
(E-Mail Removed) (Jim) wrote in news:3966ee66.0410151008.3b38007
@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.
 
Reply With Quote
 
Gunnar Hjalmarsson
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.

--
Gunnar Hjalmarsson
Email: http://www.gunnar.cc/cgi-bin/contact.pl
 
Reply With Quote
 
David H. Adler
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!
 
Reply With Quote
 
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)


 
Reply With Quote
 
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
optimal already:

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

jue


 
Reply With Quote
 
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...


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
 
Reply With Quote
 
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
 
Reply With Quote
 
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).
 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
sorting index-15, index-9, index-110 "the human way"? Tomasz Chmielewski Perl Misc 4 03-04-2008 05:01 PM
getting index to parentNode's childNodes array given an element id yawnmoth Javascript 1 06-24-2006 09:19 AM
ListControl SelectedItem gets the lowest index with same value pro Jay ASP .Net Web Controls 0 09-26-2005 02:14 PM
Given an array a[N] with value 1...N, find a repeted value cai_rongxi@hotmail.com C Programming 5 12-29-2004 12:31 AM
New Zealand, on the other hand, has one of the lowest growth rates and one of the lowest levels of broadband penetration in the world. punlic NZ Computing 6 05-02-2004 10:28 AM



Advertisments