11. 辞書を作ってみる¶

効率よく辞書を作る方法を学んで、データ構造と計算量の関係の理解を深めていきましょう。

11.1. 辞書とは¶

辞書 (dict) は、文字列を検索のキーとして、キーに対応付けられた値を取り出す簡単なデータベースです。

キー	値
apple	120
banana	100
orange	200
pineapple	50
grape	300

キー(key) は、「主キー制約」などに用いられるデータベース用語です。データセットにおいて、重複しないユニークな値であれば文字列でなくても構いません。

辞書の別称

辞書は、プログラミング言語によって、色々な呼称がある。

ハッシュ表 (hash table)
連想記憶配列
キー・バリュー・ストア (Key Value Store, KVS)
マップ (map) : キーから値への写像 (mapping) という意味

11.2. 線形探索による辞書¶

辞書のもっとも簡単な実装は、キーと値のペア線形リストで保持する方法です。

DataBase = [
    ('apple', 120),
    ('banana', 100),
    ('orange', 100),
    ('pineapple', 50),
    ('grape', 300),
]

線形リストの前から順番にキーを調べていくことで、キーに対応付けられた値を探すことができます。

[1]:

DataBase = [
    ('apple', 120),
    ('banana', 100),
    ('orange', 100),
    ('pineapple', 50),
    ('grape', 300),
]

def linear_find(key):
    for entry in DataBase:
        # entry には、('apple', 120)のようなタプルが順番に
        ekey, evalue = entry
        if ekey == key:
            return evalue
    # 見つからない場合は、KeyErrorにする
    raise KeyError(key)

print(linear_find('grape')) # 300 と 表 示 さ れ る

線形探索は単純ですが、検索速度はリストの大きさ \(N\) に依存します。平均計算量は、線形時間 \(O(N)\) となります。計算量としては悪くありません。しかし、辞書は他のアルゴリズムから頻繁に使われるため、組み合わせによってはコストが大きくなる可能性があります。

線形探索(Linear Search)

リストを前から順番に探索する手法

11.3. 二分探索による辞書¶

英和辞典を思い浮かべてください。単語を調べるとき、前から順番に全ての単語をみて探すことはしません(よね?)。なぜなら、英和辞典はアルファベット順に並んでいて、orange という単語は前より後ろの方にあることは明らかだからです。

同じように、線形リストの内容を検索する前にアルファベット順に並べておけば、英和辞典のように調べられるようになります。

ポイントは、リストの中央を調べて、探しているキーがリストの前半にあるか、それとも後半にあるか、調べることです。前半にあったら、また前半の中央を調べるように繰り返します。後半の場合も同様に繰り返します。リストの探索域を狭めていき、空になるまで繰り返します。

リストの探索域が半分になっていくので、二分探索 (binary search) と呼ばれます。

[2]:

# ソート
DataBase.sort()

def binary_find(key, start=0, end=len(DataBase)):
    mid = start + end // 2
    # 中央のタプルをとる
    ekey, evalue = DataBase[mid]
    if ekey == key:
        return evalue
    if key < ekey:
        # key は前半にある
        end = mid
    else:
        # key は後半にある
        start = mid + 1
    if end - start > 0:
        # 新しい探索域が空でなければ再帰的に調べる
        return binary_find(key, start, end)
    # 見つからない場合は、KeyErrorにする
    raise KeyError(key)

print(binary_find('grape')) # 300 と 表 示 さ れ る

二分探索は、平均計算量は、探索域が 2 分の 1 に絞られていくので、対数時間 \(O(log N )\) となります。実用上も理論上も心配のいらない計算量といえます。しかし、頻繁にデータベースが更新されるときは注意が必要になります。データベースが更新される度に、ソートしていたら、ソート・アルゴリズムの計算量 \(O(N log N )\) の計算コストが必要になります。

二分探索 (Binary Search)

探索域を分割する分割統治法による探索アルゴリズム

11.4. ハッシュ法による辞書¶

最後に、定数計算時間 O(1) でアクセスできる辞書の作り方をみてみましょう。定数時間ということは、辞書の大きさがどんなに大きくなっても計算コストは一定であるという夢のアルゴリズムといえます。

まず、配列は「O(1) で要素にアクセスできるデータ構造」ということを思い出しておきましょう。だから、辞書のキーを配列のインデックスに変換できれば、配列に格納できるようになります。

Python は、オブジェクトのハッシュ値(整数)を計算する組み込み関数 hash(x) を提供しています。

[3]:

print('apple', hash('apple'))
print('orange', hash('orange'))
print('banana', hash('banana'))
print('pineapple', hash('pineapple'))
print('grape', hash('grape'))

apple 6676052660308446185
orange 3908635519303473139
banana 8531009946719913269
pineapple -895507610814638941
grape -660568232534393894

残念ながら、ハッシュ値は大き過ぎるので、そのままインデックスにすることはできません。しかし、適切な大きさ\(M\)でモジュロを計算すると、よい感じの値になってくれます。

[5]:

M = 89
print('apple', hash('apple') % M )
print('orange', hash('orange') % M )
print('banana', hash('banana') % M )
print('pineapple', hash('pineapple') % M )
print('grape', hash('grape') % M )

apple 60
orange 59
banana 73
pineapple 16
grape 35

この hash(key) % M を配列のインデックスにして配列に格納すると、\(O(1)\) で検索できるようになります。

[6]:

M = 89
HashDB = [0] * M
def hash_set(key, value):
    HashDB[hash(key) % M] = value

hash_set('apple', 120)
hash_set('orange', 100)
hash_set('banana', 200)
hash_set('pineapple', 50)
hash_set('grape', 300)

def hash_find(key):
    return HashDB[hash(key) % M]

print(hash_find('grape'))

11.4.1. ハッシュ法と衝突¶

ハッシュ表の原理をみてきました。計算量の少ないアルゴリズムは原理も実装もシンプルなことが多いです。ただし、一つだけ困ったことが残っています。それは、\(M\) の値が小さいと、時々、モジュロをとったハッシュ値が同じ値になってしまうことです。

[7]:

M = 7
print('apple', hash('apple') % M )
print('orange', hash('orange') % M )
print('banana', hash('banana') % M)
print('pineapple', hash('pineapple') % M )
print('grape', hash('grape') % M )

apple 1
orange 6
banana 1
pineapple 0
grape 3

上の場合では、’apple’ と’banana’ の値は、共に HashDB[2] に格納されることになります。このような状態を衝突 (collision) と呼びます。

ハッシュ表では、十分に大きなハッシュ表を作れば、衝突の発生頻度は下げられますが、原理的に回避することはできません。衝突が発生したとき、データを消さないようにする仕組みが必要になります。

連鎖法 衝突を起こしても、線形リストにつないで値を格納する
開番地法 衝突が発生したとき、ハッシュ表の空いている位置を探して格納する

上記、以外にもハッシュ法のサイズを伸長して、衝突の発生頻度を下げるなど、各種の工夫が行われています。

11.5. 結論：ありがたく辞書を使おう¶

Python は、ハッシュ表に基づく高性能な辞書をユーザに提供してくれています。よほどのことがない限り、自分で辞書を開発する必要はありません。むしろ、使いこなせるようにならないと、プログラミングの神様からバチが当たりますよ。

[8]:

DataBase = {
    'apple': 120,
    'banana': 100,
    'orange': 100,
    'pineapple': 50,
    'grape': 300,
}
print(DataBase['grape']) #300 と 表 示 さ れ る

覚えておきたい主な辞書(d)の操作

コード	説明
`d = {}`	空の辞書を生成し、d という名前にする
`d[key]`	`key` に対する値をえる (key がない場合はエラー)
`d.get(key,v)`	`key` に対する値をえる (`key` がない場合は `v` を使う)
`key in d`	辞書内`d`に `key` が存在するかどうか?
`d[key]=v`	`key` に対応する値`v`をセットする
`len(d)`	辞書 `d` の大きさ(キーの数) をえる
`d.keys()`	辞書 `d` のキーのリストをえる

11.6. 演習問題¶

集計処理やバケット法を使う問題を集めてみました。

課題リストより

塩基対: 辞書で解いて見ましょう
投票
鏡餅
Not Found
多数決: 辞書を使いましょう
怪文書
K種類以下のボール

Python Programming 2021 ドキュメント