The stupid question is the question not asked PerlMonks

### finding local minima/maxima for a discrete array

 on Jul 31, 2007 at 06:07 UTC 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.

Create A New User
Node Status?
node history
Node Type: perlquestion [id://629742]
Approved by Corion
Front-paged by Corion
help
Chatterbox?
 [Corion]: [karlgoethebier]: anybody ever noticed the double bracket operator: while (<<>>) {print;}?

How do I use this? | Other CB clients
Other Users?
Others scrutinizing the Monastery: (9)
As of 2017-07-21 07:49 GMT
Sections?
Information?
Find Nodes?
Leftovers?
Voting Booth?
I came, I saw, I ...

Results (319 votes). Check out past polls.