状態変化なしに効率的な辞書を実装する重み平衡木 - Qiita状態変化なしに効率的な辞書を実装する重み平衡木 はじめに キーを指定して値を検索したいことはよくある。このような操作のために作られたデータ構造を辞書や連想配列と呼ぶ。多くの言語では辞書としてハッシュテーブルを使う。ハッシュテーブルの時間効率は「いちおう」O(1)ということになっている。しかし、ハッシュテーブルは「状態変化」を前提としたデータ構造だ。ハッシュテーブルは挿入・削除の操作のたびに変化し続ける。 状態変化があるということはコードの実行順序によって値が変化する可能性があるということだ。状態変化による結果を完全に理解することは人間の得意とするところではない。すぐに人間の思考はごちゃごちゃになってしまう。そしてよく訓練されたHaskellerなら非本質的な状態変化を「美しくない」と感じるはずだ。 リストによる辞書 そうだリストを使おう。リストを使えば状態変化にわずらわされることはない。キ
