时间戳

首页 > 解决方案 > 将递归峰值查找转换为迭代

python - 将递归峰值查找转换为迭代

问题描述

数组中的峰值是不小于其两个相邻邻居的任何值。如果它是数组的第一个或最后一个元素，我们只需要与一个邻居进行比较。我编写了一些递归代码来查找 python 中的峰值，这在原则上是快速的，因为它在 O(log n) 时间内运行：

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:])

但是，python 不是很擅长递归，所以我认为迭代会更好。如何将其转换为迭代代码？

更新

事实证明，这段代码非常慢，因为 A[n//2+1:] 和 A[0:n//2] 会复制列表。

标签： pythonalgorithm

解决方案

一个简单的解决方案是遍历列表并比较前一个值和下一个值。您还需要考虑第一个元素和最后一个元素的情况：

# 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]

同样，您可以通过替换out.append(curr)为out.append(i)or轻松获取索引而不是值（或两者） out.append([curr, i])。

更新：

如果只想得到一个峰，可以在找到一个元素满足条件后退出函数。以下返回第一个值：

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

更新 2：

递归函数到迭代函数的转换可能如下所示：

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

谁的速度更快？

递归方法比迭代方法快一点：

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

希望有帮助！

推荐阅读