Python検索アルゴリズムのブロック別検索アルゴリズムの実装
3889 ワード
一、ブロック別検索アルゴリズム
ブロック別検索は、二分割検索と順序検索の改善方法であり、ブロック別検索は、インデックステーブルが規則化されており、ブロック内のノードに対して順序付けが要求されていない。ブロック内のノードは、秩序化されていてもよく、無秩序であってもよい。
ブロック別検索とは、大きな線形表をいくつかのブロックに分解し、各ブロックのノードは任意に格納することができるが、ブロックとブロックの間で順序付けが必要である。同時に、各ブロックの最大値をインデックステーブルのインデックス値として作成します。このインデックステーブルはブロック順に補助配列に保存する必要があります。検索する場合は、まずインデックステーブルで検索して、検索するノードのあるブロックを決定します。インデックステーブルは並べ替えされているので、インデックステーブルの検索は順序検索または二分割検索を使用することができます。その後、対応するブロックの中で逐次的に検索すると、対応する結点が見つかる。
例えば、23、43、56、78、97、100、120、135、147、150の列があります。下図のように：
検索したいデータは150です。ブロック別検索を使用するステップは以下の通りです。
ステップ1：上の図のデータをブロック分けし、ブロック長4でブロック分けし、ブロック分けは下図のようにします。
説明：各ブロックの長さは任意に指定されており、ブロガーがここで使用する長さは4であり、読者は自分の必要に応じて各ブロックの長さを指定することができる。
ステップ2：各ブロックの中の最大のキーワードを選択してインデックステーブルを構成し、すなわち図に示す各ブロックの最大値を選択し、第一のブロックの最大値は78、第二のブロックの最大値は135、第三のブロックの最大値は155となり、インデックステーブルは下の図のようになる。
ステップ3：データ150を検索したいと判断する順序検索または二分割検索では、上記の図に示すインデックステーブルのどの内容において、ここでは二分割ルックアップ法を使用していますか？すなわち、先に中間値135を取って150と比較して、下記の図に示すように、
ステップ4：結果として、中間位置のデータ135はターゲットデータ150より小さいので、対象データ135の次のブロックにある。3ブロック目にデータを位置決めし、この時に3ブロック目のデータを取り出して、順序比較を行います。
ステップ5：第3のブロックの内容を逐次検索することによって、やっと9番目の位置で目標数を見つけました。このとき、ブロック分け検索は終了します。
まとめ：これで、ブロック分けのアルゴリズムはもう説明済みです。二分割ルックアップ法と逐次ルックアップ法との比較によって、サブブロックルックアップの速度は二分割ルックアップアルゴリズムには及ばないが、順序検索アルゴリズムよりずっと速い。データが多く、ブロックが大きい場合は、インデックステーブルに対して二分割検索を採用することができ、検索の速度をさらに高めることができます。
二、例：ブロック分割検索アルゴリズムを実現する
具体的なコードは以下の通りです。
上記の運転結果から、150を検索すると、上記のステップに完全に一致します。
ここでPython検索アルゴリズムのブロック分け検索アルゴリズムの実現についての記事を紹介します。Pythonのブロック別検索アルゴリズムの内容については、以前の記事を検索したり、次の関連記事を見たりしてください。これからもよろしくお願いします。
ブロック別検索は、二分割検索と順序検索の改善方法であり、ブロック別検索は、インデックステーブルが規則化されており、ブロック内のノードに対して順序付けが要求されていない。ブロック内のノードは、秩序化されていてもよく、無秩序であってもよい。
ブロック別検索とは、大きな線形表をいくつかのブロックに分解し、各ブロックのノードは任意に格納することができるが、ブロックとブロックの間で順序付けが必要である。同時に、各ブロックの最大値をインデックステーブルのインデックス値として作成します。このインデックステーブルはブロック順に補助配列に保存する必要があります。検索する場合は、まずインデックステーブルで検索して、検索するノードのあるブロックを決定します。インデックステーブルは並べ替えされているので、インデックステーブルの検索は順序検索または二分割検索を使用することができます。その後、対応するブロックの中で逐次的に検索すると、対応する結点が見つかる。
例えば、23、43、56、78、97、100、120、135、147、150の列があります。下図のように：
検索したいデータは150です。ブロック別検索を使用するステップは以下の通りです。
ステップ1：上の図のデータをブロック分けし、ブロック長4でブロック分けし、ブロック分けは下図のようにします。
説明：各ブロックの長さは任意に指定されており、ブロガーがここで使用する長さは4であり、読者は自分の必要に応じて各ブロックの長さを指定することができる。
ステップ2：各ブロックの中の最大のキーワードを選択してインデックステーブルを構成し、すなわち図に示す各ブロックの最大値を選択し、第一のブロックの最大値は78、第二のブロックの最大値は135、第三のブロックの最大値は155となり、インデックステーブルは下の図のようになる。
ステップ3：データ150を検索したいと判断する順序検索または二分割検索では、上記の図に示すインデックステーブルのどの内容において、ここでは二分割ルックアップ法を使用していますか？すなわち、先に中間値135を取って150と比較して、下記の図に示すように、
ステップ4：結果として、中間位置のデータ135はターゲットデータ150より小さいので、対象データ135の次のブロックにある。3ブロック目にデータを位置決めし、この時に3ブロック目のデータを取り出して、順序比較を行います。
ステップ5：第3のブロックの内容を逐次検索することによって、やっと9番目の位置で目標数を見つけました。このとき、ブロック分け検索は終了します。
まとめ：これで、ブロック分けのアルゴリズムはもう説明済みです。二分割ルックアップ法と逐次ルックアップ法との比較によって、サブブロックルックアップの速度は二分割ルックアップアルゴリズムには及ばないが、順序検索アルゴリズムよりずっと速い。データが多く、ブロックが大きい場合は、インデックステーブルに対して二分割検索を採用することができ、検索の速度をさらに高めることができます。
二、例：ブロック分割検索アルゴリズムを実現する
具体的なコードは以下の通りです。
def search(data, key): #
length = len(data) #
first = 0 #
last = length - 1 #
print(f" :{length} :{data}") #
while first <= last:
mid = (last + first) // 2 #
if data[mid] > key: #
last = mid - 1 # last
elif data[mid] < key: #
first = mid + 1 # first
else:
return mid #
return False
#
def block(data, count, key): # ，data ，count ，key
length = len(data) #
block_length = length // count #
if count * block_length != length: #
block_length += 1 # 1
print(" ", block_length, " ") #
print(" ：")
for block_i in range(block_length): #
block_data = [] #
for i in range(count): #
if block_i * count + i >= length: # ，
break #
block_data.append(data[block_i * count + i]) #
result = search(block_data, key) #
if result != False: # False
return block_i * count + result #
return False
data = [23, 43, 56, 78, 97, 100, 120, 135, 147, 150, 155] #
result = block(data, 4, 150) # ，
print(" :", result) #
上記の運転結果から、150を検索すると、上記のステップに完全に一致します。
ここでPython検索アルゴリズムのブロック分け検索アルゴリズムの実現についての記事を紹介します。Pythonのブロック別検索アルゴリズムの内容については、以前の記事を検索したり、次の関連記事を見たりしてください。これからもよろしくお願いします。