Странная производительность

Во время тестирования я заметил что-то странное.

Im FFTing много векторов, и время от времени функция numping FFT, казалось, сбой.

Я кратко отладил это и обнаружил, что некоторые длины векторов вызвали поведение.

В результате инцидента я продолжал работать script, и, к моему удивлению, он не разбился, он просто занял немного больше времени.

Кто-нибудь имеет представление о том, что происходит, и как противодействовать этому. Я видел это со многими различными размерами FFT, ниже приведен пример.

import numpy as np    
import time

a = np.zeros(166400)
start = time.time()
audio_fft = np.fft.fft(a,len(a))                          
print "it took %fs"%(time.time() -start)

a = np.zeros(165039)
start = time.time()
audio_fft = np.fft.fft(a,len(a))                          
print "it took %fs"%(time.time() -start)

a = np.zeros(165038)
start = time.time()
audio_fft = np.fft.fft(a,len(a))                          
print "it took %fs"%(time.time() -start)

a = np.zeros(165036)
start = time.time()
audio_fft = np.fft.fft(a,len(a))                          
print "it took %fs"%(time.time() -start)

a = np.zeros(165035)
start = time.time()
audio_fft = np.fft.fft(a,len(a))                          
print "it took %fs"%(time.time() -start)

a = np.zeros(165034)
start = time.time()
audio_fft = np.fft.fft(a,len(a))                          
print "it took %fs"%(time.time() -start)

a = np.zeros(165037)
start = time.time()
audio_fft = np.fft.fft(a,len(a))                          
print "it took %fs"%(time.time() -start)

print "done"

Выводится:

c:\Users\sol_sf\Desktop\math>fftTest.py
it took 0.029000s
it took 0.101000s
it took 0.176000s
it took 0.220000s
it took 0.671000s
it took 0.065000s
it took 369.132000s
done

c:\Users\sol_sf\Desktop\math>

Ответ 1

Разделяйте и управляйте алгоритмами FFT, такими как Cooley-Tukey, работают намного лучше, чем больше факторов, чем длина входных данных. Силы 2 работают особенно хорошо, тогда как простые числа (например, 165037) требуют альтернативных, более медленных реализаций. Если вы можете вставить свой вход в длину с длиной-2, вы можете значительно ускорить медленные БПФ.

Ответ 2

Я думаю, что power 2 padding массива несколько раз имеет несколько недостатков:

Если вы сокращаете массив до мощности 2, это приведет к большим потерям данных для больших массивов.
Если вы нажмете массив с нулями, он произведет так называемый "эффект края"

Я нашел в этом тему, что fft-производительность зависит от основной факторизации массива. Если длина массива является простым числом, это приводит к длительному времени вычисления. Поэтому я предлагаю следующий код, который уменьшает длину массива, ища лучшую факторизацию.

from sympy.ntheory import factorint

FACTOR_LIMIT = 100

def bestFFTlength(n):
    while max(factorint(n)) >= FACTOR_LIMIT:
        n -= 1
    return n

a = np.zeros(166400)
audio_fft = np.fft.fft(a,bestFFTlength(len(a)))

Ответ 3

Простой способ решить эту проблему - что не упоминается в других ответах - это использовать scipy.fftpack.next_fast_len для заполнения массива. Учитывая заданную длину, она дает вам следующую длину> target, которая является составной из 2, 3 и 5.

Как указывали другие ответы, FFT работает хуже всего, когда длина массива - простое число. Его эффективность увеличивается с увеличением числа основных факторов (2, 3, 5 и т.д.).