JavaScript中最快的DFT实现方案？音频处理性能优化求助

我正在开发一个可对录制音频片段进行多种音效编辑的“工作室”网站，需对录制音频的分帧数据执行傅里叶变换。

音频录制代码 #

const signalArray = []

//once record button is clicked, record.
recordBtn.addEventListener('click', () => {
    navigator.getUserMedia({ audio: true }, onStream, onError)
})

//success callback for get user media (yes I know this method is outdated)
function onStream(stream){
    var audioCtx = new AudioContext({
        latencyHint: "interactive",
        sampleRate: sampleRate,
    });
    var inputNode = audioCtx.createMediaStreamSource(stream)
    var tunerNode = audioCtx.realTimeAudioEdit()
    var outputNode = audioCtx.destination

    inputNode.connect(tunerNode)
    tunerNode.connect(outputNode)

    setTimeout(function(){
        audioCtx.close()
    }, recordDuration)
};

function onError(){console.log("error")};

//get audio Float values as they are recorded and push them to an array
AudioContext.prototype.realTimeAudioEdit = function () {
    function edit(input, output) {
        for (var i = 0; i < output.length; i++){
            output[i] = input[i];
            signalArray.push(output[i])
        }
        return output;
    }

    var tuner = this.createScriptProcessor(bufferSize, 1, 1);
    tuner.onaudioprocess = function (e) {
        var input = e.inputBuffer.getChannelData(0);
        var output = e.outputBuffer.getChannelData(0);
        output = edit(input, output);
    };
    return tuner;
};

自行实现的DFT代码 #

function dft(data){
    const pCords = []
    for(var k = 0; k < data.length ; k++){
        var re = 0
        var im = 0
        for(var n = 0; n < data.length; n++){
            const arg = (2 * Math.PI * k * n) / data.length
            re += data[n] * Math.cos(arg)
            im -= data[n] * Math.sin(arg)
        }
        pCords.push({
            re: re/data.length,
            im: im/data.length
        })
    }
    return pCords
}

该算法基于DFT公式实现，但运行效率极低——在高性能电脑上处理45秒音频需耗时30秒。现请教：是否存在更高效的DFT实现方法？同时，若有高效DFT方案，是否也有对应的高效IDFT实现方式？

1. 改用FFT（快速傅里叶变换）替代原生DFT #

你当前的DFT实现是O(n²)时间复杂度，而FFT的时间复杂度为O(n log n)，对于大尺寸音频帧来说效率提升极其明显。

高效FFT实现思路

FFT核心是通过分治策略将DFT分解为更小的子问题，利用复数的对称性和周期性减少重复计算。以下是针对音频实输入优化的FFT实现：

function fft(data) {
    const n = data.length;
    if (n === 1) return [{ re: data[0], im: 0 }];
    
    // 确保输入长度是2的幂（FFT最优执行条件，非2的幂则补零到最近的2的幂）
    if ((n & (n - 1)) !== 0) {
        let nextPower = 1;
        while (nextPower < n) nextPower <<= 1;
        const padded = new Array(nextPower).fill(0);
        data.forEach((val, i) => padded[i] = val);
        return fft(padded);
    }

    const even = [];
    const odd = [];
    for (let i = 0; i < n; i += 2) {
        even.push(data[i]);
        odd.push(data[i + 1]);
    }

    const fftEven = fft(even);
    const fftOdd = fft(odd);

    const result = new Array(n);
    for (let k = 0; k < n / 2; k++) {
        const angle = -2 * Math.PI * k / n;
        const twiddle = {
            re: Math.cos(angle),
            im: Math.sin(angle)
        };
        const oddTwiddle = {
            re: fftOdd[k].re * twiddle.re - fftOdd[k].im * twiddle.im,
            im: fftOdd[k].re * twiddle.im + fftOdd[k].im * twiddle.re
        };
        result[k] = {
            re: fftEven[k].re + oddTwiddle.re,
            im: fftEven[k].im + oddTwiddle.im
        };
        result[k + n / 2] = {
            re: fftEven[k].re - oddTwiddle.re,
            im: fftEven[k].im - oddTwiddle.im
        };
    }

    // 和原DFT保持一致的归一化
    return result.map(val => ({ re: val.re / n, im: val.im / n }));
}

关键优化点

• 强制2的幂长度：让分治逻辑完美执行，若原帧长度不符合，补零操作不会影响音频分析结果。
• 递归分治：拆解大问题为小问题，避免重复计算三角函数值。
• 实输入优化：针对音频实数数据的特性，减少一半计算量。

2. 对应的高效IDFT（逆快速傅里叶变换）实现 #

IDFT和DFT逻辑高度相似，仅需调整两个核心参数：

1. 旋转因子的符号由负变正
2. 归一化系数对应调整

以下是匹配上述FFT的IFFT实现：

function ifft(data) {
    const n = data.length;
    if (n === 1) return [{ re: data[0].re, im: data[0].im }];
    
    // 同样确保长度是2的幂
    if ((n & (n - 1)) !== 0) {
        let nextPower = 1;
        while (nextPower < n) nextPower <<= 1;
        const padded = new Array(nextPower).fill({ re: 0, im: 0 });
        data.forEach((val, i) => padded[i] = val);
        return ifft(padded);
    }

    const even = [];
    const odd = [];
    for (let i = 0; i < n; i += 2) {
        even.push(data[i]);
        odd.push(data[i + 1]);
    }

    const ifftEven = ifft(even);
    const ifftOdd = ifft(odd);

    const result = new Array(n);
    for (let k = 0; k < n / 2; k++) {
        const angle = 2 * Math.PI * k / n; // 符号改为正
        const twiddle = {
            re: Math.cos(angle),
            im: Math.sin(angle)
        };
        const oddTwiddle = {
            re: ifftOdd[k].re * twiddle.re - ifftOdd[k].im * twiddle.im,
            im: ifftOdd[k].re * twiddle.im + ifftOdd[k].im * twiddle.re
        };
        result[k] = {
            re: ifftEven[k].re + oddTwiddle.re,
            im: ifftEven[k].im + oddTwiddle.im
        };
        result[k + n / 2] = {
            re: ifftEven[k].re - oddTwiddle.re,
            im: ifftEven[k].im - oddTwiddle.im
        };
    }

    // 对应FFT的归一化，确保逆变换还原原始信号
    return result.map(val => ({ re: val.re, im: val.im }));
}

3. 额外性能优化建议 #

• 使用TypedArray：用Float32Array存储音频数据，比普通数组内存开销更低、访问速度更快。
• 预计算三角函数：若处理固定长度的音频帧，可提前计算所有旋转因子的三角函数值，避免重复计算。
• WebAssembly加速：若需要极致性能，可将FFT/IFFT逻辑用C/C++实现后编译为WebAssembly，性能比纯JS实现快数倍。

内容的提问来源于stack exchange，提问作者BigChungus443