Beefy Boxes and Bandwidth Generously Provided by pair Networks
Problems? Is your data what you think it is?
 
PerlMonks  

finding local minima/maxima for a discrete array

by Anonymous Monk
on Jul 31, 2007 at 06:07 UTC ( #629742=perlquestion: print w/ replies, xml ) Need Help??
Anonymous Monk has asked for the wisdom of the Perl Monks concerning the following question:

Hello everyone, I have been trying to do this but cannot find a module or perl code or even a simple but robust algorithm to do this. I have an integer array of size n. I need to find the top k local maxima i.e. points in array that are local maxima and their magnitude is amongst top k amongst all local maxima. Any help is greatly appreciated. And thanks for the great site ! thanks Ash

Comment on finding local minima/maxima for a discrete array
Replies are listed 'Best First'.
Re: finding local minima/maxima for a discrete array
by ysth (Canon) on Jul 31, 2007 at 07:00 UTC
    Do you need to find at what indexes the minima/maxima occur, or just the values? Assuming values for the moment:
    my @minima; my @maxima; my $prev_cmp = 0; for (0 .. $#array - 1) { my $cmp = $array[$_] <=> $array[$_+1]; if ($cmp != $prev_cmp) { push @minima, $array[$_] if $cmp < 0; push @maxima, $array[$_] if $cmp > 0; # when this and next elements are ==, defer checking for # minima/maxima till next loop iteration $prev_cmp = $cmp if $cmp; } } if (@array) { push @minima, $array[-1] if $prev_cmp >= 0; push @maxima, $array[-1] if $prev_cmp <= 0; }
    (untested, probably at least one bug). Then select your top k from @minima and @maxima (or replace the pushes with an insertion sort and do it on the fly.)

    Update: wow, seems to actually work. Note that I assume no NaNs in the array (see perlop for the effect of NaNs on <=>) and that the endpoints are considered minima/maxima/both (slight changes would be needed to do otherwise).

    Update2: fixed bug when array is empty :), moved $cmp check (with no effect on results) & added a comment

      You're right ysth, it does seem to work. :)

      Advice to the OP: It is a good idea for this type of problem to devise your own test suite before you start coding a solution. To demonstrate, here is a test script that I created for ysth's solution. It's not exactly comprehensive, but I attempt to take care of the most obvious of boundary conditions.

      The way it's coded, it would be easy for you to come up with a list of your own conditions that you want to test for. Or maybe rules that you would like to change. Such as is a point of inflection truly a local min or max? Your test suite can spell out what you expect or desire.
      use Test::More; use strict; ################################# # Test Data # Each element contains [ [Test Data], [Expected Min], [Expected Max] +] # Note: The reverse of any data, should simply reverse the expected re +sults. my @testdata = ( [# Empty [], [], [], ], [ # One Entry [3], [3], [3], ], [ # Two (Up slope) [2, 4], [2], [4], ], [ # Two (No slope) [3, 3], [3], [3], ], [ # Three (No slope) [4, 4, 4], [4], [4], ], [ # Three (Up slope, beginning point of inflection) [4, 4, 6], [4], [6], ], [ # Three (Up slope, ending point of inflection) [4, 6, 6], [4], [6], ], [ # Three (negative inflection) [3,6,2], [3, 2], [6], ], [ # Three (positive infection) [10, 5, 10], [5], [10, 10], ], [ # Mixed Data # mi Mi m i M i m Mi [qw(1 1 2 3 4 4 3 2 3 4 5 6 6 6 7 8 7 7 7 3 5 6 9 9)], [qw(1 2 3)], [qw(4 8 9)], ], ); # One test each for min and max, and then times two for reverse. plan tests => 2 * (2 * @testdata); ################################# # Tests foreach (@testdata) { my ($data, $min, $max) = @$_; my ($rmin, $rmax) = local_min_max(@$data); is_deeply($rmin, $min, "min of [@$data]"); is_deeply($rmax, $max, "max of [@$data]"); my @reversed = reverse @$data; ($rmin, $rmax) = local_min_max(@reversed); is_deeply($rmin, [reverse @$min], "min of [@reversed]"); is_deeply($rmax, [reverse @$max], "max of [@reversed]"); } ################################# # Functions sub local_min_max { # Boundary Conditions return ([], []) if @_ == 0; return ([@_], [@_]) if @_ == 1; my @array = @_; my @minima; my @maxima; my $prev_cmp = 0; for (0 .. $#array - 1) { my $cmp = $array[$_] <=> $array[$_+1]; if ($cmp && $cmp != $prev_cmp) { push @minima, $array[$_] if $cmp < 0; push @maxima, $array[$_] if $cmp > 0; $prev_cmp = $cmp; } } push @minima, $array[-1] if $prev_cmp >= 0; push @maxima, $array[-1] if $prev_cmp <= 0; return (\@minima, \@maxima); }
      Ok, now back to less amusing problems.

      - Miller
Re: finding local minima/maxima for a discrete array
by Anno (Deacon) on Jul 31, 2007 at 10:16 UTC
    ...need to find the top k local maxima

    ysth has shown a nice method to find local maxima in an array. I'd like to add that it isn't necessary to store (and sort) all maxima if only the top $k are needed. A heap data structure minimizes both time- and space requirements of the task.

    Assuming a mythical Heap class with methods new, insert, extract_min, and size, create a heap

    my $heap = Heap->new;
    and then for each new local maximum $max:
    $heap->insert( $max); $heap->extract_min if $heap->size > $k;
    (This step can be optimized a little more.)

    After all are done,

    map $heap->extract_min, 1 .. $heap->size;
    returns the top $k maxima (or as many as there are) in ascending order.

    CPAN has a couple of heap-implementations.

    In practice, quite often the expense of storing and sorting the full array is irrelevant, so the heap solution isn't often implemented. I still like to point out the alternative whenever a "top $k" problem comes up.

    Anno

Re: finding local minima/maxima for a discrete array
by DrHyde (Prior) on Jul 31, 2007 at 10:46 UTC
    The algorithm is simple. Find all local maxima, for some appropriate definition of a maximum (eg, $_[0] < $_[1] > $_[2] might mean that $_[1] qualifies). Sort that list of maxima by value in descending order. Return the first k entries in the list.

    so ...

    my @values = qw(1 4 3 2 5 6 3 4 2); my @maxima = (); my $k = 2; foreach my $index (1 .. $#values - 1) { push @maxima, $values[$index] if( $values[$index-1] < $values[$index] && $values[$index+1] < $values[$index] ); } # @maxima now contains qw(4 6 4); print join(', ', (sort { $a <=> $b } @maxima)[0 .. $k - 1])."\n";
    Finding the indices of the top k maxima is left as a trivial exercise for the reader (hint: push a structure onto @maxima containing the value and index).
      That's a little oversimplified. In the case of 1 2 2 1, 2 is a local maximum. In 3 2 2 3, 2 is a local minimum. In 1 2 2 3, it's neither. You can't tell them apart just looking at the adjacent elements.
Re: finding local minima/maxima for a discrete array
by wind (Priest) on Jul 31, 2007 at 07:19 UTC
    I do not yet know of a specific module for finding local maxima. However, for global maxima and minima use List Util.
    use List::Util qw(max min); my @array = qw(5 7 3 25 10 15 8); my $max = max(@array); my $min = min(@array);
    - Miller
Re: finding local minima/maxima for a discrete array
by oha (Friar) on Jul 31, 2007 at 10:07 UTC
    i found another way, a bit faster probably:
    my $d1 = 0; my @min; my @max; for(0 .. $#data-1) { my $d = $data[$_+1]-$data[$_]; push @{ $d<0 ? \@max : \@min }, [$_, $data[$_]] if $d*$d1<=0 && $d!=0 $d1 = $d; } if($d1>0) {push @max, [$#data, $data[-1]];} if($d1<0) {push @min, [$#data, $data[-1]];} print "max $$_[1] at $$_[0]\n" for(sort {$b[1] <=> $a[1]} @max); print "min $$_[1] at $$_[0]\n" for(sort {$a[1] <=> $b[1]} @min);
    $d*$d1 will be negative when the sign of $d and $d1 does not match, meaning that the the values passed from increasing to decreasing or vice-versa

    Oha

      You can't do the $d1 = $d when $d is 0 or you treat the transition between 2 and 3 as significant in 1 2 2 3. I think your $d * $d1 <= 0 && $d != 0 is the same (only slightly slower, not faster as you guess) as $d && $d != $d1 with $d set by <=> instead of -. With the final checks after the for loop being > and < , it's treated as neither a minimum or maximum when the whole array is equal; with >= and <= instead it's treated as both. You could argue for either way.

Log In?
Username:
Password:

What's my password?
Create A New User
Node Status?
node history
Node Type: perlquestion [id://629742]
Approved by Corion
Front-paged by Corion
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others taking refuge in the Monastery: (10)
As of 2015-07-29 23:46 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    The top three priorities of my open tasks are (in descending order of likelihood to be worked on) ...









    Results (269 votes), past polls