第5回 - CSV形式の読み込み、ハッシュテーブルの原理

1. PythonでCSV形式を読み込む
   • 演習 5-1. CSVファイルの読み込み
   • 演習 5-2. 郵便番号データベースを読み込む
   • for文のもうひとつの使い方
   • 文字列のスライス
   • 演習 5-3. 文字列のスライス
   • 文字列の検索
2. ハッシュテーブルとは
   • 逐次探索
   • 逐次探索・改
   • 演習 5-4. 逐次検索・改を実行する
   • ハッシュテーブル
   • 演習 5-5. ハッシュテーブルの計算量
3. ブレイクアウトルーム練習
   • 演習 5-6. 文字列の検索
4. 本日の課題
   • 小課題5. ハッシュ関数の実装 (1月24日締切)
   • チャレンジ課題B. 交差迷路の生成 (1月31日締切)

雑談

IT業界における女性の社会進出はとくに遅れている: 米国における統計

1980年代になにが起こったのか? 「パソコン」の登場である。 当時、パソコンは「男の子向けのオモチャ」という位置づけで販売されていた:

• Commodore 64 CM (米国)
• TRS-80 CM (米国)
• SEGA SC-3000H CM (日本)
• SHARP X1F CM (日本)

この傾向は、消費者に対してある一定のメッセージを送っている。

Saturday Morning Breakfast Cereal (漫画)

1. 男の子向けのオモチャ: 「メカブロックスだよ! 何通りにも組み合わせができて遠隔操作できるんだ!」
2. 女の子向けのオモチャ: 「人形だよ!」
3. 後年… 「なんでこの業界はみんな野郎ばっかりなんだ?」

しかし、女性でもコンピュータ・サイエンスのパイオニアは存在する:

• Ada Lovelace - 世界初のプログラマとも言われる。 蒸気で動くコンピュータ (解析機関、未完成) のために ベルヌーイ数を計算するプログラムを書いた。
• Grace Hopper - 米国海軍准将のプログラマ。「バグ」という言葉を広めたとされる。
• Margaret Hamilton - NASAで アポロ11号の飛行制御プログラムの開発責任者。

1. PythonでCSV形式を読み込む

CSV (Comma Separated Values、カンマ区切り値) 形式とは、テキスト形式の一種で、 カンマによって区切られた値を並べたものである。 まず、テキストファイルの各行は表の一行 (row) に相当する。 さらに各行のなかのカンマで囲まれた部分を カラム (column、列または欄) または フィールド (field) という。 空白や特殊な文字が入ったフィールドはさらに "〜" で囲まれる。 また CSVファイルは、Microsoft Excel で開くことができる:

Alice,USA,22
Bob,UK,25
"Yusuke Shinyama",Japan,13

エクセルで上の CSVファイルを開くと、以下のような表が表示される:

日本語のCSVをPythonでリスト(のリスト)として読み込むには、 以下のようにする:

import csv
with open("ファイル名", encoding="utf-8") as fp:
    変数名 = list(csv.reader(fp))

Python で上の CSV ファイルを読み込むと、 以下のような「リストのリスト」になっている:

[['Alice', 'USA', '22'], ['Bob', 'UK', '25'], ['Yusuke Shinyama', 'Japan', '13']]

# CSVファイルを読み込む。
import csv
with open("KEN_ALL_ROME.CSV", encoding="utf-8") as fp:
    table = list(csv.reader(fp))
# 表を1行(row)ずつ処理する。
for row in table:
    print(row)

1.1. for文のもうひとつの使い方

演習 5-2. のプログラムを実行すると、以下のような内容が表示される:

['0600000', '北海道', '札幌市\u3000中央区', '以下に掲載がない場合', 'HOKKAIDO', 'SAPPORO SHI CHUO KU', 'IKANIKEISAIGANAIBAAI']
['0640941', '北海道', '札幌市\u3000中央区', '旭ケ丘', 'HOKKAIDO', 'SAPPORO SHI CHUO KU', 'ASAHIGAOKA']
['0600041', '北海道', '札幌市\u3000中央区', '大通東', 'HOKKAIDO', 'SAPPORO SHI CHUO KU', 'ODORIHIGASHI']
...
(Control + C を押して止める。)

このプログラムの中で、次の部分に着目しよう:

# 表を1行(row)ずつ処理する。
for row in table:
    print(row)

これまではリストの要素をひとつずつ表示するのに、 以下のようにしていた:

a = [5,9,4,0]
for i in range(len(a)):
    x = a[i]
    print(x)

a = [5,9,4,0]
for x in a:
    print(x)

これらは同じ原理にもとづいている。 range(n) 関数は、 [0, 1, 2, ..., n-1] というリスト (のようなもの) を返す。 したがって、

for i in range(n):
    ....

1.2. 文字列のスライス

Python では、 リストと同じく、文字列もスライスが可能である。

s = "HEADACHE"

この場合、sのスライスは、以下のようになる:

1.3. 文字列の検索

文字列に対してスライスが使えると、 ある文字列の中に含まれる部分文字列の検索をおこなうことができる。 これは、検索したい文字列をスライドさせながら各位置と比較することでおこなう:

# ある文字列に含まれる部分文字列を発見する。
s = "VACATION"  # 検索対象の文字列
t = "CAT"       # 含まれる文字列
for i in range(6):  # 0〜5
    if s[i:i+3] == t:
        print("found", i)

2. ハッシュテーブルとは

演習 5-2. でやった問題をふたたび考える。 郵便番号を入力すると、その住所を表示するプログラムを作りたい。

$ python postal.py 1520001
東京都目黒区中央町

このように、ある情報 (e.g. 郵便番号) を別の情報 (e.g. 住所) に関連づける処理は、 業務用コンピュータの代表的な利用例である。数学的には、 これは2つの集合 K から V への写像 K → V として定義される。 このとき、集合 K の要素を 「キー (key)」、集合 V の要素を 「バリュー (value)」と呼ぶ。

• 成績管理システム: 学籍番号 → 氏名、履修科目、点数
• 商品管理システム: 商品名 → メーカー、価格、在庫数
• チケット予約システム: 予約番号 → 氏名、場所、日時、人数
• ...

2.1. 逐次探索

今回の例では郵便番号 (row[0]) がキー、 住所 (row[1]+row[2]+row[3]) がバリューということになる。 これを使ってプログラム postal.py を改造すると、以下のようになる:

# CSVファイルを読み込む。
import csv
with open("KEN_ALL_ROME.CSV", encoding="utf-8") as fp:
    table = list(csv.reader(fp))
# 郵便番号 (キー) を取得する。
import sys
key = sys.argv[1]
# 表を1行ずつ処理する。
for row in table:
    if row[0] == key:
        # キーが一致したら、それに対応するバリューを表示する。
        value = row[1]+row[2]+row[3]
        print(value)

郵便番号データは 12万行以上あるので、 逐次探索をすると毎回 (最悪) 12万回のループを実行することになり、 効率が悪い。n件のデータに対して、O(n) の計算量が必要である。

二分探索を使えば、最悪 O(log n) の計算量ですむが、 データをあらかじめキーが昇順になるようにソートしておく必要がある。 またキーを新しく追加・更新するたびに正しく並べ直さなければならない。

2.2. 逐次探索・改

郵便番号は 0〜9 の数字から始まるので、 まずキーを「最初の1文字」で分類し、10個のリストに分割するという手がある。

# まず 10個の (空のリストからなる) リストを作成。
index = [[], [], [], [], [], [], [], [], [], []]
for row in table:
    key = row[0]
    value = row[1]+row[2]+row[3]
    # キーの0文字目を数値に直す。
    i = int(key[0])
    # i番目のリストにキーとバリューの組を追加する。
    a = index[i]
    a.append([key, value])

ここで作られたリストのリストを「索引」あるいは 「インデックス (index)」とよぶ。 インデックスを使って検索をする処理 lookup() は以下のようになる:

def lookup(index, key):
    # キーの0文字目を数値に直す。
    i = int(key[0])
    # i番目のリストをとりだす。
    a = index[i]
    # そのリストに対して逐次探索をおこなう。
    for pair in a:
        # 一致するキーとバリューの組をとりだす。
        k = pair[0]
        v = pair[1]
        if k == key:
            return v
    # 見つからなかったら、空の文字列を返す。
    return ""

最後に、この関数を呼び出す:

import sys
key = sys.argv[1]
value = lookup(index, key)
print(value)

この例では、最初のインデックスを作成するのに ある程度の時間がかかるので、全体の実行時間はそれほど速くならないが、 検索時間だけをみると、このようにリストを10個に分割すれば 時間は約 1/10 に短縮されると思われる、が…

2.3. ハッシュテーブル

上の方法のインデックスをより一般化したものが ハッシュテーブル (hash table) である。 これはインデックス作成時にキーの最初の1文字を使うかわりに、 ハッシュ関数 (hash function) が返す値を使う。 ハッシュ関数とは、任意の文字列をなんらかの値 (ハッシュ) に 変換するような関数である:

• h("7038258") = 0
• h("7320001") = 15731
• h("4420029") = 602
• ...

ハッシュ関数 h(x) はどんな関数でもよいが、 同じ文字列に対してはつねに同じ値を返すように設計しなければならない。 また、2つの異なる文字列ができるだけ異なる値になるように 設計することが望ましい。一般的なハッシュ関数の例として考えられるのは、 与えられたキー (文字列) に含まれる文字コードをすべて足す、 などの方法である。

ハッシュ関数ができたら、これを使って何番目のリストを使うべきか決定する。 全体的な流れは以下のようになる:

1. まず k個のリストを用意する。
2. ハッシュ関数 h(x) が、与えられた文字列 x を整数に変換する。
3. インデックス作成時および検索時には、(h(x) % k) 番目の リストを使用する。

ひとたびハッシュテーブルができれば、 関数 lookup() は従来とほぼ同じ方法で検索がおこなえる:

def lookup(index, key):
    k = len(index)
    # キーをハッシュに変換し、k の剰余をとる。
    i = h(key) % k
    # i番目のリストをとりだす。
    a = index[i]
    # そのリストに対して逐次探索をおこなう。
    for pair in a:
        # 一致するキーとバリューの組をとりだす。
        k = pair[0]
        v = pair[1]
        if k == key:
            return v
    # 見つからなかったら、空の文字列を返す。
    return ""

ハッシュテーブルの検索時間は二分探索ほど速くないが、 キーの追加や変更の処理が簡単なため広く利用されている。 また、ハッシュテーブルによる検索時間は k の値に調整できるところも有利である。

一般的に、ハッシュテーブルを使うと現実の検索時間は短縮されるが、 その計算量はたかだか 1/k になるだけである。 この k は定数であるので、Big-O 記法で表した計算量は変わらない。

前節の「郵便番号の最初の数字を 0 〜 9 の整数に変換する」処理は、ある意味 ハッシュ関数の一例であるが、郵便番号にしか使えないし、ハッシュの値は 0 から 9 までに固定されている。さらに、得られる値が一様に分布していない。 どのような文字列に対しても一様に分布するハッシュ関数を 設計するのは意外に難しく、これは現在でもさかんに研究されている テーマのひとつである。ちなみに最悪のハッシュ関数とは、 どんな文字列に対しても同じ値を返す関数である。 これではすべての文字に対して同じリストを使うことになってしまい、 事実上、逐次探索と変わらない:

# 最悪のハッシュ関数
def h(x):
    return 123

ハッシュ関数の応用

ハッシュ値はどんなデータに対しても適用できる。 これを応用したものが電子署名で、あるデータのハッシュ値を使って、 そのデータが改竄されていないかチェックするものである。 ここでは、ハッシュ関数の以下のような特性を利用している:

1. もし2つのハッシュ値が違っていれば、元のデータ (キー) は確実に違っている。
2. 元のデータ (キー) が違っていても、2つのハッシュ値が違うとは限らない。 偶然に同じハッシュになるということもありうる。(ただし、その可能性は非常に小さい。)
3. ハッシュ関数として、 暗号学的ハッシュ関数 と呼ばれるものを使っており、これはたとえハッシュ値がわかっても 元のデータを容易に推測できないようになっている。

ハッシュ関数の別の応用としてビットコインに代表される ブロックチェーン技術があるが、 ここでは触れない。

3. ブレイクアウトルーム演習

ブレイクアウトルーム演習の方法:

1. ブレイクアウトルーム中はカメラを使うこと。
2. まず自己紹介をする。名前・所属・趣味などを簡単に説明する。
3. 最初の問題をやる担当者が PC の画面共有をおこない、課題のプログラムを考えながら書く。 このとき周囲の人は手助けする。
4. 終わったら、次の担当者が次の問題をやる。これを繰り返す。
5. 全部終わったら、適当に雑談する (← これが本当の目的)。

4. 本日の課題

# キーに対応したハッシュを計算する関数 h を定義する。
def h(key):
    return 123

# 検索をおこなう関数 lookup を定義する。
def lookup(index, key):
    # キーをハッシュに変換し、k の剰余をとる。
    i = h(key) % 100
    # i番目のリストをとりだす。
    a = index[i]
    # そのリストに対して逐次探索をおこなう。
    for pair in a:
        # 一致するキーとバリューの組をとりだす。
        k = pair[0]
        v = pair[1]
        if k == key:
            return v
    # 見つからなかったら、空の文字列を返す。
    return ""

# 郵便番号の一覧を読み込む。
import csv
with open("KEN_ALL_ROME.CSV", encoding="utf-8") as fp:
    table = list(csv.reader(fp))

# 100個の (空のリストからなる) リストを作成。
index = []
for i in range(100):
    index.append([])

# このリストを使ったハッシュテーブルを作成する。
for row in table:
    key = row[1]+row[2]+row[3]  # キー: 住所
    value = row[0]              # バリュー: 郵便番号
    # キーをハッシュに変換する。
    i = h(key) % 100
    # i番目のリストにキーとバリューの組を追加する。
    a = index[i]
    a.append([key, value])

# 指定された住所から郵便番号を検索し、実行時間を計測する。
import sys
key = sys.argv[1]
import time
t0 = time.time()  # 最初の時刻 (秒数) を取得する。
# 郵便番号を検索する (時間計測のため、1000回繰り返している)。
for i in range(1000):
    value = lookup(index, key)
t1 = time.time()  # 最後の時刻 (秒数) を取得する。
# 見つかった郵便番号を表示する。
print(value)
# かかった時間を表示する。
print(t1 - t0)