优化傅里叶变换后的信号长度

Question

我最近在用 np.fft.fft 计算信号的傅里叶变换时偶然发现了一个有趣的问题。复现的问题是：

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

我发现时间量出乎意料的长。例如，让我们看看其他一些 fft，但带有轻微的 longer/shorter 信号：

%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 的幂。有人可以解释如何 avoid/predict 计算时间相当长的情况吗？

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 
    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")

优化傅里叶变换后的信号长度

Optimizing Fourier transformed signal length

python

numpy

fft

scipy