Эффективно обнаруживать изменения знака в python

Question

Я хочу сделать именно то, что сделал этот парень:

Python - изменение количества знаков

Однако мне нужно оптимизировать его, чтобы он работал очень быстро. Вкратце я хочу взять временной ряд и сказать, что каждый раз, когда он пересекает, пересекает ноль (меняет знак). Я хочу записать время между переходами через ноль. Поскольку это реальные данные (32-разрядные числа с плавающей запятой), я сомневаюсь, что каждый из них будет иметь число, которое точно равно нулю, так что это не важно. В настоящее время у меня есть программа отсчета времени, поэтому я рассчитываю ваши результаты, чтобы узнать, кто победит.

Мое решение дает (микросекунды):

open data       8384
sign data       8123
zcd data        415466

Как видите, детектор пересечения нуля является медленной частью. Вот мой код.

import numpy, datetime

class timer():
    def __init__(self):
        self.t0 = datetime.datetime.now()
        self.t = datetime.datetime.now()
    def __call__(self,text='unknown'):
        print text,'\t',(datetime.datetime.now()-self.t).microseconds
        self.t=datetime.datetime.now()

def zcd(data,t):
    sign_array=numpy.sign(data)
    t('sign data')
    out=[]
    current = sign_array[0]
    count=0
    for i in sign_array[1:]:
        if i!=current:
            out.append(count)
            current=i
            count=0
        else: count+=1
    t('zcd data')
    return out

def main():
    t = timer()
    data = numpy.fromfile('deci.dat',dtype=numpy.float32)
    t('open data')
    zcd(data,t)

if __name__=='__main__':
    main()

Answer 1

А как насчет:

import numpy
a = [1, 2, 1, 1, -3, -4, 7, 8, 9, 10, -2, 1, -3, 5, 6, 7, -10]
zero_crossings = numpy.where(numpy.diff(numpy.sign(a)))[0]

Вывод:

> zero_crossings
array([ 3,  5,  9, 10, 11, 12, 15])

т.е. ноль_крестов будет содержать индексы элементов после , когда происходит пересечение нуля.Если вы хотите, чтобы элементы были до , просто добавьте 1 к этому массиву.

Answer 2

Как отметил Джей Борсет, принятый ответ не обрабатывает массивы, содержащие 0 правильно.

Я предлагаю использовать:

import numpy as np
a = np.array([-2, -1, 0, 1, 2])
zero_crossings = np.where(np.diff(np.signbit(a)))[0]
print(zero_crossings)
# output: [1]

Поскольку a) использование numpy.signbit () немного быстрее, чем numpy.sign (), так как его реализация проще, я думаю, и b) он правильно работает с нулями во входном массиве.

Однако есть один недостаток, может быть: если ваш входной массив начинается и заканчивается нулями, он найдет пересечение нуля в начале, но не в конце ...

import numpy as np
a = np.array([0, -2, -1, 0, 1, 2, 0])
zero_crossings = np.where(np.diff(np.signbit(a)))[0]
print(zero_crossings)
# output: [0 2]

Answer 3

Еще один способ подсчета пересечения нуля и выжать из кода всего несколько миллисекунд - это использовать nonzero и вычислять знаки напрямую. Предполагая, что у вас есть одномерный массив data:

def crossings_nonzero_all(data):
    pos = data > 0
    npos = ~pos
    return ((pos[:-1] & npos[1:]) | (npos[:-1] & pos[1:])).nonzero()[0]

В качестве альтернативы, если вы просто хотите посчитать пересечения нуля для определенного направления пересечения нуля (например, от положительного к отрицательному), это еще быстрее:

def crossings_nonzero_pos2neg(data):
    pos = data > 0
    return (pos[:-1] & ~pos[1:]).nonzero()[0]

На моей машине это немного быстрее, чем метод where(diff(sign)) (время для массива из 10000 выборок синусов, содержащих 20 циклов, всего 40 пересечений):

$ python -mtimeit 'crossings_where(data)'
10000 loops, best of 3: 119 usec per loop

$ python -mtimeit 'crossings_nonzero_all(data)'
10000 loops, best of 3: 61.7 usec per loop

$ python -mtimeit 'crossings_nonzero_pos2neg(data)'
10000 loops, best of 3: 55.5 usec per loop

Answer 4

Ответ Джима Бриссома терпит неудачу, если a содержит значение 0:

import numpy  
a2 = [1, 2, 1, 1, 0, -3, -4, 7, 8, 9, 10, -2, 1, -3, 5, 6, 7, -10]  
zero_crossings2 = numpy.where(numpy.diff(numpy.sign(a2)))[0]  
print zero_crossings2  
print len(zero_crossings2)  # should be 7

Выход:

[ 3  4  6 10 11 12 13 16]  
8  

Число пересечений нуля должно быть 7, но поскольку sign () возвращает 0, если передано 0, 1 для положительных значений и -1 для отрицательных значений, diff () будет считать переход, содержащий ноль, дважды.

Альтернативой может быть:

a3 = [1, 2, 1, 1, 0, -3, -4, 7, 8, 9, 10, 0, -2, 0, 0, 1, 0, -3, 0, 5, 6, 7, -10]  
s3= numpy.sign(a3)  
s3[s3==0] = -1     # replace zeros with -1  
zero_crossings3 = numpy.where(numpy.diff(s3))[0]  
print s3  
print zero_crossings3  
print len(zero_crossings3)   # should be 7

, которые дают правильный ответ:

[ 3  6 10 14 15 18 21]
7

Answer 5

Вы хотите рассчитать это?Или вы хотите сделать это как можно быстрее?

Время легко.Запустите его миллион раз, остановите секундомер и разделите на миллион.

Чтобы сделать это как можно быстрее, вам нужно выяснить, что занимает время и что вы могли бы сделать лучше.Я использую либо 1) технику случайной паузы, либо 2) одношаговую технику.

Answer 6

Я вижу, что люди часто используют diff в своих решениях, но xor, кажется, намного быстрее, и результат тот же для bools (хорошим указанием на это может быть также тот факт, что использование diff выдает устаревшее предупреждение ...) . :)) Вот пример:

positive = a2 > 0
np.where(np.bitwise_xor(positive[1:], positive[:-1]))[0]

Раз он измеряет, чтобы он был примерно в полтора раза быстрее, чем для меня:)

Если вас не интересуют крайние случаи, лучше использовать

positive = np.signbit(a2)

но положительный = a2> 0 кажется быстрее (и чище), чем signbit И проверка на 0s (например, Positive = np.bitwise_or (np.signbit (a2), np.logical_not (a2)) медленнее ...)

Answer 7

Другим способом, который может подойти некоторым приложениям, является расширение оценки выражения np.diff(np.sign(a)).

Если мы сравним, как это выражение реагирует на определенные случаи:

1. Восходящее пересечение без нуля: np.diff(np.sign([-10, 10])) возврат array([2])
2. Восходящее пересечение с нулем: np.diff(np.sign([-10, 0, 10])) возвращает array([1, 1])
3. Падающий переход без нуля: np.diff(np.sign([10, -10])) возврат array([-2])
4. Падающий переход с нуля: np.diff(np.sign([10, 0, -10])) возвращает array([-1, -1])

Таким образом, мы должны оценить np.diff(...) для возвращенных шаблонов в 1. и 2:

sdiff = np.diff(np.sign(a))
rising_1 = (sdiff == 2)
rising_2 = (sdiff[:-1] == 1) & (sdiff[1:] == 1)
rising_all = rising_1
rising_all[1:] = rising_all[1:] | rising_2

и для случаев 3. и 4.:

falling_1 = (sdiff == -2) #the signs need to be the opposite
falling_2 = (sdiff[:-1] == -1) & (sdiff[1:] == -1)
falling_all = falling_1
falling_all[1:] = falling_all[1:] | falling_2

После этого мы можем легко найти индексы с помощью

indices_rising = np.where(rising_all)[0]
indices_falling = np.where(falling_all)[0]
indices_both = np.where(rising_all | falling_all)[0]

Этот подход должен быть достаточно быстрым, поскольку он может обходиться без использования "медленного" цикла.

Это объединяет подход нескольких других ответов.