python - 优化傅立叶变换信号长度

Question

我最近在使用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 (Fast Fourier Transform) refers to a way the discrete Fourier Transform (DFT) can be calculated efficiently, by using symmetries in the calculated terms. The symmetry is highest when n is a power of 2, and the transform is therefore most efficient for these sizes.

但是这些向量的长度不等于 2 的幂。有人可以解释一下当计算时间相当长时如何避免/预测情况吗？

Answer 1

正如一些评论所指出的，素因子分解允许您预测计算 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")