Python: скользящее окно переменной ширины

Question

Я пишу программу на Python, которая обрабатывает некоторые данные, созданные во время экспериментов, и ей необходимо оценить наклон данных. Я написал код, который делает это довольно хорошо, но это ужасно медленно (и я не очень терпелив). Позвольте мне объяснить, как этот код работает:

1) Она захватывает небольшой кусочек данных размером йх (начиная с 3-х точек данных)

2) Он оценивает ли разница (т.е. | у (х +) -y (x-dx) |) больше некоторого минимального значения (40x std. шума)

3) Если разница достаточно велика, она рассчитает наклон с использованием регрессии OLS. Если разница слишком мала, это увеличит йх и повторить цикл с новым йхом

4) Это продолжается для всех точек данных

[См обновленного кода далее вниз]

Для DataSize из около 100 тыс. измерений, это занимает около 40 минут, тогда как остальная часть программы (она обрабатывает больше, чем только этот бит) занимает около 10 секунд. Я уверен, что есть гораздо более эффективный способ выполнения этих операций, не могли бы вы, ребята, помочь мне?

Благодаря

EDIT:

Итак, у меня есть проблема решена с помощью только двоичного поиска, ограничивая число допустимых шагов на 200. Я благодарю всех за вход и я выбран ответ, который помог мне больше всего.

FINAL ОБНОВЛЕНО КОД:

def slope(self, data, time): 
    (wave1, wave2) = wt.dwt(data, "db3") 
    std = 2*np.std(wave2) 
    e = std/0.05 
    de = 5*std 
    N = len(data) 
    slopes = np.ones(shape=(N,)) 
    data2 = np.concatenate((-data[::-1]+2*data[0], data, -data[::-1]+2*data[N-1])) 
    time2 = np.concatenate((-time[::-1]+2*time[0], time, -time[::-1]+2*time[N-1])) 
    for n in xrange(N+1, 2*N):  
     left = N+1 
     right = 2*N 
     for i in xrange(200): 
      mid = int(0.5*(left+right)) 
      diff = np.abs(data2[n-mid+N]-data2[n+mid-N]) 
      if diff >= e: 
       if diff < e + de: 
        break 
       right = mid - 1 
       continue 
      left = mid + 1 
     leftlim = n - mid + N 
     rightlim = n + mid - N 
     y = data2[leftlim:rightlim:int(0.05*(rightlim-leftlim)+1)] 
     x = time2[leftlim:rightlim:int(0.05*(rightlim-leftlim)+1)] 
     xavg = np.average(x) 
     yavg = np.average(y) 
     xlen = len(x) 
     slopes[n-N] = (np.dot(x,y)-xavg*yavg*xlen)/(np.dot(x,x)-xavg*xavg*xlen) 
    return np.array(slopes) 

Answer 1

Ваши комментарии свидетельствуют о том, что вам нужно найти лучший метод оценки I _{к + 1} дал я _к. Никакое знание ценностей в data не поддастся наивный алгоритм:

На каждой итерации для n, оставьте i на предыдущем значении, и посмотреть, если значение abs(data[start]-data[end]) меньше e. Если это так, оставьте i по его предыдущему значению и найдите новый, увеличив его на 1, как и сейчас. Если он больше или равен, выполните двоичный поиск по i, чтобы найти соответствующее значение. Вы можете выполнить двоичный поиск вперед, но найти хороший верхний предел кандидата без знания data может оказаться сложным. Этот алгоритм не будет работать хуже вашего текущего метода оценки.

Если вы знаете, что data не вид гладких (без резких скачков, и, следовательно, гладкий участок для всех i значений) и монотонно возрастает, вы можете заменить бинарный поиск с поиском назад, уменьшая его значение на 1 вместо этого.

Answer 2

Как оптимизировать это будет зависеть от некоторых свойств ваших данных, но вот некоторые идеи:

1. Вы пробовали профилировать код? Использование одного из Python profilers может дать вам некоторую полезную информацию о том, что занимает больше всего времени. Часто часть кода, который вы только что написали, будет иметь одно из самых больших узких мест, и не всегда очевидно, какая из них она есть; профилирование позволяет вам понять это и сначала атаковать основное узкое место.

2. Знаете ли вы, что типичные значения i? Если у вас есть какая-то идея, вы можете ускорить процесс, начиная с i больше 0 (как отмечал @vhallac), или увеличивая i на большие суммы - если вы часто видите большие значения для i, увеличьте i на 2 или 3 на время; если распределение i s имеет длинный хвост, попробуйте удвоить его каждый раз; и т. д.

3. Вам нужны все данные при выполнении регрессии наименьших квадратов? Если этот вызов функции является узким местом, вы можете ускорить его, используя только некоторые данные в диапазоне. Предположим, например, что в определенной точке вам нужно, чтобы i было 200, чтобы увидеть достаточно большое (вышешумное) изменение данных. Но вам может не понадобиться все 400 баллов, чтобы получить хорошую оценку наклона - просто использование 10 или 20 точек, равномерно расположенных в диапазоне start:end, может быть достаточным и может значительно ускорить код.

Answer 3

Я работаю с Python для подобных анализов и имею несколько предложений. Я не смотрел на детали вашего кода, только к вашей постановке задачи:

1) Он захватывает небольшой кусочек данных размером йх (начиная с 3-х точек данных)

2) Это оценивает, является ли разность (т. е. | y (x + dx) -y (x-dx) |) равна больше определенного минимального значения (40x уровень шума)

3) Если разница большая достаточно, он рассчитает наклон с использованием регрессии OLS. Если разница слишком мала, это увеличит де и повторить цикл с новым йхом

4) Это продолжается для всех точек данных

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

Для шага 1 вместо того, чтобы брать пары точек, вы можете непосредственно выполнять данные [3:] - данные [-3:] и получать все различия в одной операции с массивом;

Для шага 2 вы можете использовать результат тестов на основе массива, например numpy.argwhere(data > threshold), вместо проверки каждого элемента внутри некоторого цикла;

Шаг 3 звучит концептуально неправильно для меня. Вы говорите, что если разница слишком мала, она увеличится dx. Но если разница небольшая, результирующий наклон будет мал, потому что он действительно маленький. Тогда получение небольшого значения - это правильный результат, и искусственное увеличение dx для получения «лучшего» результата может быть не таким, каким вы хотите. Ну, на самом деле это может быть то, что вы хотите, но вы должны это учитывать. Я бы предположил, что вы рассчитали наклон для фиксированного dx по всем данным, а затем возьмите результирующий массив наклонов, чтобы выбрать интересующие вас области (например, используя data_slope[numpy.argwhere(data_slope > minimum_slope)].

Надеюсь, это поможет!