4
\$\begingroup\$

I am looking for a function, that will find in array of n integers highest or equal locally values including corners.

My code is probably wrong, and I somehow think solution is in some library like NumPy or SciPy, but I do not know how to find it:

def look_for_maximas(vals):
    '''
    actually look for hills, 1, 0, 1, 1, 0, 1, 1, 2, 1, 0, 0 should return indexes 0, 2, 3, 7
    :param vals:
    :return:
    '''
    if len(vals) == 0:
        return []
    res = []
    buff = [0]
    is_candidate = True
    i = 1
    while i < len(vals):
        if vals[i] > vals[i-1]:
            is_candidate = True
            buff = [i]
        elif vals[i] == vals[i-1] and is_candidate:
            buff.append(i)
        else:
            if is_candidate:
                res += buff
            is_candidate = False
            buff = []
        i += 1
    if is_candidate:
        res += buff

    return res

I have some tests to test it:

assert look_for_maximas([1, 0, 1, 1, 0, 1, 1, 2, 1, 0, 0]) == [0, 2, 3, 7]
assert look_for_maximas([0]) == [0]
assert look_for_maximas([0, 1, 0]) == [1]
assert look_for_maximas([]) == []
assert look_for_maximas([0, 0, 0, 0]) == [0, 1, 2, 3]
assert look_for_maximas([i for i in repeat(0, 1000)]) == range(0, 1000)
assert look_for_maximas(
    [100, 0, 0, 100, 10, 0, 10, 10, 0, 5, 3, 0, 0, 10, 10, 10, 10, 100, 0, 1]) == [0, 3, 6, 7, 9, 17, 19]

And it passes it, but it is probably not the best code and I am probably inventing wheel one more time.

\$\endgroup\$
2
  • \$\begingroup\$ Can you describe your algorithm in a sentence or so? Particularly, what counts as 'local'? I suspect that this could be done easier using a rolling window which pandas gives directly, or there's this numpy recipe. \$\endgroup\$
    – lvc
    Jul 30, 2015 at 12:52
  • \$\begingroup\$ I've always been a fan of the public-domain peakdet algorithm for cases like these. It's in Github. I'm not sure it will return every index for a "flat" maximum, but you can probably adapt it to that case. \$\endgroup\$
    – Curt F.
    Jul 30, 2015 at 17:49

4 Answers 4

4
\$\begingroup\$

First off you can change the while loop to a for loop.

for i in range(1, len(vals)):

This makes the program easier to understand. As then there is no i += 1.


It is also un-pythonic to do:

if len(vals) == 0:

Instead do:

if not vals:

As you want it to work with edge cases, what about generators? And other objects that are iterable, but not index-able.

I would change the if not vals: to a try except.

vals = iter(vals)
try:
    prev = next(vals)
except StopIteration:
    return []

And then you can change the for loop to use enumerate.

for i, curr in enumerate(vals, 1):
    if curr > prev:
        is_candidate = True
        buff = [i]
    elif curr == prev and is_candidate:
        buff.append(i)
    else:
        if is_candidate:
            res += buff
        is_candidate = False
        buff = []
    prev = curr

now it will work with anything that is iterable. And so it will work with generators.


Both yield and list.append are \$O(1)\$. However I like to think that list.append is \$O(n)\$. This is as lists rely on the amortized worst case to be \$O(1)\$.

From the Python time complexity page.

Internally, a list is represented as an array; the largest costs come from growing beyond the current allocation size (because everything must move)

So using range, assuming you're using Python3, and generators can be better.

def look_for_maximas(vals): 
    def res(vals):
        vals = iter(vals)
        # Exploiting for-loops and generators. It's kinda surprising this works.
        prev = next(vals)

        start = 0
        # Has to be in scope for the last yield.
        i = 1
        for curr in vals:
            if curr > prev:
                start = i
            elif curr < prev:
                if start is not None:
                    yield range(start, i)
                start = None
            prev = curr
            i += 1

        if start is not None:
            yield range(start, i)

    for range_ in res(vals):
        for i in range_:
            yield i

It is not as fast as a NumPy or SciPi solution, but can be a lot faster than using lists.

I tested this by doing assert list(look_for_maximas(...)) == .... And it worked for them all. However I don't have repeat, and removed that test.

\$\endgroup\$
2
\$\begingroup\$

Your problem essentially boils down to repeatedly finding the (global) maximum of some (local) values. Python for "the maximum of some values" is max(some_values), and Python for "do this iteratively on this sequence of things" is a for loop (or, in this case, a list comprehension).

You want the indexes of maxima, rather than the values, but max takes a key argument so you can do:

>>> vals = [3,5,2]
>>> max((0,1,2), key=vals.__getitem__)
1

This means that if you can work out how to generate the indices of potential locally-interesting values, you can structure your program like this:

def _local_windows(vals):
    ...

def local_maxima(vals):
    return [max(_local_windows(vals), key=vals.__getitem__]

So now we need to tell Python what "local" means. Unfortunately, I can't come up with any definition that matches all of your test cases. But hopefully, if I show you a couple of things you can do that don't quite match your code, you can glean enough to fill in the blanks.

The first thing I thought of was a strict rolling window - "every three adjacent items" (except dealing with the two edge cases):

def _local_windows(vals):
    indices = range(len(vals))
    yield (0, 1)
    yield from zip(indices, indices[1:], indices[2:])
    yield (indices[-2], indices[-1])

But that gets a lot of spurious "maxima" in flat sections. So, I thought, let's coalesce equal values into their left-most index when looking at them from the right, or their left-most when looking at them from the left. groupby from itertools is good for that:

def _local_windows(vals):
    groups = it.groupby(range(len(vals)), vals.__getitem__)
    groups = collections.OrderedDict((k, list(g)) for k, g in groups)

    keys = list(groups.keys())
    yield keys[0], keys[1]
    for l,m,r in zip(keys, keys[1:], keys[2:]):
        # the key is the left-most index of the
        # coalesced values. We want the *right* most
        # index for left-hand group
        yield (l+len(groups[l]), m, r)

    k = keys[-2]
    yield k+len(groups[k]), keys[-1]

This will noticeably fail tests like [0,0,0,0] - this definition of local will return [0], while you want [0, 1, 2, 3].

But if you can come up with a succinct, Pythonic definition of 'local', this might be an approach to consider.

\$\endgroup\$
1
\$\begingroup\$

I would use a stack (a.k.a list) to keep track of the values as they rise, fall, or stay the same.

def look_for_maxima(values):
    stack = []
    answer = []
    for ind in range(len(values)):
        if stack == []:
            stack.append(ind)
        elif values[ind] > values[stack[-1]]:
            stack.clear()
            stack.append(ind)
        elif values[ind] == values[stack[-1]]:
            stack.append(ind)
        elif values[ind] < values[stack[-1]]:
            answer = answer + stack
            stack.clear()
        if answer == [] or (values[stack[-1]] <= values[answer[-1]]):
            # There still might be some values on the stack yet to be popped
            answer += stack
    return answer
\$\endgroup\$
2
  • \$\begingroup\$ You have presented an alternative solution, but haven't reviewed the code. Please explain your reasoning (how your solution works and how it improves upon the original) so that the author can learn from your thought process. \$\endgroup\$
    – Quill
    Jul 30, 2015 at 12:01
  • \$\begingroup\$ Quill, its actually broken, it cannot handle multiple descending values, as the stack is cleared, and they are treated as new maxima :( \$\endgroup\$ Jul 30, 2015 at 12:12
1
\$\begingroup\$

I took another approach, using triplets:

numbers = [1, 0, 1, 1, 0, 1, 1, 2, 1, 0, 0]

    triplets = [
        (numbers[x], numbers[x+1], numbers[x+2])
        for x in range(len(numbers)-2)
        ]

    current_max = min(numbers)
    results = []
    for idx, values in enumerate(triplets):
        cond1 = values[0] >= current_max
        cond2 = values[0] >= values[1]
        cond3 = values[2] <= values[0]

        if cond1 and cond2 and cond3:
            results.append(idx)
            current_max = values[0]

Results: [0, 2, 3, 7]

Triplets: [(1, 0, 1), (0, 1, 1), (1, 1, 0), (1, 0, 1), (0, 1, 1), (1, 1, 2), (1, 2, 1), (2, 1, 0), (1, 0, 0)]

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.