Velocity Reviews > min max of a list

# min max of a list

querypk@gmail.com
Guest
Posts: n/a

 05-04-2005
If this is the list.

values = [ 0, 72, 0, 4, 9, 2, 0, 0, 42, 26, 0, 282,
23, 0, 101, 0, 0, 0, 0, 0]

as we can see there are peaks in the list.that is 0,72,0 is a
group(triangle) with peak 72.then 0, 4, 9, 2, 0, 0 with peak
9 and 0, 42, 26, 0 with 42 and so on...
what I want is the left and right bound index of each bin(triangle).The
list could as big as possible.So some heurestic algorithm which could
first find max in the list and look for local maxima and minima and
group its adjcent bounds.Then find next max and group the bins and so
on.

so that we can get

[[0,2],[2,7],[7,10],[10,13]]
( indexes of the bounds in the values list). so first group [0,2]
correspond to 0,72,0 in the values list and so on...
Hope I am clear.

Steven Bethard
Guest
Posts: n/a

 05-05-2005
wrote:
> If this is the list.
>
> values = [ 0, 72, 0, 4, 9, 2, 0, 0, 42, 26, 0, 282,
> 23, 0, 101, 0, 0, 0, 0, 0]
>
> as we can see there are peaks in the list.that is 0,72,0 is a
> group(triangle) with peak 72.then 0, 4, 9, 2, 0, 0 with peak
> 9 and 0, 42, 26, 0 with 42 and so on...
> what I want is the left and right bound index of each bin(triangle).The
> list could as big as possible.So some heurestic algorithm which could
> first find max in the list and look for local maxima and minima and
> group its adjcent bounds.Then find next max and group the bins and so
> on.
>
> so that we can get
>
> [[0,2],[2,7],[7,10],[10,13]]
> ( indexes of the bounds in the values list). so first group [0,2]
> correspond to 0,72,0 in the values list and so on...
> Hope I am clear.

Not exactly your output, but hopefully you can tailor it to your needs:

py> values = [0, 72, 0, 4, 9, 2, 0, 0, 42, 26, 0, 282, 23, 0, 101, 0, 0,
0, 0, 0]
py> def isnonzero((index, val)):
.... return val != 0
....
py> import itertools
py> for nonzero, vals in itertools.groupby(enumerate(values), isnonzero):
.... if nonzero:
.... vals = list(vals)
.... start = vals[0][0] - 1
.... end = vals[-1][0] + 1
.... print [start, end], "values: ", values[start:end+1]
....
[0, 2] values: [0, 72, 0]
[2, 6] values: [0, 4, 9, 2, 0]
[7, 10] values: [0, 42, 26, 0]
[10, 13] values: [0, 282, 23, 0]
[13, 15] values: [0, 101, 0]

Note that the real work is done by itertools.groupby. Zero terms are
grouped together and ignored; non-zero terms are gathered together in lists.

STeVe

querypk@gmail.com
Guest
Posts: n/a

 05-05-2005
Thanks for that. My version of python does'nt find "groupby". I am
using python 2.3.2. Is there a way I could do it with out using groupby

Steven Bethard
Guest
Posts: n/a

 05-05-2005
wrote:
> Thanks for that. My version of python does'nt find "groupby". I am
> using python 2.3.2. Is there a way I could do it with out using groupby

itertools.groupby is in Python 2.4. The docs[1] give a Python
equivalent, so if for some reason you can't upgrade to the current
version of Python, you can just copy the groupby code from there.

STeVe

[1]http://docs.python.org/lib/itertools-functions.html#l2h-1379

querypk@gmail.com
Guest
Posts: n/a

 05-05-2005
what if we do something like this. Assume the values list is the
content of a histogram. Then we see that
values = [ 0, 72, 0, 4, 9, 2, 0, 0, 42, 26, 0, 282,
23, 0, 101, 0, 0, 0, 0, 0]
1 is repeated 72 times, 3 -> 4 times and so on. That is the index
would be the value repeated as many times as in the list.
Now If we find the max and look for the adjcent index. FOr example

take 282 :

Index of 282 --> 11
now check for value of index 10 and 12 .If value(10) < value(9) then
there is a dip as value(9) and value(11) are greater than value(10).
that could be the lower bound of that range. then if
value(11) and value(13) for value(12). if value(11)< value(10) there is
a dip. SO the bounds of [10,12] -> [0,282,23] rather than [10, 13]
values: [0, 282, 23, 0] ( in your case).
How would this work. Is there someway I could do this faster.

querypk@gmail.com
Guest
Posts: n/a

 05-06-2005
Hi Steve!
I am not sure if I was clear with my previous post .Ok let me rephrase
it .

Assume the values list is the
content of a histogram. Then we see that
values = [ 0, 72, 2, 4, 9, 2, 0, 0, 42, 26, 0, 282,
23, 0, 101, 0, 0, 0, 0, 0]

1 is repeated 72 times, 3 -> 4 times and so on. That is the index
would be the value repeated as many times as in the list.
Now If we find the max and look for the adjcent index.

That is if we plot the above list as a histogram. We will have crests
and troughs ie peaks and dips. if we find two dips then the region
between the two dips could be a range like [0, 72, 2] .So here we
are not looking for a zero. But if we find dips then we consider the
regions between it as a bin and group it.

| /\
| /\ / \ /\
| / \/ \/ \
|/_____________________________________
|----|-----|---|
1 2 3

so pictorially. In the above plot. If y axis is the list above. then we
need to bin it this way.
If I use you previous approach using the groupby then all these three
regions will be considered as one.

Hope I am clear this time.

Kent Johnson
Guest
Posts: n/a

 05-06-2005
wrote:
> If this is the list.
>
> values = [ 0, 72, 0, 4, 9, 2, 0, 0, 42, 26, 0, 282,
> 23, 0, 101, 0, 0, 0, 0, 0]
>
> as we can see there are peaks in the list.that is 0,72,0 is a
> group(triangle) with peak 72.then 0, 4, 9, 2, 0, 0 with peak
> 9 and 0, 42, 26, 0 with 42 and so on...
> what I want is the left and right bound index of each bin(triangle).The
> list could as big as possible.So some heurestic algorithm which could
> first find max in the list and look for local maxima and minima and
> group its adjcent bounds.Then find next max and group the bins and so
> on.
>
> so that we can get
>
> [[0,2],[2,7],[7,10],[10,13]]
> ( indexes of the bounds in the values list). so first group [0,2]
> correspond to 0,72,0 in the values list and so on...
> Hope I am clear.

ISTM you just have to look for the valleys - places where the values change from descending to
ascending. Here is a simple-minded way to do it:

def findPeaks(values):
groups = []
startIx = 0
lastValue = values[0]
ascending = True

for i, value in enumerate(values[1:]):
if value <= lastValue:
ascending = False
else:
if not ascending:
# Switch from descending to ascending
groups.append( [startIx, i] )
startIx = i
ascending = True

lastValue = value

# Get the last group if any
if i > startIx:
groups.append( [startIx, i] )

return groups

values = [ 0, 72, 2, 4, 9, 2, 0, 0, 42, 26, 0, 282,
23, 0, 101, 0, 0, 0, 0, 0]

print findPeaks(values)

## prints:
[[0, 2], [2, 7], [7, 10], [10, 13], [13, 18]]

Kent

Steven Bethard
Guest
Posts: n/a

 05-06-2005
wrote:
> Hi Steve!
> I am not sure if I was clear with my previous post .Ok let me rephrase
> it .
>
> Assume the values list is the
> content of a histogram. Then we see that
> values = [ 0, 72, 2, 4, 9, 2, 0, 0, 42, 26, 0, 282,
> 23, 0, 101, 0, 0, 0, 0, 0]
>
> 1 is repeated 72 times, 3 -> 4 times and so on. That is the index
> would be the value repeated as many times as in the list.
> Now If we find the max and look for the adjcent index.
>
> That is if we plot the above list as a histogram. We will have crests
> and troughs ie peaks and dips. if we find two dips then the region
> between the two dips could be a range like [0, 72, 2] .So here we
> are not looking for a zero. But if we find dips then we consider the
> regions between it as a bin and group it.
>
> | /\
> | /\ / \ /\
> | / \/ \/ \
> |/_____________________________________
> |----|-----|---|
> 1 2 3
>
> so pictorially. In the above plot. If y axis is the list above. then we
> need to bin it this way.
> If I use you previous approach using the groupby then all these three
> regions will be considered as one.
>
> Hope I am clear this time.

So you want the peaks and valleys basically. Well, using itools.window
from http://aspn.activestate.com/ASPN/Coo.../Recipe/299529, you
could do something like:

py> values = [0,72,2,4,9,2,0,0,42,26,0,282,23,0,101,0,0,0,0,0]
py> peaks = [i
.... for i, (v1, v2, v3) in enumerate(itools.window(values))
.... if v1 < v2 and v2 > v3]
py> peaks
[1, 4, 8, 11, 14]
py> valleys = [i
.... for i, (v1, v2, v3) in enumerate(itools.window(values))
.... if v1 >= v2 and v2 <= v3]
py> valleys
[2, 6, 7, 10, 13, 15, 16, 17, 18]
py> [(min((abs(p - v), v) for v in valleys + [0] if v < p)[1],
.... p,
.... min((abs(p - v), v) for v in valleys if v > p)[1])
.... for p in peaks]
[(0, 1, 2), (2, 4, 6), (7, 8, 10), (10, 11, 13), (13, 14, 15)]

This is not likely the most efficient approach, but it's pretty simple:
* identify the peaks and valleys
* identify the valley on each side of a peak

STeVe

querypk@gmail.com
Guest
Posts: n/a

 05-06-2005
Hi Kent,
Thanks for that. But We are considering [..., 0, 101, 0, 0, 0, 0, 0] ->
[13,18] .In fact if you look at the list, the histogram ends at 15 that
is [0,101,0] --> [13,15]. Dont you think so.

Kent Johnson
Guest
Posts: n/a

 05-06-2005
wrote:
> Hi Kent,
> Thanks for that. But We are considering [..., 0, 101, 0, 0, 0, 0, 0] ->
> [13,18] .In fact if you look at the list, the histogram ends at 15 that
> is [0,101,0] --> [13,15]. Dont you think so.
>

Well you consider ..., 0, 4, 9, 2, 0, 0, ... as an interval [2, 7] in your example. How is
that different from ..., 0, 101, 0, 0, 0, 0, 0 ?

Kent