ジャンプ探索

ジャンプ探索は、目次のない本でページを探すやり方と同じです。ある程度まとめてページをめくりながらページ番号をちらっと見て、行き過ぎたら最後のまとまりを1ページずつ戻ります。整列済みのリストなら、すべての値を調べるよりずっと少ない比較で済みます。

ブロックに分けられた整列済みの棒の列。飛ばしたブロックの最後の棒は薄く、目標値がありうるブロックは網掛けになっている
ブロックに分けられた整列済みの棒の列。飛ばしたブロックの最後の棒は薄く、目標値がありうるブロックは網掛けになっている

考え方

整列済みのリストでは、ブロックの最後の値を見れば、目標値がそのブロックにありうるかどうかがわかります。それが目標値より小さければ、ブロック内の値はすべて小さいからです。だから中を見る必要はありません。各ブロックの最後の値を順に調べてブロックごと飛ばし、目標値より小さくない値に出会ったら止まります。目標値はそのブロックにしかありえないので、先頭から走査します。

例

2, 5, 8, 12, 16, 23, 38, 56, 72, 91 から23を、3個ずつのブロックで探します。最初のブロックの最後は8で、小さいので飛ばします。2番目のブロックの最後は23で、小さくないので、23は12, 16, 23の中にしかありえません。走査すると12、16、そして23で、比較5回で見つかります。線形探索なら6回、二分探索なら3回です。40を探す場合は、ブロックの最後の値8、23、72を見てブロック38, 56, 72に進みます。38は小さく、56はもう大きいので、40はありません。これも比較5回です。

なぜ√nか

ブロックがm個ずつなら、正しいブロックを見つけるのに最大約n/m回、それを走査するのに最大m回の比較がかかります。少ない長いジャンプでは走査が長くなり、多い短いジャンプではジャンプが長くなります。和n/m + mは2つが等しいm = √nのとき最小で、約2√nになります。40個ならブロックは6個ずつで比較は最大13回、100万個ならブロックは1,000個ずつで比較は約2,000回です。

使いどころ

二分探索のほうが比較は少なく、約log₂ n回です。しかし二分探索はリストのあちこちを行ったり来たりするのに対し、ジャンプ探索は前に進むだけで、戻るのは1回、あるブロックの先頭までです。そのため、テープ上のデータや、戻るのが遅い連結構造のデータに向いていました。Ben Shneidermanは1978年にこれをjump searchingとして記述しました。√n個のブロックに分けるという同じ考え方は平方分割(square-root decomposition)と呼ばれ、ほかの多くのアルゴリズムにも登場します。

ベン・シュナイダーマン(左)とキャサリン・プレザン、2012年のWebshopにて。シュナイダーマンは1978年にジャンプ探索を述べた。
ベン・シュナイダーマン(左)とキャサリン・プレザン、2012年のWebshopにて。シュナイダーマンは1978年にジャンプ探索を述べた。

試してみよう

アプリを開き、「探す値」で値を選んで「ステップ」を押します。ジャンプのたびにブロックの最後の値が強調され、飛ばしたブロックは薄くなり、目標値がありうるブロックは走査の間網掛けになります。棒40本で「ジャンプ幅」を√nから2や8に変え、ジャンプと走査のバランスがどう変わるか見てみましょう。

よくある質問

ジャンプ探索の時間計算量は?

√n個ずつのブロックでO(√n)、比較は最大約2√n回です。追加メモリはO(1)で、整列済みのリストが必要です。

ジャンプ探索と二分探索の違いは?

二分探索は毎回残りを半分にし、比較は約log₂ n回ですが、行ったり来たりします。ジャンプ探索は一定の幅で前へ飛び、1つのブロックを走査します。比較は約2√n回で、戻るのは1回だけです。

最後のブロックの走査に二分探索を使えますか?

はい。ブロックを二分探索で調べると、走査の比較はm回から約log₂ m回に減ります。ジャンプには引き続きn/m回かかるので、その場合はブロックを大きくしたほうが得です。

ジャンプ探索には整列済みのリストが必要ですか?

はい。ブロックを飛ばしても安全なのは、最後の値が小さければブロック内の値がすべて小さいからです。アプリは整列されていないリストを先に整列します。

試してみますか?

ブラウザで PictorX を開きます。インストール不要、始めるのにクレジットカードも不要です。

ジャンプ探索を試す