Convert recursive peak finding to iterative

Question

A peak in an array is any value that is no smaller than its two adjacent neighbors. If its the first or last element of the array we only need to compare with one neighbor. I wrote some recursive code to find peaks in python which is fast in principle as it runs in O(log n) time:

def peak_recursive(A):
    n = len(A)
    if n == 1:
        print("n == 1")
        return 0
    if n == 2:
        return 0 if A[0] >= A[1] else 1
    if A[n//2] >= A[n//2+1] and A[n//2] >= A[n//2 - 1]:
        return n//2
    elif A[n//2 - 1] >= A[n//2]:
        return peak_recursive(A[0:n//2])
    else:
        return n//2 + 1 + peak_recursive(A[n//2+1:])

However, python isn't very good at recursion so I think it would be better iteratively. How can I convert this to iterative code?

Update

It turns out this code is very slow as A[n//2+1:] and A[0:n//2] make copies of the lists.

The solution is very similar to the iterative version of binary search. Try going in that direction. — Ajmal, Aug 13 '19 at 15:31
Take a look here: https://stackoverflow.com/questions/41883258/how-to-implement-a-binary-search — Sparky05, Aug 13 '19 at 15:31
If you want ready to use function, you can use [`scipy.signal.find_peaks`](https://docs.scipy.org/doc/scipy/reference/generated/scipy.signal.find_peaks.html) — Alexandre B., Aug 13 '19 at 15:52
@AlexandreB. Thank you but I am looking for an implementation that find just one peak in pure python. — Simd, Aug 13 '19 at 15:53
You cannot use binary search in this case. The data is random, not sorted. The best time complexity you can do is O(n). — Andrej Kesely, Aug 13 '19 at 17:40
@AndrejKesely That can't be true. My code runs in O(log n ) time. — Simd, Aug 13 '19 at 17:41
It runs O(log n) but it won't give you always correct answer — Andrej Kesely, Aug 13 '19 at 17:42
@AndrejKesely can you give an example where it gives the wrong answer? — Simd, Aug 13 '19 at 17:44
Did you test this? `a = [1,2,1,1,1,1]` -> `3` and `a = [1,1,1,1,2,1]` -> `1`. Are these the expected values? — PaulMcG, Aug 13 '19 at 17:44
@PaulMcG Yes a[3] is a peak in the first case as is a[1] in the second. — Simd, Aug 13 '19 at 17:46
I guess this is a definition of "peak" I am unfamiliar with. — PaulMcG, Aug 13 '19 at 17:47
@PaulMcG "A peak in an array is any value that is no smaller than its two adjacent neighbors." That's the definition I am using. — Simd, Aug 13 '19 at 17:47

score 3 · Accepted Answer · edited Jun 20 '20 at 09:12

One simple solution is to iterate over the list and compare the previous and next values. You also need to consider the first element and last element situation:

# Import numpy to create random vector
import numpy as np

l = np.random.randint(0, 10, 20).tolist()
print(l)
# [6, 7, 2, 7, 1, 4, 2, 8, 9, 1, 3, 7, 0, 5, 4, 6, 9, 0, 5, 7]

def peak_iter(A):
    out = []                            # Output
    n = len(A)                          # Number element A
    for i, curr in enumerate(A):        # Iterate over A
        condi = True                    # Peak condition
        if i > 0: condi = A[i-1] < curr         # Update peak condition from previous value
        if i < n - 1: condi = curr > A[i + 1]   # Update peak condition from next value
        if condi: out.append(curr)     # If condition satisfied: add value to output
    return out

print(peak_iter(l))
# [7, 7, 4, 9, 7, 5, 9, 7]

As well, you can easily get the index instead of the value (or the both) by replacing out.append(curr) with out.append(i) or out.append([curr, i]).

Update:

If you just want to get the one peak, you can exit the function after finding one element meeting condition. The following returns the first values:

def peak_iter_first(A):
    out = None                          # Output
    n = len(A)                          # Number element A
    for i, curr in enumerate(A):        # Iterate over A
        condi = True                    # Peak condition
        if i > 0: condi = A[i-1] < curr         # Update peak condition from previous value
        if i < n - 1: condi = curr > A[i + 1]   # Update peak condition from next value
        if condi: return curr           # If condition satisfied: return value
    return out

print(peak_iter_first(l))
# 7

Update 2:

The translation of the recursive function to an iterative one might looks something like this:

def peak_iterative(A):
    n = len(A)
    out = 0
    while True:
        if n == 1:
            out += 0
            break
        if n == 2:
            out += 0 if A[0] >= A[1] else 1
            break
        if A[n//2] >= A[n//2+1] and A[n//2] >= A[n//2 - 1]:
            out += n//2
            break
        elif A[n//2 - 1] >= A[n//2]:
            A = A[0:n//2]
        else:
            out += n//2 + 1
            A = A[n//2+1:]
        n = len(A)
    return out

Who's the faster ?

The recursive one is a bit faster than the iterative method:

import timeit
import functools

# Bigger array (2000 elements)
l = np.random.randint(0, 10, 2000).tolist()

t = timeit.Timer(functools.partial(peak_recursive, l))
print (t.timeit(50))
# 3.950000000019216e-05

t = timeit.Timer(functools.partial(peak_iterative, l))
print (t.timeit(50))
# 7.049999999986234e-05

Hope that helps !

I hardly see how to get a `O(log(n))` if you need to compare all values. The algorithm you introduced only return one value. Is it what you want ? How do you select this value ? — Alexandre B., Aug 13 '19 at 16:49
Yes I only need to return one peak. It doesn't matter which one. That's what the code in the question does. — Simd, Aug 13 '19 at 17:04
In this case, just replace `if condi: out.append(curr)` by `return curr` ? — Alexandre B., Aug 13 '19 at 17:08
Your code still seems to iterate over all of A making it O(n) time. It doesn't seem to do binary search. Am I wrong? — Simd, Aug 13 '19 at 17:13
Oh no.. It turns out both your and my codes are really slow. A[n//2+1:] makes a copy :( I will ask another question instead of editing this one. — Simd, Aug 13 '19 at 19:46
This [post](https://stackoverflow.com/questions/986006/how-do-i-pass-a-variable-by-reference) might help you — Alexandre B., Aug 13 '19 at 19:49

Convert recursive peak finding to iterative

1 Answers1

Who's the faster ?