奇特的numpy fft性能

在测试过程中我注意到了一些奇怪的东西。奇特的numpy fft性能

我对很多矢量进行了FFT处理，并且时不时的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>

来源

2014-01-16 Svend Feldt

根据len（a）的因式分解，使用了许多不同的算法。正如你所知道的，2的能力是最快的，所以如果你能垫上这是最好的路线。 http://en.wikipedia.org/wiki/Fast_Fourier_transform#Cooley.E2.80.93Tukey_algorithm有更多的信息。 – marshall

分而治之FFT算法，如Cooley-Tukey，运行得更好的多个因素输入长度了。 2的幂效果特别好，而素数（如165037）需要交替，较慢的实现。如果你可以将你的输入填充到2的幂的长度，那么你可能会大大加快FFT的速度。

来源

2014-01-16 11:57:52 user2357112

我知道2的幂对FFts很好，也许我可以理解，素数也是缓慢的，但是例如480057也是缓慢的 - 它不是素数？ –

我会接受你的答案，因为它是一种愚蠢的165037点FFT，最后你可能是对的。我会做一些重叠，并加上并坚持2的权力。 –

虽然你的解释是现货，但我不认为这个陈述“素数要求交替，较慢的实现”是真实的。 FFT所做的是将大小为“N = P * Q”的DFT划分为大小为“Q”的“P”个DFT和大小为“P”的“Q”个修改后的DFT。这是递归地重复直到找到一个素数大小的DFT，然后直接计算。不管最终发现的素数大小的DFT的大小是2（输入是2的幂），3,5或165037，执行可能是相同的。 – Jaime

我认为，功率2阵列的填充有时有几个缺点：

如果你砍阵列功率2长度会产生一个很大的丢失数据的大阵列
如果你垫它会产生所谓的“边缘效应”

我在这topic中发现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)))

来源

2015-11-11 20:28:16

奇特的numpy fft性能

回答

相关问题