get extremes from a list of numbers
If I have a list of numbers like this:
10,9,8,8,9,7,6,5,4,6,7,8,11,10,12,14,16,20,30,29,28,29,27,25,20,18,15,10,8,5,4,1
I want to get the following numbers (according to this example): 10,4,30,1
Is it possible to write a function that receives these extremes?
These numbers are chart values, I want to get the peaks of the chart.
source to share
Mine is like jprofitt's
but I have divided them into peaks and valleys so I can do some more with that.
I think his loop is much cleaner than mine, but I just wanted to test it out for myself.
Do not judge me th e e
This script simply displays points and selects peaks and valleys and gives them green and red respectively. Look at this as a visual aid. :P
<?php
$plot = array(10,9,8,8,9,7,6,5,4,6,7,8,11,10,12,14,16,20,30,29,28,29,27,25,20,18,15,10,8,5,4,1);
$res = local_extremes($plot);
function local_extremes(array $array){
$peaks = array();
$valleys = array();
$peak_keys = array();
$valley_keys = array();
for($i = 0; $i < count($array); $i++){
$more_than_last = $array[$i] > $array[$i-1];
$more_than_next = $array[$i] > $array[$i+1];
$next_is_equal = $array[$i] == $array[$i+1];
if($next_is_equal) continue;
if($i == 0){
if($more_than_next){
$peaks[] = $array[$i];
$peak_keys[] = $i;
}else{
$valleys[] = $array[$i];
$valley_keys[] = $i;
}
}elseif($i == (count($array)-1)){
if($more_than_last){
$peaks[] = $array[$i];
$peak_keys[] = $i;
}else{
$valleys[] = $array[$i];
$valley_keys[] = $i;
}
}else{
if($more_than_last && $more_than_next){
$peaks[] = $array[$i];
$peak_keys[] = $i;
}elseif(!$more_than_last && !$more_than_next){
$valleys[] = $array[$i];
$valley_keys[] = $i;
}
}
}
return array("peaks" => $peaks, "valleys" => $valleys, "peak_keys" => $peak_keys, "valley_keys" => $valley_keys);
}
?>
<style type="text/css">
.container{
position: absolute;
}
.point{
position: absolute;
width: 4px;
height: 4px;
background: black;
}
.extreme{
position: absolute;
top: 5px;
}
.extr_low{
background: red;
}
.extr_high{
background: green;
}
</style>
<?php
//Plot
echo "<div class='container'>";
foreach($plot as $key => $point){
$left = ($key*10);
$top = 400 - ($point*10);
if(in_array($key, $res['peak_keys']) || in_array($key, $res['valley_keys'])){
$extreme = "<div class='extreme'>$point</div>";
}else{
$extreme = "";
}
if(in_array($key, $res['peak_keys'])){
$xc = "extr_high";
}elseif(in_array($key, $res['valley_keys'])){
$xc = "extr_low";
}else{
$xc = "";
}
echo "<div class='point $xc' style='left: ".$left."px; top: ".$top."px;'>$extreme</div>";
}
echo "</div>";
?>
<table>
<tr>
<th> </th>
<th>Valley</th>
<th>Peak</th>
</tr>
<tr>
<th>Lowest</th>
<td><?php echo min($res['valleys']); ?></td>
<td><?php echo min($res['peaks']); ?></td>
</tr>
<tr>
<th>Highest</th>
<td><?php echo max($res['valleys']); ?></td>
<td><?php echo max($res['peaks']); ?></td>
</tr>
</table>
source to share
I haven't tested very much and it won't actually work with anything less than 3 points, but that should give you a good starting point.
<?php
$array = array(10,9,8,8,9,7,6,5,4,6,7,8,11,10,12,14,16,20,30,29,28,29,27,25,20,18,15,10,8,5,4,1);
$extremes = array();
$last = null;
$num = count($array);
for($i=0;$i<$num - 1;$i++) {
$curr = $array[$i];
if($last === null) {
$extremes[] = $curr;
$last = $curr;
continue;
}
//min
if($last > $curr && $curr < $array[$i + 1]) {
$extremes[] = $curr;
}
//maxes
else if ($last < $curr && $curr > $array[$i + 1]) {
$extremes[] = $curr;
}
if($last != $curr && $curr != $array[$i + 1]) {
$last = $curr;
}
}
//add last point
$extremes[] = $array[$num - 1];
print_r($extremes);
Gives you the results (you missed a couple on your list):
Array
(
[0] => 10
[1] => 8
[2] => 9
[3] => 4
[4] => 11
[5] => 10
[6] => 30
[7] => 28
[8] => 29
[9] => 1
)
If you want it to be exactly like the list, you need to apply some anti-aliasing to the data or some detection tolerances.
source to share
A variant of the first test for determining local extrema, identify the points where the triangle alternates sign from one interval to the next. These points will be highs if the delta goes from positive to negative and lows if the delta goes from negative to positive, but this doesn't seem to matter to your use. Also, throw at the endpoints because the interval is considered open for this test and you seem to want them to be included.
<?php
define('MSB_MASK', (int)(PHP_INT_MAX + 1));
$points = array(0, 0, 1, 0, -1, -2, -2, -3, -4, -3, 0, 1);
$extrema = getExtrema($points);
function getExtrema($points) {
$extrema = array($points[0]);
$limit= count($points)-2;
for ($i = 0; $i < $limit; ++$i) {
$deltai = $points[$i+1]-$points[$i];
$deltaiplus1 = $points[$i+2]-$points[$i+1];
if (($deltai ^ $deltaiplus1) & MSB_MASK)
$extrema[] = $points[$i+1];
}
$extrema[] = $points[$limit+1];
return $extrema;
}
?>
Note. I tested a bit on ideone.com, it works, but it may have undetected issues. This should work for floats as well.
Credit: This is the first derivative test from every Calculus I textbook, adapted for discrete math only. We treat each point as a tipping point because we don't know the function for the graph.
Edit: Looking at the graph of the wolframalf data , I think maybe you are just looking for the global high and low on a closed interval, plus endpoints? If so, just use something simple like max($points)
and min($points)
.
Edit: I've never had a good opportunity to use xor before!
source to share
Here's the pseudocode for that
input: listOfNumbers
//Handle exceptional cases
if listOfNumbers.length == 0
return []
if listOfNumbers.length == 1
return [listOfNumbers[0]]
//Pre-condition listOfNumbers.length > 1
extremes = emptyList
lastNumber = listOfNumbers[0]
isIncreasing = listOfNumbers[0] < listOfNumbers[1]
extremes.push(listOfNumbers[0])
foreach number in listOfNumbers[1...listOfNumbers.length]
if(isIncreasing AND lastNumber > number)
extremes.push(lastNumber)
isIncreasing = false
if(NOT isIncreasing AND lastNumber < number)
extremes.push(lastNumber)
isIncreasing = true
extremes.push(listOfNumbers.length-1)
return extremes
I think it will do it, although I haven't tested it.
source to share