2013-03-07

「アルゴリズムを、はじめよう」ハッシュ探索法をPythonで書く(データ格納編)

「アルゴリズムを、はじめよう」をPythonで書く第三弾。第一弾の線形探索法のアルゴリズムはこちら。第二弾の二分探索法のアルゴリズムはこちら。

アルゴリズムを、はじめよう

第6章:ハッシュ探索法のアルゴリズム(データの格納)

12,25,36,20,30,8,42という数字を要素11個の配列に格納する。ハッシュ関数は、ArrayD % 11。


#!/usr/bin/env python
#-*- coding: utf-8 -*-

def insert():
    arrayD = [12, 25, 36, 20, 30, 8, 42]
    arrayH = [0] * 11
    for d in arrayD:
        k = d % 11
        max = len(arrayH)
        count = 0
        while count < max:
            if arrayH[k] == 0:
                arrayH[k] = d
                break
            else:
                k += 1
                if k >= max - 1:
                    k = 0
                    count += 1
    print arrayH

if __name__ == '__main__':
    insert()

だんだん合っているかどうか自身が無くなってきた。間違いや改善方法など、何でもご意見いただければ嬉しいです。

ちなみに既にデータが入っていて衝突(collision)が起こった場合に別の場所を探す方法をオープンアドレス法と呼び、その中でも1ずつ隣が空いているか探していって、空いている段階で格納する方法を線形走査法と呼ぶらしいです。

オープンアドレス法以外にもチェイン法というのがあるらしいです。

こういう事は「アルゴリズムを、はじめよう」には全く書いてありませんでしたので、この本は本当にアルゴリズムの基本中の基本だけを書いているということでしょう。

ここまでシンプルに基礎だけを書いてあるからこの本は分かりやすいのでしょう。なかなか自分の知っている事で書いた方が分かりやすいし、正確になるという事でも、対象読者のレベルを考えてあえて削るって難しいんですよね。

それがうまくできているのでアルゴリズムの勉強を始める初心者向けの本としては素晴らしいと思います。

0 件のコメント:

コメントを投稿