奇怪的numpy fft表现

Question

在测试期间,我注意到一些奇怪的事

我正在对很多向量进行FFT,并且有时会出现numpy FFT函数崩溃的情况.

我简要地调试了这一点,发现一些矢量长度触发了这种行为.

通过事件,我保持一个脚本运行,令我惊讶的是,它没有崩溃,只是花了一点时间.

有没有人知道发生了什么,以及如何反击这一点.我已经看到了许多不同的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>

Answer 1

分割和算法的FFT算法,例如Cooley-Tukey,在输入长度越多的因素下工作得越好.2的功率特别好,而素数(如165037)需要交替的,较慢的实现.如果您可以将输入填充为2的幂,则可以大幅加速慢速FFT.