提高Python中FFT的性能

Question

在Python中，哪个快速傅里叶变换（FFT）的实现最快？

看起来numpy.fft和scipy.fftpack都是基于fftpack这个库，而不是FFTW。fftpack的速度和FFTW相比怎么样？那如果使用多线程的FFT或者分布式（MPI）FFT呢？

Answer 1

pyFFTW3这个包在实现上比pyFFTW要差一些。因为它们都是在使用FFTW3这个库，所以我想它们的速度应该差不多。

https://pypi.python.org/pypi/pyFFTW

Answer 2

在一个测试中，详细信息可以在这个链接找到：https://gist.github.com/fnielsen/99b981b9da34ae3d5035。我发现使用scipy.fftpack的表现还不错，跟我用pyfftw.interfaces.scipy_fftpack简单应用pyfftw相比，除了处理长度为质数的数据时表现不佳。

第一次调用pyfftw.interfaces.scipy_fftpack.fft时，似乎会有一些准备时间，但第二次就快多了。对于我尝试的数据大小，Numpy和scipy的fftpack在处理质数长度的数据时表现得很糟糕。在这种情况下，CZT的速度更快。几个月前，Scipy的Github上也有关于这个问题的讨论，具体可以查看这个链接：https://github.com/scipy/scipy/issues/4288

20000 prime=False
  padded_fft : 0.003116
   numpy_fft : 0.003502
   scipy_fft : 0.001538
         czt : 0.035041
    fftw_fft : 0.004007
------------------------------------------------------------
20011 prime=True
  padded_fft : 0.001070
   numpy_fft : 1.263672
   scipy_fft : 0.875641
         czt : 0.033139
    fftw_fft : 0.009980
------------------------------------------------------------
21803 prime=True
  padded_fft : 0.001076
   numpy_fft : 1.510341
   scipy_fft : 1.043572
         czt : 0.035129
    fftw_fft : 0.011463
------------------------------------------------------------
21804 prime=False
  padded_fft : 0.001108
   numpy_fft : 0.004672
   scipy_fft : 0.001620
         czt : 0.033854
    fftw_fft : 0.005075
------------------------------------------------------------
21997 prime=True
  padded_fft : 0.000940
   numpy_fft : 1.534876
   scipy_fft : 1.058001
         czt : 0.034321
    fftw_fft : 0.012839
------------------------------------------------------------
32768 prime=False
  padded_fft : 0.001222
   numpy_fft : 0.002410
   scipy_fft : 0.000925
         czt : 0.039275
    fftw_fft : 0.005714
------------------------------------------------------------

Answer 3

你可以用Cython或者其他类似的工具来包装你想测试的任何FFT实现，这样就能访问外部库了。

基于GPU的

如果你要测试FFT实现，可能还需要看看基于GPU的代码（前提是你有合适的硬件）。有几个不错的选择：reikna.fft和scikits.cuda。

基于CPU的

还有一个基于CPU的Python FFTW封装，叫pyFFTW。

（还有一个叫pyFFTW3的，但它的维护不如pyFFTW活跃，而且不支持Python3。(来源))

我对这些都没有经验。如果你对速度很在意，可能需要自己多花点时间去研究和测试不同的代码，看看哪个最适合你的应用。