优化傅里叶变换信号长度

我最近偶然发现了一个互相矛盾的问题，当计算一个信号的傅里叶变换与np.fft.fft。再现的问题是：优化傅里叶变换信号长度

%timeit np.fft.fft(np.random.rand(59601))  
1 loops, best of 3: 1.34 s per loop

我发现时间量意外地长。例如让我们来看看其他一些FFT的，但有一个稍微长/短的信号：

%timeit np.fft.fft(np.random.rand(59600)) 
100 loops, best of 3: 6.18 ms per loop 

%timeit np.fft.fft(np.random.rand(59602)) 
10 loops, best of 3: 61.3 ms per loop 

%timeit np.fft.fft(np.random.rand(59603)) 
10 loops, best of 3: 113 ms per loop 

%timeit np.fft.fft(np.random.rand(59604)) 
1 loops, best of 3: 182 ms per loop 

%timeit np.fft.fft(np.random.rand(59605)) 
100 loops, best of 3: 6.53 ms per loop 

%timeit np.fft.fft(np.random.rand(59606)) 
1 loops, best of 3: 2.17 s per loop 

%timeit np.fft.fft(np.random.rand(59607)) 
100 loops, best of 3: 8.14 ms per loop

我们可以观察到，现在时代以毫秒为单位，除了np.random.rand(59606)，持续2.17秒。

笔记，所述numpy的文档状态：

FFT（快速傅立叶变换）是指一种方法离散傅里叶变换（DFT）可以有效地计算出，通过使用所计算出的术语对称。当n是2的幂时，对称性最高，因此变换对于这些尺寸是最有效的。

然而，这些向量不具有2的幂的长度。有人可以解释如何避免/预测的情况下，当计算时间相当高？

来源

2016-01-22 blaz

59601是3 * 19867，和19867是素数。请参阅http://stackoverflow.com/questions/21161033/strange-numpy-fft-performance –

另外，59606是2 * 29803，而29803是总理。对于一个非常缓慢的情况，请尝试59611，这是主要的。 –

是的，就是这样。谢谢！ – blaz

正如一些评论指出的那样，素数因子分解允许您预测计算FFT的时间。以下图表显示您的结果。备注对数刻度！

该图像被用下面的代码生成：

import numpy as np 
import matplotlib.pyplot as plt 

def prime_factors(n): 
    """Returns all the prime factors of a positive integer""" 
    #from http://stackoverflow.com/questions/23287/largest-prime-factor-of-a-number/412942#412942 
    factors = [] 
    d = 2 
    while n > 1: 
     while n % d == 0: 
      factors.append(d) 
      n /= d 
     d = d + 1 

    return factors 


times = [] 
decomp = [] 
for i in range(59600, 59613): 
    print(i) 
    t= %timeit -o np.fft.fft(np.random.rand(i)) 
    times.append(t.best) 
    decomp.append(max(prime_factors(i))) 

plt.loglog(decomp, times, 'o') 
plt.ylabel("best time") 
plt.xlabel("largest prime in prime factor decomposition") 
plt.title("FFT timings")

来源

2016-01-22 15:13:41

优化傅里叶变换信号长度

回答

相关问题