「大人の教養・知識・気付き」を伸ばすブログ

一流の大人(ビジネスマン、政治家、リーダー…)として知っておきたい、教養・社会動向を意外なところから取り上げ学ぶことで“気付く力”を伸ばすブログです。目下、データ分析・語学に力点を置いています。今月(2022年10月)からは多忙につき、日々の投稿数を減らします。

MENU

Pythonで学ぶアルゴリズム(09/18)

 アルゴリズムを学ぶのにPythonの学習も兼ねて

を参照していく。

5. データの探索

5.4 ヒープ構造

 ヒープ構造はデータの最小値・最大値を知りたいときに便利な構造である。先頭に最小値・最大値があることが分かれば、計算量を削減することができる。ヒープ構造は完全二分木で表現される。

5.4.1 ヒープの更新

 ヒープから最小値を取り出すことを考える。最小値は根にあるからこれを取り出せばよく、この際の計算量は\mathcal{O}(1)である。このとき木の形が崩れるため、修復する問題を考える。
 まず最後の要素を根に移動する。親子間の大小関係を修正すべく、子ノードと根のうち小さい方と交換することを続けていく。このヒープの更新は、頂点の数をnとすれば長さは\log n程度である。そのため最悪の場合でも大小関係の矛盾を解決するためのステップが根から葉まで到達すればよいから、\mathcal{O}(\log n)と言える。

5.4.2 ヒープの利点

 ヒープは木で表現されるものの配列を用いて実装することができる。ヒープの各ノードに順番を付与することでそれをそのまま配列の添字にすることができる。ヒープの計算量はヒープの更新とその後のヒープ利用の2つのステップの合計からなる。ヒープ更新の計算量は最終的に\mathcal{O}(n)で与えられる。他方でヒープの更新は要素1個につき\mathcal{O}(\log n)かかるため、総計で\mathcal{O}(n\log n)である。後者の計算量の方が影響力が強いため、ヒープソートの総計算量は\mathcal{O}(n\log n)と見積もることができる。

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 ハッシュを用いた検索

 定数時間(\mathcal{O}(1))で探索が可能なデータ構造を扱うべく、\mathrm{Python}の辞書型を導入する。

5.4.1 Pythonの辞書型

 \mathrm{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.3 ハッシュ関数の性質

 ハッシュ関数は任意長のビット列から規則性のない固定長のビット列を生成する関数のことである。\mathrm{hash}関数は引数に指定したオブジェクトのハッシュ値を返す。

  • オブジェクトに対応した整数値を返す。
  • オブジェクトが同じならば同一のハッシュ値を返す*1
5.4.4 ハッシュテーブルの構造

 データのハッシュ値を探索に利用するのがハッシュテーブルである。ハッシュテーブルはデータの探索を高速で行うためのデータ構造である。ハッシュ値が分かればデータがどこにあるかがすぐに分かる。そのためハッシュテーブルの探索に掛かる計算量はデータのサイズに依存せず\mathcal{O}(1)である。
 ただし課題が3点あり、これらを克服しなければならない:

  • \mathrm{hash}関数が返すハッシュ値の値は相当広く、格納には長大なリストが必要になる。
  • ハッシュ値は負値を取り得るため、そのままリストの添字に使うことは出来ない。
  • 異なるオブジェクトが同じハッシュ値を取る可能性がある
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')
5.4.6 ハッシュテーブルとサイズ

 ハッシュテーブルを用いる場合、異なるオブジェクトのハッシュ値が同一値を取る場合があり得る、
 64\mathrm{bit}の整数を返すハッシュ関数であっても2^{64}\approx2^4\times 10^{3*6}=8.0\times10^{18}=20億Gバイトが必要となり、家庭用\mathrm{PC}では実用性が著しく低い水準となる。また実際にそれだけのバイト数を確保したとしても、そのうちの大半には値が格納されないため、メモリを無駄に取ることとなる。したがって単純に多数の値を取れるようにメモリを確保すればよいという訳ではない。
 ただし現代のプログラミング言語はこの問題を自動的に解消してくれるため、普段はあまり気にしなくて良い。

*1:ただし違うオブジェクトが同じハッシュ値を返す可能性はある。

プライバシーポリシー お問い合わせ