在python中查找数组的转折点

Question

例如，如果我有一个数组：

A = (0,2,3,4,5,2,1,2,3,4,5,6,7,8,7,6,5,4,5,6)

可以看出有4个转折点。（在A[4]、A[6]、A[13]、A[17]）

如何使用python返回转折点的数目？

import numpy as np
import scipy.integrate as SP
import math

def turningpoints(A):
    print A
    N = 0
    delta = 0
    delta_prev = 0
    for i in range(1,19):
        delta = A[i-1]-A[i]       #Change between elements
        if delta < delta_prev:    #if change has gotten smaller
            N = N+1               #number of turning points increases
        delta_prev = delta        #set the change as the previous change
    return N

if __name__ == "__main__":
    A  = np.array([0,2,3,4,5,2,1,2,3,4,5,6,7,8,7,6,5,4,5,6])
    print turningpoints(A)

目前，这个系统有缺陷，当然不是很优雅。有什么想法吗？

Answer 1

如果你有numpy：

def turningpoints(lst):
    dx = np.diff(lst)
    return np.sum(dx[1:] * dx[:-1] < 0)

或非numpy等效版本：

def turningpoints(lst):
    dx = [x - y for x, y in zip(lst[1:], lst[:-1])]
    return sum(dx1 * dx2 < 0 for dx1, dx2 in zip(dx[1:], dx[:-1]))

只为一句俏皮话：

def turningpoints(lst):
    return sum(x0*x1 + x1*x2 < x1*x1 + x0*x2 for x0, x1, x2 in zip(lst[2:], lst[1:-1], lst[:-2]))

但这本书的可读性可能会降低：）

Answer 2

我知道这是个老问题，但我也遇到了同样的问题，正如Cardin在Malvolio's answer的注释中所说，答案不能处理具有相同值的连续点，如[1, 2, 3, 4, 4, 4, 3, 2, 1]。我的实现可以处理这个问题。

尽管如此，它返回两个列表，其中包含最小和最大转折点的索引。

def turning_points(array):
    ''' turning_points(array) -> min_indices, max_indices
    Finds the turning points within an 1D array and returns the indices of the minimum and 
    maximum turning points in two separate lists.
    '''
    idx_max, idx_min = [], []
    if (len(array) < 3): 
        return idx_min, idx_max

    NEUTRAL, RISING, FALLING = range(3)
    def get_state(a, b):
        if a < b: return RISING
        if a > b: return FALLING
        return NEUTRAL

    ps = get_state(array[0], array[1])
    begin = 1
    for i in range(2, len(array)):
        s = get_state(array[i - 1], array[i])
        if s != NEUTRAL:
            if ps != NEUTRAL and ps != s:
                if s == FALLING: 
                    idx_max.append((begin + i - 1) // 2)
                else:
                    idx_min.append((begin + i - 1) // 2)
            begin = i
            ps = s
    return idx_min, idx_max

为了正确回答问题，转折点的数量计算如下：

sum(len(x) for x in turning_points(X))

示例

Answer 3

你想得太多了。一个“转折点”要么高于两边的点，要么低于两边的点。

def turningpoints(x):
  N=0
  for i in range(1, len(x)-1):
     if ((x[i-1] < x[i] and x[i+1] < x[i]) 
         or (x[i-1] > x[i] and x[i+1] > x[i])):
       N += 1
  return N

>>> turningpoints([0,2,3,4,5,2,1,2,3,4,5,6,7,8,7,6,5,4,5,6])
4