Нахождение точек поворота массива в 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

Вы слишком задумываетесь об этом. «Точка поворота» - это точка, которая либо выше, чем точки с обеих сторон, либо ниже.

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 

Answer 2

>>> def turns(L): 
...  answer, delta = 0, -1 if L[1]<L[0] else 1 
...  i = 2 
...  while i < len(L): 
...    d = -1 if L[i]<L[i-1] else 1 
...    if d != delta: 
...      answer += 1 
...      delta = d 
...    i += 1 
...  return answer 
... 
>>> L = [0,2,3,4,5,2,1,2,3,4,5,6,7,8,7,6,5,4,5,6] 
>>> turns(L) 
4 

Answer 3

def group_in_threes(slicable): 
    for i in range(len(slicable)-2): 
     yield slicable[i:i+3] 

def turns(L): 
    for index, three in enumerate(group_in_threes(L)): 
     if (three[0] > three[1] < three[2]) or (three[0] <three[1]> three[2]): 
      yield index + 1 

>>> list(turns([0,2,3,4,5,2,1,2,3,4,5,6,7,8,7,6,5,4,5,6])) 
[4, 6, 13, 17] 
>>> len(_) 
4 

Answer 4

Если у вас есть 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 5

Я знаю, что это старый вопрос, но я просто была такая же проблема, и как указано 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)) 

Пример