python - 为什么在 NumPy 中填充 FFT 会使它运行得更慢？

Question

我使用 NumPy 的 fft 函数编写了一个脚本，我将我的输入数组填充到最接近的 2 的幂以获得更快的 FFT。

分析代码后，我发现 FFT 调用花费的时间最长，所以我摆弄了参数，发现如果我没有填充输入数组，FFT 运行快了好几倍。

这是一个最小的例子来说明我在说什么(我在 IPython 中运行它并使用 %timeit 魔法来计时执行)。

x     = np.arange(-4.*np.pi, 4.*np.pi, 1000)
dat1  = np.sin(x)

计时结果:

%timeit np.fft.fft(dat1)
100000 loops, best of 3: 12.3 µs per loop

%timeit np.fft.fft(dat1, n=1024)
10000 loops, best of 3: 61.5 µs per loop

将数组填充到 2 的幂会导致非常剧烈的减速。

即使我创建一个包含素数元素的数组(因此理论上 FFT 最慢)

x2    = np.arange(-4.*np.pi, 4.*np.pi, 1009)
dat2  = np.sin(x2)

运行所需的时间仍然没有太大变化!

%timeit np.fft.fft(dat2)
100000 loops, best of 3: 12.2 µs per loop

我原以为填充数组是一次性操作，然后计算 FFT 应该会更快。我错过了什么吗？

编辑: 我应该使用 np.linspace 而不是 np.arange。以下是使用 linspace

的计时结果

In [2]: import numpy as np

In [3]: x = np.linspace(-4*np.pi, 4*np.pi, 1000)

In [4]: x2 = np.linspace(-4*np.pi, 4*np.pi, 1024)

In [5]: dat1 = np.sin(x)

In [6]: dat2 = np.sin(x2)

In [7]: %timeit np.fft.fft(dat1)
10000 loops, best of 3: 55.1 µs per loop

In [8]: %timeit np.fft.fft(dat2)
10000 loops, best of 3: 49.4 µs per loop

In [9]: %timeit np.fft.fft(dat1, n=1024)
10000 loops, best of 3: 64.9 µs per loop

填充仍然会导致减速。这可能是本地的问题吗？即，由于我的 NumPy 设置中的一些怪癖，它以这种方式运行？

Answer 1

像 NumPy 的 FFT 算法对于分解成小素数乘积的数组大小来说速度很快，而不仅仅是 2 的幂。如果通过填充来增加数组大小，则计算工作量会增加。 FFT 算法的速度也严重依赖于缓存的使用。如果填充到创建效率较低的缓存的数组大小，则使用效率会降低。真正快速的 FFT 算法，如 FFTW 和 Intel MKL，实际上会生成数组大小分解的计划以获得最有效的计算。这包括启发式和实际测量。所以不，填充到最接近的 2 的幂只对入门教科书有用，在实践中不一定有用。根据经验，如果数组大小分解为一个或多个非常大的素数，您通常会受益于填充。