numpy fft对于长度小的素数而言是快速的,但是有多小？

Question

我已经看到几个例子表明如果输入长度是2,3,5,7等的乘积,那么numpy的fft实现很快.但是这里仍然被认为是"小"的最大素数是多少？

Answer 1

请注意,scipy的FFT具有2,3,4和5(参考)的基数.我假设numpy可能有类似的实现,这将使5成为FFT长度中最大的有效素数因子.

根据经验,出于FFT性能的目的,我认为"小"的最大素数是11.但是对于实际目的而言,任何小于约30的输入长度都将非常快.Python的执行开销肯定会使任何算法性能提升都相形见绌.对于更高的输入长度,事情变得越来越有趣.

以下是小型FFT的一些性能结果(中间执行时间超过500批1000个FFT):

我n用红色标记了素数值,用绿色标记了两倍的力量值.

标记以下观察结果:

• 一般来说,FFT对素数来说很慢,但对于两倍的幂来说很快.这是非常期待并验证结果.

• 没有n <=11可衡量的性能差异.这可能是由于FFT实现或执行开销.

• 31(可能是29)或更高的总数明显慢于其他附近值.

• 有一些非幂二值也可以提供良好的性能.这可能是高度复合的数字.

测量结果如下:

import numpy as np
import matplotlib.pyplot as plt
from time import time


N = np.arange(2, 65)
times = np.empty((500, N.size))
for i, n in enumerate(N):
    for r in range(times.shape[0]):
        x = np.random.randn(1000, n)
        t = time()
        y = np.fft.fft(x, axis=-1)
        t = time() - t
        times[r, i] = t


med = np.median(times, axis=0)
plt.plot(N, med, 'k')

primes = np.array([2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61])
plt.plot(primes, med[primes-2]+0.0005, 'rx', label='n = prime')

ptwos = np.array([2, 4, 8, 16, 32, 64])
plt.plot(ptwos, med[ptwos-2]-0.0005, 'gx', label='n = 2**k')

plt.legend(loc='best')
plt.xlabel('n')
plt.ylabel('time')
plt.grid()
plt.show()

Answer 2

numpy.fft对于合数来说速度很快，但是对于素数来说就不那么快了。用于pyFFTWPython 的最高性能 DFT。

\n\n

解释：

\n\n

根据一个老numpy问题，Bluestein 算法没有在素数长度数组上实现 DFT。维基百科指出，该算法的性能特征相当于应用于长度已被零填充的输入的高性能算法：

\n\n

\n

关键点是这些 FFT 的长度 N 不同：仅通过将其零填充到大于或等于 2N\xe2\x80\x931 的长度，就可以从 FFT 精确计算出这样的卷积。特别是，可以填充到 2 的幂或某种其他高度复合的大小，为此可以通过例如 Cooley\xe2\x80\x93Tukey 算法在 O(N log N) 时间内有效地执行 FFT。因此，Bluestein 的算法提供了一种 O(N log N) 的方法来计算素数大小的 DFT，尽管比计算复合大小的 Cooley\xe2\x80\x93Tukey 算法慢了几倍。

\n

\n\n

我建议numpy通常避免在这些退化情况下使用 \ 的实现。请改用https://pypi.python.org/pypi/pyFFTW。我的直觉是性能差异将保持不变（即速度减半），直到填充长度数组不再适合处理器的缓存\xe2\x80\x94，然后速度会慢 10-100 倍。

\n