python - scipy.fftpack 的 FFT 冻结

Question

在计算大小为约 150 万个项目的数组的 FFT 时：

import numpy as np
from scipy.fftpack import fft

x0 = np.ones(1492828, dtype=np.int32)
fft(x0)
print 'hello'

FFT 计算永远不会完成，程序正在冻结。如果我更改1492828为1492827，它似乎工作。但是，如果我更改1492828为1492826，它仍然会冻结，这有点奇怪。

这是一个已知的错误？

笔记：

• CPU 保持在 25%（正常，我有一个 4 核 CPU），Python 进程的 RAM 使用率保持在 ~75 MB

• 我在 Windows 7 64 位上使用 Python 2.7.15 64 位：

  print scipy.__version__     # 1.1.0
  print sys.version           # 2.7.15 (v2.7.15:ca079a3ea3, Apr 30 2018, 16:30:26) [MSC v.1500 64 bit (AMD64)]
  

Answer 1

通常的 FFT 算法对于具有小的素因数的长度要快得多，如此处所述。

解决方案是将数组补零到 2 的下一个幂：

def zeropad_nextpoweroftwo(A):
    return np.concatenate([A, np.zeros(int(2 ** np.ceil(np.log2(len(A))))-len(A), 
        dtype=A.dtype)])

或者，一个更简单/更好的解决方案是使用第二个参数允许自动填充零next_fast_len的事实：fftpack.fft

fftpack.fft(a, next_fast_len(len(a)))