Scipyの高速フーリエ変換のデータ数(2のべき乗か否か)と計算時間の関係について - Qiita

初めに 高速フーリエ変換(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のマジックコマンド%timei