ハッシュ表と連結リスト
- 《関連記事》__str__
K&R で紹介された事例をもとに、組み込み型 dict と同等の機能を提供するために必要な、ハッシュ表と連結リストを実現します。
class HashTable:
hashsize = 5 # = 101
none = NoneList()
def __init__(self, none=none):
self.hashtab = [none]*self.hashsize
def __str__(self):
return "%s(%s)"%(
self.__class__.__name__, self.hashtab)
クラス HashTable は（前述した、クラス Htable/配列 hashtab を参考にして）ハッシュ表の特性を規定します。インスタンス属性 hashtab は、hashsize 個の連結リストを保持するとともに、各リストは同じハッシュ値を持つ要素群を保持します。
メソッド __str__ は、組み込み関数 str の動作を規定して、オブジェクトに固有の「非公式な」文字列表現を得ます。クラス属性 __name__ を参照すると、クラス名を変更したときの影響を最小限に止められます。
class LinkedList:
def __init__(self, next=None, key=None, value=None):
self._next = next
self.key = key
self.value = value
def __repr__(self):
s = ""
for k, v in self.items():
s += "%r: %r, "%(k, v)
return "<%s>"%s[:-2]class NoneList(LinkedList):
def __str__(self): return ""
クラス LinkedList は（前述した、クラス Nlist/構造体 nlist を参考にして）連結リストの特性を規定します。任意の要素対 key/value とともに、次の要素対 next を保持します。
クラス NoneList は、連結リストの「末尾」の特性を規定します。要素対を持たないので、どのメソッドも単純に実現できます。他の記事で、if 文の呪縛から逃れる術として、Null Object を紹介しました。ここでも、その手法を踏襲します。
メソッド __repr__ は、組み込み関数 repr の動作を規定して、オブジェクトに固有の「公式な」文字列表現を得ます。可能なら「同じオブジェクトを生成するのに有効なコード」を表わす文字列が得られるようにします。そうでなければ、括弧 <> の中に、オブジェクトに固有の「非公式な」文字列表現を記述します。ここでは、連結リストの各項目を、コロンで区切った形式「キー:値」で表現します。
メソッド __str__ は、組み込み関数 str の動作を規定して、オブジェクトに固有の「非公式な」文字列表現を得ます。
class HashTable:
def __len__(self):
return reduce(
lambda acc, e: acc+len(e), self.hashtab, 0)class LinkedList:
def __len__(self):
return reduce(
lambda acc, e: acc+1, self.items(), 0)class NoneList(LinkedList):
def __len__(self): return 0
メソッド __len__ は、組み込み関数 len の動作を規定します。ハッシュ表に含まれる要素数を獲得します。クラス HashTable では、インスタンス属性 hashtab が保持する各連結リストに含まれる要素数 len(e) を累積して、その値をリターン値とします。クラス LinkedList では、その中に含まれる要素数をリターン値とします。クラス NoneList では、要素を持たないので、0 をリターン値とします。ここで、OOP の特徴のひとつである、ポリモフィズムの思想を体現しています。
ためしてごらん
>>> p = HashTable()
>>> p
HashTable([<>, <>, <>, <>, <>])
>>> len(p)
0
空のハッシュ表 HashTable() を生成して、結果を出力します。このとき、ハッシュ表 p の文字列表現が使われます。すると、要素を持たないので、空の連結リスト <> をカンマ「,」で区切って出力します。また、要素数 len(p) は 0 になります。
>>> p = HashTable()
>>> s = "CABDECEADEAEADE"
>>> for e in s: p.add(e)
>>> p
HashTable([<'A': 4>, <'B': 1>, <'C': 2>, <'D': 3>, <'E': 5>])
>>> len(p)
5
ハッシュ表 p の文字列表現を使って、指定した文字列 s を構成する、各文字とその出現頻度を出力します。すると、連結リストの文字列表現 <'E': 5> から、文字 'E' を 5 個含むことが分かります。また、要素数 len(p) は 5 になります。
>>> p = HashTable()
>>> s = "now is the time for all good men to come to the aid of their party"
>>> for e in s.split(" "): p.add(e)
>>> p
HashTable([<'party': 1, 'their': 1, 'come': 1, 'men': 1, 'good': 1, 'is': 1, 'now': 1>, <'time': 1, 'the': 2>, <'aid': 1, 'to': 2, 'for': 1>, <'of': 1, 'all': 1>, <>])
>>> len(p)
14
ハッシュ表 p の文字列表現を使って、p.139 の例文を構成する、各単語とその出現頻度を出力します。すると、連結リストの表現 <..., 'the': 2> から、定冠詞 'the' を 2 個含むことが分かります。また、要素数 len(p) は 14 になります。
《ひよ子のきもち♪2007/12/06》
