感謝のプログラミング 10000時間

たどり着いた結果(さき)は、感謝でした。

線形探索のコストを抑える番兵法

<スポンサーリンク>

番兵法って何?

「探索する値」と全く同じ値を、配列の一番後ろに置く探索の方法を番兵法という。
番兵とは、そのとき格納する「探索する値と全く同じ値」のこと。

では、なんで番兵なんて置くのか?というと、線形探索で前から順番に走査するときに、以下のように、
「これが配列の最後なの?」
「このインデックスの値は探している値と一致してる?」
と毎回2つのif文を通してチェックしていることがわかる。

while (true) {
    if (i == size) {
        return -1;
    }
    if (array[i] == target) {
        return i;
    }
    i++;
}

番兵は、この

while (true) {
    if (i == size) {
        return -1;
    }

の、ここのif文をいちいちやらなくていいようにするために使われる。
なお、線形探索のサンプルは、以下の記事を参考にしてほしい。

番兵法を図にするとこんな感じ。
f:id:sho322:20131218223126j:plain
NUBoard
CANSAY NUboard

サンプルを作ってみる。

package algorithm.search;

import java.util.Random;

public class SequentialSearch {
    public static int seqSearch(int[] array, int target) {
        int i = 0;
        int size = 0;
        if (array != null) {
            size = array.length;
        } else {
            return -1;
        }
        
        while (true) {
            if (i == size) {
                return -1;
            }
            if (array[i] == target) {
                return i;
            }
            i++;
        }
    }

    public static int seqSearchBanpei(int[] array, int max, int key) {
        int i = 0;
        array[max] = key;
        
        while (true) {
            if (array[i] == key) {
                break;
            }
            i++;
        }
        return i == max ? -1 : i;
    }
    public static void main(String[] args) {
        int max = 10;
        int keyNum = 7;
        int[] array = new int[max + 1];
        Random rnd = new Random();
        
        //max分配列に値をつっこむ
        for (int i = 0; i < max; i++) {
            array[i] = rnd.nextInt(10);
        }
        
        System.out.println("配列の値は・・・");
        for (int j : array) {
            System.out.print(j + ",");
        }
        System.out.println();
        long start = System.nanoTime();
        int index = seqSearchBanpei(array, max, keyNum);
        long end = System.nanoTime();
        if (index != -1) {
            System.out.println("探したかった数字→" + keyNum + " は" + (index + 1) + "番目にあります!");
            System.out.println("array[" + index + "]→" + array[index]);
        } else {
            System.out.println("探してた数字→" + keyNum + "はねぇよ");
        }

        //数が少ない場合はlong t1 = System.nanoTime();を使った方がいい
        System.out.println("かかった時間は・・・:" + (end - start) + "ナノ秒");
    }
}

実行した結果は以下の通りになる。

配列の値は・・・
8,4,2,3,9,9,7,2,3,3,0,
探したかった数字→7 は7番目にあります!
array[6]→7
かかった時間は・・・:6569ナノ秒

参考にした本

明解 Javaによるアルゴリズムとデータ構造

明解 Javaによるアルゴリズムとデータ構造