Numpy Funktion + Konstante zu verwenden

from numpy import tile, interp, linspace, exp, r_, pi

DFT (langsam)

def dft(x):return exp(-2j * pi * r_[:len(x)] / len(x))**r_[[r_[:len(x)]]].T @ x

FFT (beschränkt auf Leistungselemente von 2)

def fft(x):return tile(fft(x[::2]), 2) + (r_[[[1],[-1]]] * (exp(-2j * pi * r_[:len(x) // 2] / len(x)) * fft(x[1::2]))).ravel() if len(x) > 1 else x

FFT (keine Begrenzung der Anzahl der Elemente, lang)

def fft(x):return interp(linspace(0, 1 << (len(f'{len(x) - 1:b}')), len(x)), r_[:1 << (len(f'{len(x) - 1:b}'))], fft(r_[x, [0] * ((1 << (len(f'{len(x) - 1:b}'))) - len(x))])) if ('1' in f'{len(x):b}' [1:]) else tile(fft(x[::2]), 2) + (r_[[[1], [-1]]] * (exp(-2j * pi * r_[:len(x) // 2] / len(x)) * fft(x[1::2]))).ravel() if len(x) > 1 else x

Funktionsprüfung

from numpy import sin, fft, random
import matplotlib.pyplot as plt

Zu konvertierende Wellenform

Synthese von 5 $ sin $ Wellen mit zufälliger Frequenz und Amplitude, $ 2048 (= 2 ^ {11}) $ Element

n = 1 << 11
x = linspace(0, 2 * pi, n)
y = 0

for w in n / 2 * random.rand(5):
    y += random.rand() * sin(w * x)

plt.plot(x, y, lw = .3)

Numpy.fft.fft

%timeit fft.fft(y)
plt.plot(abs(fft.fft(y))**2)

9.01 µs ± 42.9 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)

DFT

%timeit dft(y)
plt.plot(abs(dft(y))**2)

568 ms ± 899 µs per loop (mean ± std. dev. of 7 runs, 1 loop each)

FFT (begrenzt auf das Leistungselement 2)

%timeit fft(y)
plt.plot(abs(fft(y))**2)

51.2 ms ± 76.9 µs per loop (mean ± std. dev. of 7 runs, 10 loops each)

FFT (länger)

%timeit fft(y)
plt.plot(abs(fft(y))**2)

54.1 ms ± 159 µs per loop (mean ± std. dev. of 7 runs, 10 loops each)

Zusammenfassung

Numpys FFT ist zu früh! Die Ausgabe ist dieselbe, aber Sie können sehen, dass die FFT etwa zehnmal schneller ist als nur die DFT.

[Python] Einzeilige FFT (schnelle Fourier-Transformation) und anderer Wahnsinn