ハイパフォーマンスPython

4章辞書と集合

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

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

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

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

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