を参照していく。
前回
5. データの探索
5.4 ヒープ構造
ヒープ構造はデータの最小値・最大値を知りたいときに便利な構造である。先頭に最小値・最大値があることが分かれば、計算量を削減することができる。ヒープ構造は完全二分木で表現される。
5.4.1 ヒープの更新
ヒープから最小値を取り出すことを考える。最小値は根にあるからこれを取り出せばよく、この際の計算量はである。このとき木の形が崩れるため、修復する問題を考える。
まず最後の要素を根に移動する。親子間の大小関係を修正すべく、子ノードと根のうち小さい方と交換することを続けていく。このヒープの更新は、頂点の数をとすれば長さは
程度である。そのため最悪の場合でも大小関係の矛盾を解決するためのステップが根から葉まで到達すればよいから、
と言える。
5.4.2 ヒープの利点
ヒープは木で表現されるものの配列を用いて実装することができる。ヒープの各ノードに順番を付与することでそれをそのまま配列の添字にすることができる。ヒープの計算量はヒープの更新とその後のヒープ利用の2つのステップの合計からなる。ヒープ更新の計算量は最終的にで与えられる。他方でヒープの更新は要素1個につき
かかるため、総計で
である。後者の計算量の方が影響力が強いため、ヒープソートの総計算量は
と見積もることができる。
import random import heapq def heap_sort(array): heap = [] for v in array: heapq.heappush(heap, v) return [heapq.heappop(heap) for i in range(len(heap))] my_array = [random.randint(0, 100) for i in range(15)] print(my_array) heap_sort(my_array)
5.4 ハッシュを用いた検索
定数時間()で探索が可能なデータ構造を扱うべく、
の辞書型を導入する。
5.4.1 Pythonの辞書型
の辞書型はキーとなる値と格納する値とのペアを保持するデータ型である。
################################ ### 辞書型でデータを格納する ### ################################ # 空の辞書型を作る my_dic = {} my_dic['taro'] = 10 my_dic[2] = [1,2,3] print(my_dic) # 格納したデータの修正 my_dic['taro'] = 30 # 値の更新 my_dic[2].append(25) # 2つ目に登録したリストに値を追加 print(my_dic) # 辞書型のキーとして格納できるかはhash()がエラーを返すかで分かる hash('taro') # 問題が無ければ整数が返ってくる
5.4.4 ハッシュテーブルの構造
データのハッシュ値を探索に利用するのがハッシュテーブルである。ハッシュテーブルはデータの探索を高速で行うためのデータ構造である。ハッシュ値が分かればデータがどこにあるかがすぐに分かる。そのためハッシュテーブルの探索に掛かる計算量はデータのサイズに依存せずである。
ただし課題が3点あり、これらを克服しなければならない：
5.4.5 ハッシュテーブルの実装
このような課題を
######################## ### ハッシュテーブル ### ######################## class HashTable: def __init__(self, table_size = 100): self.data = [[] for i in range(table_size)] self.n = table_size # オブジェクトのハッシュ値を計算 def get_hash(self, v): return hash(v) % self.n def search(self, key): i = self.get_hash(key) for j, v in enumerate(self.data[i]): if v[0] == key: return (i,j) return (i, -1) def set(self, key, value): i,j = self.search(key) if j != -1: # 既に存在する値を書き換える self.data[i][j][1] = value else: self.data[i].append([key,value]) def get(self, key): i, j = self.search(key) if j != -1: return self.data[i][j][1] raise KeyError(f'{key} was not found in this Hashtable !') my_hash_table = HashTable() my_hash_table.set('taro', 10) my_hash_table.get('taro')
