- 目標値
- 対象のブロック
- 比較中
- 除外
- 発見
ジャンプ探索
ジャンプ探索は線形探索と二分探索の中間にあたります。整列済みのリストをm個ずつジャンプしながら進み、各ブロックの最後の値だけを調べて、最後の値が目標値より小さくないブロックに着いたら止まります。そしてそのブロックを先頭から走査します。探す値とジャンプ幅を選び、ジャンプと走査にそれぞれ何回の比較がかかるか見てみましょう。 「再生」で探索を見るか、「ステップ」と「戻る」で比較を1回ずつ進めます。ステップスライダーをドラッグすると好きな位置に移動できます。破線は探す値を示し、網掛け部分は対象のブロックです。ジャンプ探索には整列済みのリストが必要なので、整列されていないリストは先に整列します。探す値、ジャンプ幅、棒の数を選ぶか、数値を自分で入力できます。ボードを選択中は、矢印キーで1ステップ移動、スペースキーで再生と一時停止、Home と End で最初と最後に移動します。
使い方
- 探す値、ジャンプ幅、棒の数を選びます。数値を自分で入力することもでき、その場合は先に整列されます。
- 「再生」を押すか、「ステップ」と「戻る」で比較を1回ずつ進めます。ステップスライダーをドラッグすると、探索の好きな位置に移動できます。
- 棒40本でジャンプ幅2と8を試し、比較回数を√nのときと比べてみましょう。
ジャンプ探索のしくみ
整列済みのリストをm個ずつのブロックに分けます。最初のブロックの最後の値を見ます。それが目標値より小さければ、目標値はそのブロックのどこにもないので、次のブロックの末尾へジャンプしてまた見ます。ブロックの最後の値が小さくなくなったら、目標値はそのブロックにしかありえません。ブロックの先頭に戻り、目標値が見つかるか、それを通り過ぎるまで値を1つずつ調べます。
ジャンプ幅の選び方
値がn個のとき、ジャンプには最大n/m回、走査には最大m回の比較がかかります。ジャンプ幅が小さいと走査は短いもののジャンプが多くなり、大きいとその逆になります。合計n/m + mはm = √nのとき最小で、比較は約2√n回です。40個なら最大13回で、線形探索の40回、二分探索の6回と比べられます。ジャンプ探索は1ブロックより多く戻ることがないので、データを後ろへたどるのが遅い場合に役立ちます。
よくある質問
ジャンプ探索はどのように動きますか?
整列済みのリストをm個ずつ先へジャンプし、各ブロックの最後の値を調べます。その値が目標値より小さくなくなったら、目標値はそのブロックにしかありえないので、ブロックを先頭から走査します。
最適なジャンプ幅は?
√nを丸めた値です。ジャンプには最大n/m回、走査には最大m回の比較がかかり、その和は両者が等しいm = √nのとき最小になります。最悪の場合の比較は約2√n回です。
ジャンプ探索は二分探索より速いですか?
いいえ。二分探索のほうが比較が少なく、約log₂ n回に対してジャンプ探索は約2√n回です。それでも、データを後戻りするコストが高い場合はジャンプ探索が有利になりえます。後戻りは1回、あるブロックの先頭までだけだからです。
同じ値が複数あるときはどれが見つかりますか?
最初のものです。飛ばすブロックはどれも目標値より小さい値で終わるので、それより前のブロックに一致する値はなく、走査はブロックの先頭から始まります。
入力した数値はどこかに送信されますか?
いいえ。探索はブラウザ内で実行され、最後の設定はこのブラウザのローカルストレージに保存されます。
試してみますか?
ブラウザで PictorX を開きます。インストール不要、始めるのにクレジットカードも不要です。
エディターへ