はじめに
K&Rで紹介された二分木は、単語の出現頻度を扱うのに便利な機能を提供します。同じことは二重配列でも実現できますが、扱いづらいのが難点です。辞書dictは、配列にはない、便利な機能を提供します。そこで、二分木を辞書としても扱えるように再構成してみるのも一興です。
対象読者
こんな症状を抱えているなら……。
- 配列の添字に数値以外を使いたい
- 配列の中に任意のオブジェクトを混在させたい
辞書の使用例
手始めに、次のコードを実行してみてください。
>>> from random import *
>>> m = {}
>>> for e in range(100):
... k = randint(0,9)
... m[k] = m.get(k,0) + 1
>>> reduce(lambda acc,e:acc+e, m.values(), 0)
100
>>> for k,v in m.items(): print "%d: %s %d"%(k,"*"*v,v)
0: ******** 8
1: ********** 10
2: ******** 8
3: ******** 8
4: ************* 13
5: ******** 8
6: ********* 9
7: ************ 12
8: ************ 12
9: ************ 12
これは、1桁の乱数（0～9）を 100 個生成して、そのヒストグラム〔histogram〕を作成したものです。各行には、乱数（階級）とその出現頻度（度数）が出力されます。各度数には、それと同数の文字 "*" を並べた後に、数値を示しています。
そこで、このヒストグラムの事例を使って、先の連載で紹介した二分木と、組み込み型dictとを比較しながら、それぞれの理解を深めます。
辞書：参照と変更
辞書〔dictionary〕とは、写像型〔mapping type〕を実現したもので、連想記憶〔associated memory〕または連想配列〔associative array〕とも呼ばれます。キー〔key〕と値〔value〕からなる要素対を列挙したもので、それらを列挙する順序には意味がありません。
>>> ord("A"), hex(ord("A"))
(65, '0x41')
組み込み関数ordを利用すると、任意の文字に対応する ASCII コード値が得られます。また、組み込み関数hexを利用すると、任意の整数に対応する16進表記の文字列が得られます。ここでは、文字'A'の値が 65 であり、それは16進表記で'0x41'となるのが分かります。そこで、文字とその ASCII 値の対からなる要素を辞書を使って表現すると、次のようになります。
リテラルを使って
>>> {"A" : ord("A")}
{'A': 65}
>>> {"A":65, "B":66}
{'A': 65, 'B': 66}
辞書は、括弧 {} の中に、キーと値をコロン「:」で区切って表現します。ここでは、文字列キー'A'に整数値 65 が対応するのが分かります。また、複数の要素対を列挙するときには、各要素対をカンマ「,」で区切って表現します。
変数を使って
>>> s = {"A":65,"B":66}
>>> s
{'A': 65, 'B': 66}
演算子 = を使うと、ある変数に任意の辞書を束縛させることができます。ここでは、変数 sを介して、辞書にアクセスできるようになります。
値を参照するには
>>> s["B"] 66
辞書の値を参照するには、キーを利用します。演算子 [] の中に任意のキーを指定すると、対応する値が得られます。ここでは、文字列キー'B'に整数値 66 が対応するのが分かります。
値を変更するには
>>> s["C"] = ord("C")
>>> s
{'A': 65, 'C': 67, 'B': 66}
さらに、演算子 [] と演算子 = を組み合わせると、任意のキーに対して値を設定できます。最初は、指定したキー'C'が辞書に含まれないので、文字列キー'C'に整数値 67 が対応する、新たな要素対'C':67が追加されます。ここで注意して欲しいのは、辞書に要素を登録する順序には意味がないことです。そのため、新たに追加した要素対が（それを追加した順序とは関係なく）2番目に表示されます。
>>> s["C"] = hex(s["C"])
>>> s
{'A': 65, 'C': '0x43', 'B': 66}
今度は、指定したキー'C'が辞書に含まれるので、既存の要素対が更新されます。すると、更新した要素対'C':'0x43'によって、文字列キー'C'には、もとの整数値を16進表記した文字列'0x43'が対応します。辞書に登録された要素対（キー/値）には、異なる型のものを混在できます。ここでは、すべてのキーは文字列ですが、対応する値には数値と文字列とが混在しています。
辞書の中に、同じキーが含まれないときには、新たな要素対を追加しますが、既に同じキーが含まれるときには、それに対応する値だけを更新します。そのため、最初は、キー'C'が含まれないので、新たな要素対'C': 67を追加しますが、次には、キー'C'が含まれるので、古い値 67 ではなく、新しい値'0x43'を束縛します。
