# FFT卷积的速度比较

相关文档： [_频域信号处理_](21)

直接卷积的复杂度为O(N*N)，FFT的复杂度为O(N*log(N))，此程序分别计算直接卷积和快速卷积的耗时曲线。请注意Y轴为每点的平均运算时间。


# -*- coding: utf-8 -*-

import numpy as np

import timeit

def fft_convolve(a,b):

n = len(a)+len(b)-1

N = 2**(int(np.log2(n))+1)

A = np.fft.fft(a, N)

B = np.fft.fft(b, N)

return np.fft.ifft(A*B)[:n]

if __name__ == "__main__":

from pylab import *

n_list = []

t1_list = []

t2_list = []

for n in xrange(4, 14):

N = 2**n

count = 10000**2 / N**2

if count > 10000: count = 10000

setup = """

import numpy as np

from __main__ import fft_convolve

a = np.random.rand(%s)

b = np.random.rand(%s)

""" % (N, N)

t1 = timeit.timeit("np.convolve(a,b)", setup, number=count)

t2 = timeit.timeit("fft_convolve(a,b)", setup, number=count)

t1_list.append(t1*1000/count/N)

t2_list.append(t2*1000/count/N)

n_list.append(N)

figure(figsize=(8,4))

plot(n_list, t1_list, label=u"直接卷积")

plot(n_list, t2_list, label=u"FFT卷积")

legend()

title(u"卷积的计算时间")

ylabel(u"计算时间(ms/point)")

xlabel(u"长度")

xlim(min(n_list),max(n_list))

show()