ハイパフォーマンスPython 第2版

4章辞書と集合

4章を読めば以下の問いに答えられるようになる

• 辞書と集合の長所は？
• 辞書と集合の共通点は？
• 辞書を使うときのオーバーヘッドは？
• 辞書の性能を向上させる方法は？
• Pythonが名前空間を管理するためにどのように辞書を使っているか？

　辞書（dict）と集合（set）は、データに固有の順序（挿入順序を除く）がなく、参照可能なユニークなオブジェクトがある場合に最適なデータ構造です。参照に用いるオブジェクトを「キー（key）」といい、データを「値（value）」といいます。キーには文字列がよく使われますが、ハッシュ可能なデータ型であれば何でも使えます。辞書と集合はほとんど同じものですが、集合には値がなく、ユニークなキーの集まりだけがあります。名前が示すとおり、集合型は、集合演算に非常に便利です。

	ハッシュ可能な型とは、関数__hash__と、__eq__か__cmp__のいずれかを実装したものです。Pythonの組み込み型には、これらが実装済みであり、ユーザー定義のクラスにもデフォルトの値があります。詳細は「4.1.4　ハッシュ関数とエントロピー」を参照してください。

　前章で説明したように、固有の順序がないリストやタプルを探索する計算量はO(n)であり、ソートされていれば最良でO(log n)でした。一方、辞書と集合では任意のインデックスに対する探索の計算量はO(1)で済みます。さらに、リストやタプルと同様に、辞書と集合はO(1)の挿入時間で済みます†1。「 ...