奇怪的Numpy FFT性能 [英] strange numpy fft performance

问题描述

在测试期间，我发现了一些奇怪的东西.

During testing I have noticed something strange.

我正在对很多向量进行FFT，并且numpy FFT函数有时会崩溃.

I’m FFT’ing a lot of vectors, and from time to time the numpy FFT function seemed to crash.

我对此进行了短暂调试，发现某些向量长度触发了此行为.

I briefly debugged this, and found that some vector lengths triggered the behavior.

偶然地，我保持了脚本的运行，但令我惊讶的是，它没有崩溃，只是花了一点时间.

By incident, I kept a script running, and to my surprise, it was not crashed, it simply took a little longer.

是否有人知道发生了什么以及如何应对.我已经在许多不同的FFT大小中看到了这一点，以下仅是示例.

Does anyone have an idea of what is going on, and how to counter act this. I have seen this with many different FFT sizes, the below is an example only.

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>

推荐答案

分而治之FFT算法，例如

Divide-and-conquer FFT algorithms, such as Cooley-Tukey, work much better the more factors the input length has. Powers of 2 work especially well, whereas primes (like 165037) require alternate, slower implementations. If you can pad your input to a power-of-2 length, you may be able to drastically speed up slow FFTs.

这篇关于奇怪的Numpy FFT性能的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！