似非プログラマーの雑多な日記

似非プログラマーの雑多な日記

「継続は力なり」の実証実験してます

線形探索を高速化する【番兵】

アルゴリズムとデータ構造に関して学んだことの備忘録。
今回は「番兵」を用いて線形探索を高速化する方法。

1. 線形探索とは

線形探索は、あるデータが、あるデータ群の中に含まれているかを先頭のデータから順に調べる方法である。
プログラミングでは一般的に配列に対して用いられ、配列の先頭の要素から順に、目的の値と等しいかどうかを調べる。

線形探索の例

処理速度を測りたいためある程度の長さの配列に対して下記の条件で試す。

  • 配列の長さ(要素数)は500
  • 配列は自然数1-100の数字を持つ
  • 目的の数字は99
  • 目的の数字はできるだけ要素番号の大きい方に置く

#include <iostream>
using namespace std;
int main(){
    int array[500] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 20, 19, 18, 17, 16, 15, 14, 13, 12, 11, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 
                      40, 39, 38, 37, 36, 35, 34, 33, 32, 31, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 60, 59, 58, 57, 56, 55, 54, 53, 52, 51, 
                      61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 80, 79, 78, 77, 76, 75, 74, 73, 72, 71, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 
                      100, 100, 98, 97, 96, 95, 94, 93, 92, 91,1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 20, 19, 18, 17, 16, 15, 14, 13, 12, 11, 
                      21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 40, 39, 38, 37, 36, 35, 34, 33, 32, 31, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 
                      60, 59, 58, 57, 56, 55, 54, 53, 52, 51, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 80, 79, 78, 77, 76, 75, 74, 73, 72, 71, 
                      81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 100, 100, 98, 97, 96, 95, 94, 93, 92, 91,1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 
                      20, 19, 18, 17, 16, 15, 14, 13, 12, 11, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 40, 39, 38, 37, 36, 35, 34, 33, 32, 31, 
                      41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 60, 59, 58, 57, 56, 55, 54, 53, 52, 51, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 
                      80, 79, 78, 77, 76, 75, 74, 73, 72, 71, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 100, 100, 98, 97, 96, 95, 94, 93, 92, 91,
                      1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 20, 19, 18, 17, 16, 15, 14, 13, 12, 11, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 
                      40, 39, 38, 37, 36, 35, 34, 33, 32, 31, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 60, 59, 58, 57, 56, 55, 54, 53, 52, 51, 
                      61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 80, 79, 78, 77, 76, 75, 74, 73, 72, 71, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 
                      100, 100, 98, 97, 96, 95, 94, 93, 92, 91,1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 20, 19, 18, 17, 16, 15, 14, 13, 12, 11, 
                      21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 40, 39, 38, 37, 36, 35, 34, 33, 32, 31, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 
                      60, 59, 58, 57, 56, 55, 54, 53, 52, 51, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 80, 79, 78, 77, 76, 75, 74, 73, 72, 71, 
                      81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 100, 99, 98, 97, 96, 95, 94, 93, 92, 91};

    int target = 99; // 目的の数字
    string result = "NO";

    for(int i = 0; i < 500; i++){
        if(array[i] == target){
            result = "YES";
            break;
        }
    }

    cout << result << endl;
}

上記は単純な線形探索の例を示した。次に説明する「番兵」を用いることで処理速度を上げることができる。

2. 番兵とは

番兵は、ループの制御を簡略化する目的などで使われる方法である。番兵を用いると通常の線形探索の定数倍の速度向上が期待できるらしい。
番兵を線形探索で実装する場合は、探索対象の配列の末尾に目的の要素を追加する。上の例題の場合は配列の末尾に99を追加することになる。

なぜ高速化が期待できるのか

ポイントは「メインのループ処理における比較演算の数」である。
例のように通常の線形探索を行なった場合は、forループの終了条件と目的の値との比較の2つの演算が必要であるが、番兵を用いて実装した場合は、while文の終了条件1つで済む(番兵によってwhile分が必ず終了することが担保されているため)

1.の例を番兵で試してみる。

#include <iostream>
using namespace std;
int main(){
    // 番兵を置くことを前提としているため明示的に500+1としている、固定長配列はあとから追加できないから。
    int array[500+1] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 20, 19, 18, 17, 16, 15, 14, 13, 12, 11, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 
                        40, 39, 38, 37, 36, 35, 34, 33, 32, 31, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 60, 59, 58, 57, 56, 55, 54, 53, 52, 51, 
                        61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 80, 79, 78, 77, 76, 75, 74, 73, 72, 71, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 
                        100, 100, 98, 97, 96, 95, 94, 93, 92, 91,1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 20, 19, 18, 17, 16, 15, 14, 13, 12, 11, 
                        21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 40, 39, 38, 37, 36, 35, 34, 33, 32, 31, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 
                        60, 59, 58, 57, 56, 55, 54, 53, 52, 51, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 80, 79, 78, 77, 76, 75, 74, 73, 72, 71, 
                        81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 100, 100, 98, 97, 96, 95, 94, 93, 92, 91,1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 
                        20, 19, 18, 17, 16, 15, 14, 13, 12, 11, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 40, 39, 38, 37, 36, 35, 34, 33, 32, 31, 
                        41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 60, 59, 58, 57, 56, 55, 54, 53, 52, 51, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 
                        80, 79, 78, 77, 76, 75, 74, 73, 72, 71, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 100, 100, 98, 97, 96, 95, 94, 93, 92, 91,
                        1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 20, 19, 18, 17, 16, 15, 14, 13, 12, 11, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 
                        40, 39, 38, 37, 36, 35, 34, 33, 32, 31, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 60, 59, 58, 57, 56, 55, 54, 53, 52, 51, 
                        61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 80, 79, 78, 77, 76, 75, 74, 73, 72, 71, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 
                        100, 100, 98, 97, 96, 95, 94, 93, 92, 91,1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 20, 19, 18, 17, 16, 15, 14, 13, 12, 11, 
                        21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 40, 39, 38, 37, 36, 35, 34, 33, 32, 31, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 
                        60, 59, 58, 57, 56, 55, 54, 53, 52, 51, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 80, 79, 78, 77, 76, 75, 74, 73, 72, 71, 
                        81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 100, 99, 98, 97, 96, 95, 94, 93, 92, 91};

    int target = 99; // 目的の数字

    int i = 0;
    array[500] = target; // 番兵 // 配列番号は0から始まるから最後尾は100+1ではないことに注意
    while(array[i] != 99){
        i++;
    }

    if(i != 500){
        cout << "YES" << endl;
    }else{
        cout << "NO" << endl;
    }
}

番兵を使って実装するとこんな感じ。実際は可変長配列を使うのが普通だろうが、簡単にするために固定長配列にした。

3. まとめ

timeコマンドを使って速さを計測したけど長さ500程度の配列じゃ差はなかったwww
もしかしたら実装の方法に問題があるのかもしれないので、使いどころ含め学習を続ける

以上