Numpy fft.pack vs FFTW vs 自己实现 DFT

Question

我目前需要运行对 1024 个采样点信号进行 FFT。到目前为止，我已经在 python 中实现了自己的 DFT 算法，但它非常慢。如果我使用 NUMPY fftpack，甚至转向 C++ 并使用 FFTW，你们认为会更好吗？

Answer 1

如果您完全在 Python 内实现 DFFT，您的代码将运行 数量级 比您提到的任何一个包都慢。不仅因为这些库是用低级语言编写的，而且（尤其是 FFTW）它们经过高度优化，利用了缓存局部性、向量单元以及本书中基本上所有的技巧，这不足为奇如果他们运行的速度是天真的 Python 实施速度的 10,000 倍。即使你在你的实现中使用了 numpy，相比之下它仍然显得苍白无力。

是的；使用 numpy 的 fftpack。如果这还不够快，您可以尝试 FFTW (PyFFTW) 的 python 绑定，但从 fftpack 到 fftw 的加速不会那么显着。我真的怀疑是否有必要只为 FFT 使用 C++ - 它们是 Python 绑定的理想情况。

Answer 2

如果您需要速度，然后想要进行 FFTW，请查看 pyfftw 项目。为了使用处理器 SIMD 指令，您需要对齐数据，而在 numpy 中没有一种简单的方法可以做到这一点。此外，pyfftw 允许您使用真正的多线程，相信我，它会快得多。

Answer 3

如果您希望坚持使用 Python（处理和维护自定义 C++ 绑定可能很耗时），您可以选择使用 OpenCV's FFT 实现。

我在 python（Intel(R) Core(TM) i7-3930K CPU）中整理了一个比较 OpenCV 的 dft() 和 numpy 的 fft2 函数的玩具示例。

samplesFreq_cv2 = [
        cv2.dft(samples[iS])
        for iS in xrange(nbSamples)]

samplesFreq_np = [
        np.fft.fft2(samples[iS])
        for iS in xrange(nbSamples)]

从 20x20 到 60x60 的不同分辨率的 20000 个图像块顺序变换的结果：
Numpy 的 fft2：1.709100 秒
OpenCV 的 dft：0.621239 秒

这可能不如绑定到像 fftw 这样的专用 C++ 库那么快，但它是一个相当容易实现的成果。

Numpy fft.pack vs FFTW vs 自己实现 DFT

Numpy fft.pack vs FFTW vs Implement DFT on your own

python

numpy

fft

fftw