Numpy fft 对于长样本会冻结

Question

我现在在玩numpy.fft这个库。我有200个.wav文件，每个文件都是单个音符，长度大约4秒。我一个一个地对每个文件运行numpy.fft，但对于那些长度在4.5秒或更长的样本，numpy.fft就会卡住。我不明白为什么会这样？另外，如果我明确指定fft的长度，函数就能正常工作，但它检测到的频率是错误的（频率偏高了一到两个半音）。

这是我的代码：

(framerate, sample) = wav.read(wav_file)
monoChannel = sample.mean(axis=1)
fft_length = int(duration * framerate)     # duration is usually around 4sec long
FFT = numpy.fft(monoChannel, n=fft_length)

对于fft_length小于216090的样本，numpy.fft工作得很好，但对于任何更长的fft，算法就会挂起，不过在我按下终端的ctrl+C后，它又会继续运行。

我使用的是python 2.7.3

我对FFT还很陌生，真的很想搞清楚这里发生了什么。

Answer 1

在 np.fft 中使用的快速傅里叶变换（FFT）算法在处理输入长度有很多小质因数时表现得非常好（也就是复杂度是 O(n log n)），但当输入长度是质数时，表现就很差（这时需要用到简单的离散傅里叶变换，复杂度是 O(n^2)）。下面是一些关于二的幂和下一个最小质数的时间测试示例：

In [69]: a = np.random.rand(1024)
In [70]: b = np.random.rand(1031)

In [71]: %timeit np.fft.fft(a)
10000 loops, best of 3: 20.8 µs per loop

In [72]: %timeit np.fft.fft(b)
100 loops, best of 3: 2.09 ms per loop

In [73]: a = np.random.rand(65536)
In [74]: b = np.random.rand(65537)

In [75]: %timeit np.fft.fft(a)
100 loops, best of 3: 3.16 ms per loop

In [76]: %timeit np.fft.fft(b)
1 loops, best of 3: 11.8 s per loop

对于你具体的情况，注意：

216090 = 2 * 3**2 * 5 * 7**4
216091 = 216091 (prime)
216092 = 2**2 * 89 * 607

因此：

In [77]: %timeit np.fft.fft(np.random.rand(216090))
10 loops, best of 3: 37.1 ms per loop

In [78]: %timeit np.fft.fft(np.random.rand(216092))
10 loops, best of 3: 149 ms per loop

In [79]: %timeit np.fft.fft(np.random.rand(216091))
# Got bored and killed it before it finished, should take ~2 min
# based on the other results for prime numbers