FFTのメモリーを無駄遣いしない実装

2025/03/09

　本記事では、前記事で解説した「高速フーリエ変換(FFT)」における、 メモリーを無駄遣いしない実装による最適化について解説します。 前記事を理解していることが前提のため、まだの方は先にそちらをご覧いただくことを推奨します。

メモリーとは

　コンピューターは主に、実行を司るCPU(しーぴーゆー)と、記憶を司るメモリーから成り立ちます。
　今のコンピューターには他にも色々な要素がありますが、この2つが最も重要な要素です。
　どちらも限られた資源であり、有効活用することで最適化に繋がります。 例えばメモリーをたくさん使用してしまうと、それ以上アプリケーションを起動できなくなる、あるいは起動に非常に時間がかかるようになるなどの問題が発生します。
　本記事では、その大切なメモリーを無駄遣いしないことによる最適化手法について解説します。

データはメモリーに置かれる

　処理されるデータは、メモリーに置かれます。
　元々のデータは外部ストレージに保存されていて、そこからメモリーに読み込まれる場合もあるでしょうし、 プログラムでメモリー上に生成される場合もあるでしょう。 いずれにしても、データはメモリーに配置されて、処理されます。

メモリーコピーの問題点

　データを処理する際に、色々なプログラムに処理を引き継いでいくことはよくあります。 別のプログラムに処理を移すときには、処理するデータもそのプログラムに渡す必要があります。
　その際、データを複製して渡してしまえば、プログラミングは比較的容易になることが多いです。
　この方式はメモリーコピーと呼ばれます。 しかしこの方式では、別のプログラムが呼ばれる度に、新しいメモリー領域を確保して、そこにデータをコピーしていく形になりますので、 多くのメモリーを消費するだけでなく、処理速度の低下も招きます。 今回のFFTのように、元データの量が大きく、何度も別のプログラムに渡されるケースでは、できるだけメモリーコピーをしないべきです。
　ただし、そのためにはプログラミングの工夫が必要なため、以下で解説していきます。

高速フーリエ変換(FFT)のポイントおさらい

　高速フーリエ変換は、元のデータ配列を偶数番データ配列と奇数番データ配列に分解していき、 それぞれの結果を合成していく方式で、高速化を実現するものです。
　詳細はこちらをご覧ください。

偶数番配列、奇数番配列の作り方

　高速フーリエ変換では、偶数番データ配列と、奇数番データ配列を作る必要があります。
　この図のように、元データ配列が8個であれば、4個のデータが格納できる領域を2箇所確保して、そこに対象のデータをコピーする、と考えるのが自然です。
　このメモリーコピーをしない工夫を考えましょう。

ステップ数を導入

　まず、配列の情報として、ステップ数を導入します。
　+1 が初期状態です。
　図のように +2 であれば、データ配列はひとつずつ飛ばして読む、と定義します。 そうすることで、偶数番データ配列が作れます。

開始位置を導入

開始位置	ステップ数	内容
0	2	偶数番データ配列
1	2	奇数番データ配列

　加えて開始位置を導入します。
　初期状態は0です。
　開始位置が +1、ステップ数が +2 なら奇数番データ配列です。

次の段階における開始位置とステップ数

　偶数番データ配列を、さらに偶数番データ配列と奇数番データ配列に分離していきましょう。
　この図の上のように、その配列だけを見ればステップ数を2にすればよいのですが、 実際にはこの図の下のようになりますので、ステップ数は4になります。

　まとめるとこのとおりです。

開始位置	ステップ数	内容
0	4	偶数番＞偶数番
2	4	偶数番＞奇数番

　奇数番データ配列も以下のようにさらに偶数番データ配列と奇数番データ配列に分割できます。

開始位置	ステップ数	内容
1	4	奇数番＞偶数番
3	4	奇数番＞奇数番

開始位置とステップ数を求める計算式

　上記をプログラミングできるようにしましょう。 次の段階における開始位置とステップ数を求める計算式は、以下のとおりです。 仮想的なプログラムコードで記します。

　これらの情報を次のプログラム(関数)に渡していくことで、元データをメモリーコピーすること無く、 偶数番データ配列、奇数番データ配列に分解して進めることができるようになりました！

変換結果データ配列のメモリー確保を抑制

　高速フーリエ変換の実装では、偶数番データ配列と奇数番データ配列に分解して変換したあと、 変換結果データ配列を合成していく必要があります。 そちらもメモリーを無駄遣いしない工夫をしていますので、解説します。

解答データ配列の書き込み位置を指定

　結論としては、偶数番データ配列の変換結果を前半に、奇数番データ配列変換結果を後半に書き込むようにします。
　そのために、変換結果を書き込むための、変換結果データ配列の領域を確保してから処理を開始します。

次のステップでもさらに指定

　次のステップでも変換結果データ配列の書き込み位置を指定します。
　偶数番配列の変換結果は、変換結果データ配列の前半の半分に書き込むことになっていますので、 さらにそれを、この図のように、前半と後半にわけて指定します。

フーリエ変換結果を加減算するときに書き戻す

　フーリエ変換結果は、段階をひとつ戻る度に合成する必要があります。
　この図は、上部にはひとつ前の段階の変換結果が入っています。 前半[\(F_0F_1\)]が偶数番データ配列の変換結果、後半[\(F_2F_3\)]が奇数番データ配列の変換結果です。
　これらを、以下の仮想プログラムコードで合成します。
　このプログラムの F[0]は、図の上部分の\(F_0\)に、Fnew[0]は、図の下部分の\(F_0\)に対応しています。
　つまりこの式は \(F_0\)と\(F_2\)のみの影響しかありません。 これは、次の \(F_1\)と\(F_3\) でも同様です。
　この場合 \(F_0\)と\(F_2\) の値が変更されても、次の \(F_1\)と\(F_3\) の処理に影響がありません。 つまり合成結果は、同じメモリー領域に書き戻すことができます。
　こうすることで、各段階ごとに変換結果用のメモリー領域を確保する必要がなくなりますので、メモリーの節約になります。
　ただし、例えば加算時に単純に F[0] に書き戻してしまうと、減算で F[0] を使用する前に変わってしまい、正しい結果が得られません。

　そのため、プログラミングは注意が必要です。 例えば以下のようにします。

　なお、この加減算は、実際には単純な加減算ではありません。 高速フーリエ変換の概要についてはこちらごご参照ください。

最後まで合成して結果完成

　この処理を各段階で実施します。 そして最後まで実施することで、変換結果のデータ配列が完成します。

FFT関数に渡す情報を整理

　以上を統合すると、各段階でのFFT関数が必要な情報は以下の通りです。

• 固定された情報
• 元データ配列
• 変換結果データ配列
• 呼び出しごとに変わる情報
• 元データ配列読み出し開始位置
• 元データ配列読み出しステップ数
• 変換結果データ配列書き込み開始位置

　なお特に触れていませんでしたが「変換結果データ配列書き込みステップ数」は常に1です。

どのくらい無駄遣いを減らせたか

　これでどのくらいメモリーの無駄遣いが減るのでしょうか。 結論としては、1秒の音声で約12MBの無駄遣いを減らせることになります。
　以下、詳細は省略して、ざっと追います。
　44.1KHzでサンプリングしたデータは、1秒で44100個。 高速フーリエ変換ではデータ数が65536個へ拡張されて16回の分解と合成が必要です。
　元データ1個につき4バイト、変換結果データは1個につき8バイトの必要なため、 メモリーコピー方式ですと \(65536 \times (4 + 8) \times 16 = 12582912\) 必要です。
　元データ領域と変換結果データ領域として1つぶん、すなわち \(65536 \times (4 + 8) = 786432\) は必要ですので、それを除いた分が無駄遣いです。
　これが多いか少ないかは、使っているシステムによっても変わるでしょう。 ただし現行の家庭用ゲーム機でのプログラミングなら、この工夫ができるのにしないのであれば、先輩(?)に怒られそうです。

パズルを解いている楽しさ

　今回の件に限らず、こうした工夫は、セオリーの部分もありますが、ひらめきが必要になる場合もあります。 ほんのちょっとしたことだったとしても、うまくいくと、パズルを解いている楽しさを感じます。
　なお、本記事の工夫は、自分の力だけではまったく無くて、補足に記載の記事を参考にさせてもらいました。 感謝しております。

まとめ

　本記事では、高速フーリエ変換(FFT)における、メモリーを無駄遣いしない実装による最適化ついて解説しました。
　こうした工夫を通して、プログラミングが少しでも楽しいと感じていただけたら幸いです。

補足

・仮想プログラム内の「=」(イコール)は、右辺の計算結果を、左辺に代入することを意味します。
・仮想プログラム内の「*」(アスタリスク)は乗算を表します。
・MBはメガバイトです。メガ(M)は100万倍です。
・フーリエ変換の実装ではこちらとこちらのサイトを参考にさせてもらいました。特に前者は実装が美しくてため息が出るほどでした。
・画像内のラスタライズ文字フォントにOpen Font LicenseのZen Antiqueを使用しております。
・画像内のラスタライズ文字フォントにOpen Font LicenseのNoto Sans Japaneseを使用しております。
・数式表現にMathJaxを使用しております。助かります！

カテゴリー：オーディオ推し,プログラミング

Copyright (C) Logic Lovers Inc.

Loading...

Loading...