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 | [reply] [d/l] [select] |
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 | [reply] [d/l] |
...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 | [reply] [d/l] [select] |
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). | [reply] [d/l] [select] |
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.
| [reply] |
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 | [reply] [d/l] |