python - 离散傅立叶变换在python中不起作用/效率很低

我正在尝试在 python 中编写一个离散傅立叶变换函数，它将以数组的形式给出信号的能量谱密度(然后我将以图形方式输出)。我正在使用矩阵乘法来做到这一点。我的代码似乎适用于一小部分数据，但需要很长时间来处理；对于大量数据，例如一个 wav 文件，它永远不会完成任务。该功能目前是:

from scipy.io import wavfile
import numpy as np
import matplotlib.pyplot as plt

def esd(数据，fs):

a=[]


for i in range(int(np.size(data)/100)):

    dt = 1/(fs)

    fvec = np.arange(100*i , 100+(100*i) , 1)
    nvec = np.arange(0 , np.size(data) , 1)

    Wconst = np.exp(-1j*2*np.pi/np.size(data))

    ematrix = Wconst**(np.outer(fvec,nvec))

    b = (dt**2)*(abs(np.inner(ematrix , data))**2)

    a = np.concatenate((a,b))




return a

其中 data 是数据集，fs 是采样频率。这个功能如此缓慢或低效有什么原因吗？它旨在处理 100 个频率块中的信号，否则矩阵将非常大。

最佳答案

该算法通过计算 Vandermonde 频率矩阵来实现“朴素”离散傅立叶变换 (DFT)。问题就在这里:

b = (dt ** 2) * abs(np.inner(ematrix, data)) ** 2

这个简单的实现使用直接矩阵向量乘法，并且运行时间为 O(N**2) ，其中 N == data.size 。因此，当您获得更大的数据时，情况会更糟，并且可能无法在合理的时间内完成您的 WAV 文件。

这就是使用快速傅立叶变换算法的全部意义所在，它利用了问题中的大量结构。最值得注意的是，FFT 将问题递归分解为 N / 2 大小的较小问题。这种递归结构使 FFT 的运行时间为 O(N log N) 。

关于python - 离散傅立叶变换在python中不起作用/效率很低，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/47660194/