47 lines
1,008 B
Python
47 lines
1,008 B
Python
# DFT vs FFT - porovnani casu
|
|
from cmath import exp, pi
|
|
import numpy as np
|
|
import time
|
|
|
|
|
|
def fft(f):
|
|
N = len(f)
|
|
|
|
if N <= 1:
|
|
return f
|
|
|
|
even = fft(f[0::2])
|
|
odd = fft(f[1::2])
|
|
|
|
T = [exp(-2j * pi * k / N) * odd[k] for k in range(N // 2)]
|
|
|
|
return [even[k] + T[k] for k in range(N // 2)] + [even[k] - T[k] for k in range(N // 2)]
|
|
|
|
|
|
def dft(f):
|
|
N = len(f)
|
|
result = [0] * N
|
|
|
|
for i in range(N):
|
|
for j in range(N):
|
|
result[i] += f[j] * exp(-2j * pi * i * j / N)
|
|
return result
|
|
|
|
|
|
print("i, 2**i DFT, FFT, numpy")
|
|
for i in range(10, 21):
|
|
f = [1] * 2**i
|
|
start_time_D = end_time_D = 0
|
|
if i < 15:
|
|
start_time_D = time.time()
|
|
dft(f)
|
|
end_time_D = time.time()
|
|
|
|
start_time_F = time.time()
|
|
fft(f)
|
|
end_time_F = time.time()
|
|
|
|
start_time_N = time.time()
|
|
np.fft.fft(f)
|
|
end_time_N = time.time()
|
|
print(i, 2**i, end_time_D - start_time_D, end_time_F - start_time_F, end_time_N - start_time_N)
|