リニアサーチに番兵を付けると

最近、id:nowokay/@kis さんのアルゴリズムの勉強のしかた - きしだのはてな (Sep 22, 2011) という記事に触発されて、プログラミングの基本のようなところに興味が湧いてきました。具体的には、アルゴリズムというものを、かつてまともに勉強したことがなかったので、そのあたりから始めたいと思っています。

紹介されていた書籍のうち、最初の Java データ構造とアルゴリズム基礎講座 (長尾和彦著技術評論社 2009 ISBN978-4-7741-3697-4) は、早速読んでみました。そのことは簡単にやらずに来てしまったアルゴリズムの勉強 (Oct 11, 2011) にも書いたとおりです。

続いて紹介されていたのは、@hyuki さんの数学ガール乱択アルゴリズム (結城浩著ソフトバンククリエイティブ 2011 ISBN978-4797-36100-1) です。いま、この本を読んでいます。

この中で、「番兵付きリニアサーチ」というものが紹介されていました。「数学ガール」で取り上げられるくらいなので、高校数学をまじめに修了した人なら誰でも知っていることなのかもしれませんが、わたしには初耳のアルゴリズムでした。ちょっと便利そうな気がしたので、手元で実験してみました。ちなみに、アルゴリズムの勉強のためには、いい加減にそろそろ C 言語の勉強を始めるべきなんじゃないかという気がしていますが、今回の実験に使った言語は、ごめんなさい、相変わらず Java です。 orz

以下のようなコードを書いてみました。

package tt4cs.beginner;

import java.util.Date;

public class LinearSearch {
  
  public static int[] getData(int n) {
    if (n < 0)
      throw new IllegalArgumentException();
    int[] data = new int[n];
    for (int i = 0; i < n; i++)
      data[i] = (int)(Math.random() * n);
    return data;
  }
  
  public static int search0(int[] data, int wanted) {
    int i = 0;
    while (i < data.length) {
      if (data[i] == wanted)
        return i;
      i++;
    }
    return -1;
  }
  
  public static int search1(int[] data, int wanted) {
    int i = 0;
    try {
      while (data[i] != wanted) {
        i++;
      }
      return i;
    } catch (IndexOutOfBoundsException e) {
      return -1;
    }
  }
  
  public static void main(String[] args) {
    
    // Initialization
    int[] data = getData(1000000);
    int idx = -1;
    long t0, t1;
    
    // Use of search0
    t0 = new Date().getTime();
    for (int i = 0; i < 1000; i++)
      idx = search0(data, 123456);
    t1 = new Date().getTime();
    System.out.println("Index: " + idx);
    System.out.println("Elapsed time: " + (t1 - t0) + " msec");
    
    // Use of search1
    t0 = new Date().getTime();
    for (int i = 0; i < 1000; i++)
      idx = search1(data, 123456);
    t1 = new Date().getTime();
    System.out.println("Index: " + idx);
    System.out.println("Elapsed time: " + (t1 - t0) + " msec");
    
  }
  
}

リニアサーチの対象となる数列の個数を 1,000,000 個としていますが、これよりも桁を増やすと OutOfMemoryError を惹き起こしてしまいます。かといって、そのままでは、1 ミリ秒以内に処理が終わってしまうことも多いので、同じリニアサーチを 1,000 回繰り返すことにしています。

メソッド search0 がふつうのリニアサーチなら、メソッド search1 が番兵付きリニアサーチである、というつもりです。後者では、既存の配列の大きさをいじって最後尾に番兵を配置するのは容易でない (その処理だけで余計な時間的ロスが発生する気がする) ので、番兵の代わりに IndexOutOfBoundsException をキャッチするという、少々荒っぽいことをしてみました。

上記のコードの結果は、10 回やってみて、たとえば次のとおりでした。所要時間の単位はミリ秒です。

	search0 所要時間	search1 所要時間
1 回目	184	140
2 回目	653	495
3 回目	645	487
4 回目	1,816	1,465
5 回目	806	618
6 回目	1,836	1,463
7 回目	1,862	1,465
8 回目	1,817	1,467
9 回目	994	758
10 回目	1,315	1,011

大雑把に言うと、search0 よりも search1 のほうが、所要時間は 20% から 25% 程度は短いようです。これは、数学ガールで取り上げられていた事例にも、だいたい合致します。

もしや、どちらのメソッドを先に実行するかで違いが出るのだろうかと思いまして、先に search1 を実行して、その次に search0 を実行してみましたが、やはり結果は、search0 よりも search1 のほうが速かったです。

ということで、ごくごく簡単ながら、きょうは、サンプル数が十分に多い場合は、番兵付きリニアサーチは処理速度の向上に役立つかもしれないということがわかって、ちょっとうれしかったです。

ところで、最後に少し脱線しますが、番兵という言葉を聞くと、わたしはどうしても番人という言葉のほうを思い浮かべてしまいます。番人と言えば、やはり「PRIDE の番人 (PRIDE's gatekeeper)」でしょうか。格闘技に関心のある人であれば誰でも名前を聞いたことはあると思いますが、ゲーリー・グッドリッジ (Gary Goodridge) さんが、かつてそのように呼ばれていました。最近、まったく消息を聞かなくなりましたが、お元気なのでしょうか。

ちなみに、脱線から戻りますと、番兵付きリニアサーチと言うときの番兵は、英語では gatekeeper ではなく sentinel だそうです。センティネルと言うと、どちらかというと、映画「マトリックス」に現れる偵察ロボットのほうを想像してしまいます。あんなものが空中を浮遊している世界で生身の人間が生き延びなければならないなんて、おっそろしいことだなあと思いましたよ。おっと、やっぱり、脱線してしまいました。