優化傅里葉變換信號長度

我最近偶然發現了一個互相矛盾的問題，當計算一個信號的傅里葉變換與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

優化傅里葉變換信號長度

回答

相關問題