通常配列と連想配列の併用による時間計算量削減

はじめに

ABC343-D問題を解いていたら、通常配列と連想配列を併用して解く問題が登場した。

素朴に考えれば、データは１つの形式で持っておく方が自然だし、同じ対象を２つの形式で保持すれば、両者の間に競合が発生し内容に実装にナイーブになる必要がある。

通常配列 vs 連想配列

通常配列は、順番が重要なデータに対して使用される。ランダムアクセスがO(1)だが、追加削除がO(N)である。とにかく、前から順番に値が入るので、順番が重要なデータは通常配列として持つのが自然。

連想配列は、データの順番が重要では無い場合に使用すると有効。追加や削除、検索はO(1)で行える。

対象に応じてこれらの特性を活かすのが大事で、他にもデータ構造は複数あるし、言語によっても違う。ただ、「順序が必要かどうか」は、データ構造を考える上で広く使える味方だと思う。

「連結リスト＋連想配列」の実例

一見不自然で素朴では無い気がしたこの実装、実は現実問題に対しても使われている。

LRUというキャッシュアルゴリズムでは、最近使われていない、つまり最後に使われてから最も時間が経過しているものを削除するという方法でキャッシュを管理する。

ここで、連想配列は idから履歴のデータを参照するために、連結リストは、時系列順にでデータを保持するために、という別々の用途で使用されているらしい。