【超基本】初心者に贈るアルゴリズム論 ～探索法～
スポンサーリンク
はじめに
こんにちは。talosです。
今回から数回に分けてアルゴリズムについて説明します。
プログラミングを始めたばかりの人は勉強しておきましょう。
今回は「逐次探索」、「ソート済みデータの逐次探索」、「m-ブロック法」、「2分探索法」、「ハッシュ法」の5つの探索法について説明します。
探索法はデータ集合の中から特定のデータを探索する方法です。
データ量が増えれば増えるほど、アルゴリズムごとの計算時間の差は顕著になります。
膨大なデータを取り扱う現代において、いかに効率よく探索を行うかは重要な課題と言えるでしょう。
それでは順番に探索法を説明していきます。
逐次探索
逐次探索は配列の先頭から順に見ていく方法です。
探索するデータが配列にある場合は、最善の場合は1回、最悪の場合n回で見つけることができます。
つまり計算時間はO(n)であると言えます。
（O記法については「計算量オーダーについて - Qiita」でわかりやすく説明されています。）
実装例を下に示します。
def sequential_search(array, x): path = '' for num in array: path += '->' + str(num) if num == x: print(path) return 1 print(path) return 0 # 探索対象のリスト array = [10, 43, 54, 92, 69, 11, 9, 23, 29, 6, 88, 19, 94, 3] # 探索する値 x1 = 9 if sequential_search(array, x1): print('発見！') else: print('発見できず...') # output # ->10->43->54->92->69->11->9 # 発見！ # 探索する値 x2 = 12 if sequential_search(array, x2): print('発見！') else: print('発見できず...') # output # ->10->43->54->92->69->11->9->23->29->6->88->19->94->3 # 発見できず...
ご覧の通り、配列を先頭から見ていき見つかれば終了、見つからなければ末尾まで探索しています。
存在しないデータを探し続けるのってばかばかしいですよね。
そこで次の探索法を紹介します。
ソート済みデータの逐次探索
ソートをすることで、探しているデータが存在しないときは早めに切り上げることができます。
昇順にソートして先頭から見ていくと、探しているデータより大きいデータが見つかった時点で、それ以降に探しているデータが存在しないことがわかります。
ただ、若干計算時間が減りますが、O(n)のままです。
実装例を下に示します。
def sequential_search_sort(array, x): path = '' for num in array: path += '->' + str(num) if num >= x: break print(path) if num == x: return 1 else: return 0 # 探索対象のリスト array = [10, 43, 54, 92, 69, 11, 9, 23, 29, 6, 88, 19, 94, 3] # ソート済みリスト array_sort = sorted(array) # [3, 6, 9, 10, 11, 19, 23, 29, 43, 54, 69, 88, 92, 94] # 探索する値 x1 = 9 if sequential_search_sort(array_sort, x1): print('発見！') else: print('発見できず...') # output # ->3->6->9 # 発見！ # 探索する値 x2 = 12 if sequential_search_sort(array_sort, x2): print('発見！') else: print('発見できず...') # output # ->3->6->9->10->11->19 # 発見できず...
m-ブロック法
m-ブロック法は、ソートされた配列をm個のブロックに分けてから探索することで計算時間を減らします。
具体例を用いて説明します。
次のような配列array[n]があるとします。
これをm=4個のブロックに分けます。
（ブロック長はk=ceil(n/m)とします）
各ブロックの最大値と見つけたいデータxを比較します。
ただし、最後のブロックは他のブロックよりもブロック長が短い可能性があるので行いません。
（行おうとすると配列の外を参照してしまうことになります）
このとき、左から順に探索しブロックの最大値よりxが小さいところが現れたら、そのブロック以外にはxがないことがわかります。
ここでx=69とすると、初めて「ブロックの最大値 > x」となるのはブロック2なので、xがあるとするならばブロック2だと判断します。
そうしたら、ブロック2の先頭から逐次探索をします。
3回目で発見できたので終了します。
それでは実装例を下に示します。
def m_block_search(array, x, m, k): path = '' # ブロック番号 j = 0 while j <= m - 2: path += '->' + str(array[(j + 1) * k - 1]) if x <= array[(j + 1) * k - 1]: break else: j += 1 i = j * k t = min((j + 1) * k - 1, len(array) - 1) while(i < t): path += '->' + str(array[i]) if x <= array[i]: break else: i += 1 if(i == t): path += '->' + str(array[i]) print(path) if x == array[i]: return 1 else: return 0 import math # 探索対象のリスト array = [10, 43, 54, 92, 69, 11, 9, 23, 29, 6, 88, 19, 94, 3] # ソート済みリスト array_sort = sorted(array) # [3, 6, 9, 10, 11, 19, 23, 29, 43, 54, 69, 88, 92, 94] # ブロック数 m = 4 # ブロック長 k = math.ceil(len(array)/m) # 探索する値 x1 = 9 if m_block_search(array_sort, x1, m, k): print('発見！') else: print('発見できず...') # output # ->10->3->6->9 # 発見！ # 探索する値 x2 = 12 if m_block_search(array_sort, x2, m, k): print('発見！') else: print('発見できず...') # output # ->10->29->11->19 # 発見できず... # 探索する値 x3 = 94 if m_block_search(array_sort, x3, m, k): print('発見！') else: print('発見できず...') # output # ->10->29->88->92->94 # 発見！ # 探索する値 x4 = 95 if m_block_search(array_sort, x4, m, k): print('発見！') else: print('発見できず...') # output # ->10->29->88->92->94 # 発見できず...
比較回数は最大で、「データが存在しているブロックを探す回数m+ブロック内を探す回数n/m」なので、
比較回数≦m+n/m
と表せます。
相加平均と相乗平均の関係より、上記の右辺が最小になるのはm=n/mが成り立つとき、すなわちm=√nのときです。
これを右辺に代入すると、
比較回数≦2√n
となるので計算時間はO(n)となります。
2分探索法
2分探索法は、見つけたいデータが真ん中より左にあるか、右にあるかを繰り返すことで、探索範囲を絞っていく方法です。
毎回探索範囲が半分になっていくので、計算時間はO(n)です。
実装例を下に示します。
def binary_search(array, x): if x < array[0] or x > array[len(array) - 1]: return 0 left = 0 right = len(array) - 1 while True: mid = int((left + right) / 2) print(str(left) + '(' + str(array[left]) + ')', str(mid) + '(' + str(array[mid]) + ')', str(right) + '(' + str(array[right]) + ')') if x < array[mid]: right = mid - 1 else: left = mid + 1 if left > right: print( str(right) + '(' + str(array[right]) + ')') break if x == array[right]: return 1 else: return 0 import math # 探索対象のリスト array = [10, 43, 54, 92, 69, 11, 9, 23, 29, 6, 88, 19, 94, 3] # ソート済みリスト array_sort = sorted(array) # [3, 6, 9, 10, 11, 19, 23, 29, 43, 54, 69, 88, 92, 94] # 探索する値 x1 = 9 if binary_search(array_sort, x1): print('発見！') else: print('発見できず...') # output # 0(3) 6(23) 13(94) # 0(3) 2(9) 5(19) # 3(10) 4(11) 5(19) # 3(10) 3(10) 3(10) # 2(9) # 発見！ # 探索する値 x2 = 12 if binary_search(array_sort, x2): print('発見！') else: print('発見できず...') # output # 0(3) 6(23) 13(94) # 0(3) 2(9) 5(19) # 3(10) 4(11) 5(19) # 5(19) 5(19) 5(19) # 4(11) # 発見できず... # 探索する値 x3 = 94 if binary_search(array_sort, x3): print('発見！') else: print('発見できず...') # output # 0(3) 6(23) 13(94) # 7(29) 10(69) 13(94) # 11(88) 12(92) 13(94) # 13(94) 13(94) 13(94) # 13(94) # 発見！ # 探索する値 x4 = 95 if binary_search(array_sort, x4): print('発見！') else: print('発見できず...') # output # 発見できず...
ハッシュ法
ハッシュ法は、ハッシュ関数を使用してデータをハッシュテーブルに蓄え、探索するときもハッシュ関数を使用して探す方法です。
具体例を用いて説明します。
配列のサイズの2倍のサイズを持つハッシュhtbを用意します。
そして、配列内のデータを順にハッシュ関数に通してハッシュ値jを計算し、hab[j]にデータを格納します。
hash(x)=x mod 28
としています。
modは除算時の余りを計算する関数で、28はハッシュテーブルのサイズです。
すでにj番目にデータが格納されているときは、右隣（ハッシュテーブルの末尾の次は先頭）に格納します。
格納するときと同じ方法で探索することができます。
そこになければ右へ右へと移っていきます。
もしなにも格納されていない場所を参照してしまったときは、探しているデータは存在しないということになります。
それでは実装例を下に示します。
def hash_method(htb, x): path = '' hash_size = len(htb) j = x % hash_size while htb[j] != 0 and htb[j] != x: path += '->' + str(j) + '(' + str(htb[j]) + ')' j = (j + 1) % hash_size path += '->' + str(j) + '(' + str(htb[j]) + ')' print(path) if htb[j] == x: return 1 else: return 0 def make_table(array): hash_size = len(array) * 2 htb = [0] * (hash_size) for num in array: j = num % hash_size while htb[j] != 0: # ハッシュテーブルのサイズを超えないようにmod hash_size j = (j + 1) % hash_size htb[j] = num return htb import math # 探索対象のリスト array = [10, 43, 54, 92, 69, 11, 9, 23, 29, 6, 88, 19, 94, 3] # ハッシュテーブル htb = make_table(array) # [0, 29, 0, 3, 88, 0, 6, 0, 92, 9, 10, 11, 94, 69, 0, 43, 0, 0, 0, 19, 0, 0, 0, 23, 0, 0, 54, 0] # 探索する値 x1 = 9 if hash_method(htb, x1): print('発見！') else: print('発見できず...') # output # ->9(9) # 発見！ # 探索する値 x2 = 12 if hash_method(htb, x2): print('発見！') else: print('発見できず...') # output # ->12(94)->13(69)->14(0) # 発見できず... # 探索する値 x3 = 94 if hash_method(htb, x3): print('発見！') else: print('発見できず...') # output # ->10(10)->11(11)->12(94) # 発見！ # 探索する値 x4 = 95 if hash_method(htb, x4): print('発見！') else: print('発見できず...') # output # ->11(11)->12(94)->13(69)->14(0) # 発見できず...
ハッシュ法はほぼ定数時間で探索を終えることができます。
したがって、探索時間はO(1)です。
参考
