必要なデータを探し出すことは、コンピュータ以前の古くからの問題である。
そのため、開発者は効率的にデータを取得するために、多くの検索アルゴリズムを作成している。
検索アルゴリズムは、逐次検索と区間検索の2つに大別される。
逐次探索はデータ構造中の各要素をチェックする。
インターバル検索は、データのさまざまな点（インターバルと呼ばれる）をチェックし、ソートされたデータセットがある場合、項目を見つけるのにかかる時間を短縮します。
この記事では、Pythonのジャンプ検索（ソートされた配列に対する順次検索と区間検索のハイブリッドな組み合わせ）について説明します。
ジャンプ検索
ジャンプ検索では、ソートされたデータの配列を、ブロックと呼ばれる要素の部分集合に分割する。
各ブロックの検索候補を比較することで、検索キー（入力値）を見つける。
配列はソートされているので、検索候補はブロックの中で最も大きな値である。
検索キーと検索候補を比較するとき、アルゴリズムは次の3つのうち1つを行うことができます。
- 検索候補が検索キーより小さければ、後続のブロックをチェックする
- 検索候補が検索キーより大きい場合、現在のブロックに対して線形探索を行う。
- 探索候補が探索キーと同じなら、その候補を返す
ブロックの大きさは，配列の長さの平方根として選ばれる．したがって，長さ n の配列のブロックサイズは √n となります．これは，平均的にほとんどの配列で最高の性能を発揮するためです．
どのように動作するかを説明するのに便利かもしれません。
以下は、ジャンプ検索が9つの要素からなる配列の中の値78をどのように検索するかを示しています。
上の例では、線形探索の部分で2回のチェックがあるため、5回のステップで要素を見つけることができます。
このように、ジャンプ・サーチがどのように機能するかは理解できたので、次にこのアルゴリズムの疑似コード実装を見てみましょう。
ジャンプ検索ステップ
入力
- サイズ
nの配列/リストAを入力とする。 - 検索キー
item
出力
出力: * 検索キーにマッチしたインデックス、または item が見つからない場合は -1 を出力する。
S
実装
ジャンプ検索の仕組みを理解した上で、Pythonで実装してみましょう。
'''
Jump Search function
Arguments:
A - The source list
item - Element for which the index needs to be found
'''
import math
def jump_search(A, item):
print("Entering Jump Search")
n = len(A) # Length of the array
m = int(math.sqrt(n)) # Step length
i = 0 # Starting interval
while i != len(A)-1 and A[i] < item:
print("Processing Block - {}".format(A[i: i+m]))
if A[i+m-1] == item: # Found the search key
return i+m-1
elif A[i+m-1] > item: # Linear search for key in block
B = A[i: i+m-1]
return linear_search(B, item, i)
i += m
B = A[i:i+m] # Step 5
print("Processing Block - {}".format(B))
return linear_search(B, item, i)
jump_search()関数は 2 つの引数を取ります。
第 1 引数には評価対象のソートされたリスト、第 2 引数には探す必要のある要素を指定します。
ブロックサイズを求めるには、math.sqrt()関数を用います。
反復はwhile条件によって容易になり、増分はi += m` によって実現されます。
ステップ4bとステップ5では、linear_search()関数が呼び出されていることにお気づきかと思います。
この linear_search() 関数は、以下のいずれかのシナリオで起動されます。
-
Step 4b– 比較対象がずれたとき。ブロック/ウィンドウの最後の要素がitemよりも大きい場合、linear_search()がトリガーされます。 -
Step 5– ソースリストAのうち、ブロックに収まらない残りの要素は、派生リストとしてlinear_search()関数に渡されます。
linear_search()` 関数は以下のように記述することができる。
'''
Linear Search function
Arguments:
B - The derived list
item - Element for which the index needs to be found
loc - The Index where the remaining block begins
'''
def linear_search(B, item, loc):
print(" Entering Linear Search")
i = 0
while i != len(B):
if B[i] == item:
return loc+i
i += 1
return -1
ステップ5では、元のリストの残りの要素が派生リストとして linear_search() 関数に渡される。
比較は、派生リスト B の各要素に対して行われる。
派生リストのマッチしたインデックスがソースブロックのインデックスに追加され、ソースリストにおけるその要素の正確なインデックス位置が提供されます。
もしマッチする要素がなければ、 item が見つからなかったことを示すために -1 を返します。
完全なスニペットはここで見ることができる。
ベンチマーク – ジャンプサーチとリニアサーチの比較
Jump SearchのランタイムをLinear Searchと比較することができます。
次の図は、ソートされた配列の末尾に近い要素を検索する際のアルゴリズムのパフォーマンスを示しています。
バーが短いほど、優れています。
リストの要素数が増えるにつれて、ジャンプ探索は線形探索アルゴリズムより速くなります。
ビッグ・オー解析
ジャンプ検索がどのように機能するか、より一般的な分析をしてみましょう。
ここではもう一度、見つけるべき要素がリストの最後にあるという最悪のシナリオを考えてみます。
n個の要素からなるリストとm個のブロックサイズに対して、ジャンプ検索は理想的にはn/m回のジャンプを実行することになります。
ブロックサイズを√nと考えると、実行時間もO(√n)` となります。
このことから、ジャンプ探索は実行複雑度 O(n) の線形探索（最悪）と実行複雑度 O(log n) の二項探索（最高）の中間に位置することになります。
したがって、バイナリサーチが実行不可能で、線形サーチではコストがかかりすぎるような場所で、ジャンプサーチを使うことができます。
結論
この記事では、ジャンプ検索アルゴリズムの基本を説明しました。
次に、Pythonで実装する前に、擬似コードでJump Searchがどのように動作するかを調べました。
その後、Jump Searchがどのように動作するか、またその理論的な速度制限を分析しました。