min max of a list

[querypk]

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]

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]

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]

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]

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]

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]

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]

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/Cookbook/Python/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]

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]

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

 

[querypk]

I get a syntax error in :

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]

 

[querypk]

oh yes its the same case. even [0,4,9,2,0] as a set [2,6] and may be
not [2,7]. Its not that you are wrong its jus that I was not clear.
Sorry about that.

 

[Peter Hansen]

I get a syntax error in :

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]

I think we already covered the part where you were using an older
version of Python. In this case, the missing feature is "generator
expressions" and they are inside the two min() calls.

You might want to consider upgrading...

-Peter

 

[Steven Bethard]

I get a syntax error in :

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]

I think we already covered the part where you were using an older
version of Python. In this case, the missing feature is "generator
expressions" and they are inside the two min() calls.

You might want to consider upgrading...

But if you can't, you should write this as something like:

[(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]

Note the extra brackets in the min calls.

STeVe