By using this site, you agree to our updated Privacy Policy and our Terms of Use. Manage your Cookies Settings.
425,805 Members | 1,100 Online
Bytes IT Community
+ Ask a Question
Need help? Post your question and get tips & solutions from a community of 425,805 IT Pros & Developers. It's quick & easy.

min max of a list

P: n/a
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.

Jul 19 '05 #1
Share this Question
Share on Google+
13 Replies


P: n/a
qu*****@gmail.com 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
Jul 19 '05 #2

P: n/a
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

Jul 19 '05 #3

P: n/a
qu*****@gmail.com 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
Jul 19 '05 #4

P: n/a
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.

Jul 19 '05 #5

P: n/a
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.

Jul 19 '05 #6

P: n/a
qu*****@gmail.com 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
Jul 19 '05 #7

P: n/a
qu*****@gmail.com 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
Jul 19 '05 #8

P: n/a
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.

Jul 19 '05 #9

P: n/a
qu*****@gmail.com 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
Jul 19 '05 #10

P: n/a
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]

Jul 19 '05 #11

P: n/a
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.

Jul 19 '05 #12

P: n/a
qu*****@gmail.com wrote:
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
Jul 19 '05 #13

P: n/a
Peter Hansen wrote:
qu*****@gmail.com wrote:
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
Jul 19 '05 #14

This discussion thread is closed

Replies have been disabled for this discussion.