PONOS Advent Calendar 2024の3日目の記事です。
はじめに
もちろん某アニメのことではありません！
だいぶ前に 【小ネタ】ルックアップテーブルの効果 という記事を書きました。
記事ではルックアップテーブルによるパフォーマンス改善を計測してみたわけですが、そもそもこのようなアルゴリズムにおける計算量というのは、どのような観点で着目すべきかという話が前提にあるよなという事をふと思いました。
ということで、今回はそれを補完する形で ビッグ・オー について書いてみたいと思います。
アルゴリズムと計算量
アルゴリズムを考えるにあたり重要な指標が二つあります。「時間計算量」と「空間計算量」です。
「時間計算量」とは時間的な資源量、つまり処理の実行回数です。「空間計算量」とは空間的な資源量、つまりメモリ使用量の指標です。
どちらについても、小さいほうがより優秀ということになりますが、ここでは前者について着目します。
ビッグ・オー（Big O） と O(1)
ビッグ・オー記法、O記法、オーダー記法などと言われます。
これはアルゴリズムの「時間計算量」に着目した指標であり、問題の大きさ（入力の大きさ）に対しての計算ステップの成長率の特性を表します。
O(1)というのは定数時間と呼ばれ、理論上の理想的な計算量のことです。
ビッグ・オーの具体例
| 表記 | 説明 | 補足 |
|---|---|---|
| O(N) | 線形時間 | 問題の大きさに比例する。例えば配列の全要素を一度に検査する際にこれ。 |
| O(N^2) | 二次時間 | 問題の大きさの二乗に比例する。ある配列に対する二重ループなどの場合です。 |
| O(log n) | 対数時間 | 問題の大きさが倍になるごとに計算量が1増加します。 ステップごとに処理データが半分になるようなアルゴリズムで、二分探索などがこれに当たります。 |
| O(1) | 定数時間 | 問題の大きさによらずに常に一定の計算量です。理論上は理想です。 |
ゲームにおけるアルゴリズム
前述の通り、アルゴリズムにおいて O(1) とは理想的な計算量です。
ゲーム開発でよく使われるものの中でも O(1) となっている仕組みがあります。もちろん、あらゆる構造が O(1) でできるわけではないですが、一般的に O(1) であることが多いものを見ていきたいと思います。
キャッシュやインベントリーシステム
例えばシンプルな Hashtable や Dictionary はキーに基づいた値の取得が O(1) であるため、データ量の増加に対しても一定の計算量でアクセスが可能です。
実際には、より複雑なキャッシュ機構を作ろうとした場合は注意が必要です。値の追加のたびに並び替えが発生するなどの場合は O(1) とはならない可能性がありますが、Least Recently Used なアルゴリズムであれば O(1) で書くことができるはずです。
オブジェクトプール
主に頻繁なオブジェクト生成を避けるために使われる、みんな大好きオブジェクトプールも通常は O(1) となるはずです。
例えば内部が Queue であれば O(1) です。
グリッドポジショニング / 空間分割
例えば近くのキャラクターを検索したり、当たり判定、経路探索など、様々な場面で全件操作のコストを低減する目的で、グリッドや円形に空間を分割してエンティティを管理するパターンがあると思います。
これらもある特定のグリッドから所属するエンティティを取得するという点において O(1) です。
実際には取り出したエンティティたちに対して個別の処理を適用するため、そこに対しての処理は O(N) になりますが、それでも一連の手続きのうちグリッドに絞り込んでいる部分が O(1) であるため有用な手段です。
まとめ
ビッグ・オーは時間計算量にしか着目していません。実際のシステムパフォーマンスはもちろん空間計算量、すなわちメモリにも注意が必要です。トレードオフとしてメモリ量が増えることもありますし、それが許容できるかできないかもケースバイケースです。
とはいえ当たり前のことではありますが "とりあえず動く" というところから脱却し、計算量が最適かどうかという視点を持ってプログラミングに臨むことは、プロのエンジニアとしてのスキルが見えてくるポイントかなと思います。
それでは次回は@kerimekaさんです。