Lowest array value given index

Discussion in 'Perl Misc' started by Jim, Oct 15, 2004.

  1. Jim

    Jim Guest

    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
    Jim, Oct 15, 2004
    #1
    1. Advertising

  2. Jim <> 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
    Perl programming
    Fort Worth, Texas
    Tad McClellan, Oct 15, 2004
    #2
    1. Advertising

  3. (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.
    A. Sinan Unur, Oct 15, 2004
    #3
  4. 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
    Gunnar Hjalmarsson, Oct 15, 2004
    #4
  5. On 2004-10-15, 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.


    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 - <> - http://www.panix.com/~dha/
    The Teletubbies are coming to America.
    They must be stopped!
    David H. Adler, Oct 15, 2004
    #5
  6. Jim

    Clyde Ingram Guest

    Jim,

    "Jim" <> wrote in message
    news:...
    > 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::Dumper;
    local $Data::Dumper::Terse = 1;
    local $Data::Dumper::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::Dumper->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::Dumper->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)
    Clyde Ingram, Oct 16, 2004
    #6
  7. 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
    Jürgen Exner, Oct 16, 2004
    #7
  8. Jim

    Anno Siegel Guest

    Jim <> 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
    Anno Siegel, Oct 18, 2004
    #8
  9. >>>>> "j" == Jim <> 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
    Charlton Wilbur, Oct 18, 2004
    #9
  10. Jim

    Eric Bohlman Guest

    "David H. Adler" <> wrote in
    news::

    > 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).
    Eric Bohlman, Oct 19, 2004
    #10
  11. On 2004-10-19, Eric Bohlman <> wrote:
    > "David H. Adler" <> wrote in
    > news::
    >
    >> 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

    --
    David H. Adler - <> - http://www.panix.com/~dha/
    "Perl Porters, Inc. today announced the release of version .006 of
    their popular Perl5 compiler suite, codenamed `Rabid Rat'."
    - Nathan Torkington on p5p (this was a *joke*)
    David H. Adler, Oct 19, 2004
    #11
  12. Jim

    Eric Bohlman Guest

    "David H. Adler" <> wrote in
    news::

    > On 2004-10-19, Eric Bohlman <> wrote:
    >> 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.
    Eric Bohlman, Oct 19, 2004
    #12
  13. Jim

    Anno Siegel Guest

    David H. Adler <> wrote in comp.lang.perl.misc:
    > On 2004-10-19, Eric Bohlman <> wrote:
    > > "David H. Adler" <> wrote in
    > > news::
    > >
    > >> 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
    Anno Siegel, Oct 19, 2004
    #13
  14. On 2004-10-19, Abigail <> wrote:
    > David H. Adler () 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

    --
    David H. Adler - <> - http://www.panix.com/~dha/
    I'd redesign my program to something less absurd.
    - Abigail, in comp.lang.perl.misc
    David H. Adler, Oct 19, 2004
    #14
  15. Jim

    Jim Guest

    "Clyde Ingram" <> wrote in message news:<PJYbd.477$>...
    > Jim,
    >
    > "Jim" <> wrote in message
    > news:...
    > > 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::Dumper;
    > local $Data::Dumper::Terse = 1;
    > local $Data::Dumper::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::Dumper->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::Dumper->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, Oct 21, 2004
    #15
  16. Jim

    Jim Guest

    "Jürgen Exner" <> wrote in message news:<xxZbd.167$TW4.3@trnddc07>...
    > 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


    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, Oct 21, 2004
    #16
  17. Jim

    Jim Guest

    Charlton Wilbur <> wrote in message news:<>...
    > >>>>> "j" == Jim <> 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


    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
    Jim, Oct 21, 2004
    #17
  18. Jim wrote:
    > "Jürgen Exner" <> wrote in message
    > news:<xxZbd.167$TW4.3@trnddc07>...
    >> 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;

    >
    > 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
    Jürgen Exner, Oct 21, 2004
    #18
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. davenet
    Replies:
    7
    Views:
    357
    Steven Bethard
    Nov 19, 2007
  2. Replies:
    3
    Views:
    855
  3. Jay
    Replies:
    0
    Views:
    145
  4. Tomasz Chmielewski

    sorting index-15, index-9, index-110 "the human way"?

    Tomasz Chmielewski, Mar 4, 2008, in forum: Perl Misc
    Replies:
    4
    Views:
    266
    Tomasz Chmielewski
    Mar 4, 2008
  5. Lowest Value in List

    , Oct 2, 2013, in forum: Python
    Replies:
    5
    Views:
    120
    Peter Otten
    Oct 3, 2013
Loading...

Share This Page