CODEWITHSUNDEEP
pythonalgorithm
Simd
Simd

Reputation: 21343

Convert recursive peak finding to iterative

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.

Upvotes: 0

Views: 619

Answers (1)

Alexandre B.
Alexandre B.

Reputation: 5500

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 !

Upvotes: 3

Related Questions