初めに
高速フーリエ変換(FFT)は通常の離散フーリエ変換(DFT)と比較して計算速度も速くて非常に便利ですが、データ数が2のべき乗個のでないと計算効率が良くないという欠点があります。
Scipyのfftpackのfft場合、2のべき乗個でなくても計算はしてくれるのですが、大量のデータを計算した時に体感でもかなり速度が低下したことがわかります。
ちなみに理論的にはFFTの計算量はNlogN、DFTはNの自乗の計算量になるらしいです。詳しくはwikideiaのFFTのページを参照ください。
理論はともかく、今回2のべき乗のデータとそうでないデータを作成して実際に計算速度を比較してみました。
環境は
- scipy version 1.0.0
- numpy version 1.12.1
- CPU core i5 7200U
となっています。Jupyter Notebookのマジックコマンド%timeitで計算速度を計算してます。
2のnべき乗個でない場合
# -*- coding: utf-8 -*-
import numpy as np
from scipy import fftpack
data = np.random.random(2**17-2)
%timeit fftpack.fft(data)
2の17乗個から2個マイナスして131070個の乱数を生成しました。
本当はもう少し意味のあるデータのほうが良いかもしれませんが、手抜きです。
結果は
100 loops, best of 3: 11.5 ms per loop
となりました。
このぐらいのデータ数だと特に計算速度は問題ならないですね。
2のnべき乗個の場合
上記のコードのデータ数だけいじります。
# -*- coding: utf-8 -*-
import numpy as np
from scipy import fftpack
data = np.random.random(2**17)
%timeit fftpack.fft(data)
結果は
100 loops, best of 3: 2.7 ms per loop
となり、(これぐらいのデータ数では誤差の範囲ですが)かなり時間短縮されました。
しかしながら現実のデータが2のべき乗個であることはほとんどありません。その場合はデータ数が2のべき乗個になるように前後に0のデータをつけることによって、データ数を2のべき乗個になるように調節する方法があります。
# -*- coding: utf-8 -*-
import numpy as np
from scipy import fftpack
data = np.random.random(2**17-2)
data_sq = np.zeros(2**17)
data_sq[1:-1] = data
%timeit fftpack.fft(data_sq)
今回は2のべき乗個でない配列dataを、2のべき乗個の「ゼロ」で構成された配列data_sqに代入しています。
data_sqに対してFFTを行った時の出力結果は
100 loops, best of 3: 2.69 ms per loop
となり、11.5 msと比較してかなり高速になっていることがわかります。
まとめ
- SciPyのFFTPackは2のべき乗個でなくても計算してくれるが、計算速度は犠牲になる。
- 計算速度が問題になる場合は前後に0のデータをつけると良い。