導入

第9回より「データ構造とアルゴリズム」という大きなテーマの中から、4つのトピックをとりあげています。

• 配列とコレクション
• ソート
• サーチ
• 再帰

今回はその第3回目として「サーチ」を学習しましょう。前回のソートで数多くのデータを順番に並べ替える手段を学習しました。サーチはデータの集合の中から目的の要素を探し出す手段です。前回のソートを学習し終えた方ならば、今回の学習内容は手強い相手ではありません。きっちり乗り越えていきましょう。

展開

サーチとは

サーチ（Search）とは、複数のデータの中から特定のデータを見つけ出す作業のことです。日本語では探索や検索と呼びます。

サーチのアルゴリズムには、ランダムなデータを取り扱えるものと、ソート済みのデータを取り扱うものとがあります。

サーチは大変広い成果のある項目で、概略であってもここで紹介するには大変な量です。そこで、今回はサーチの中でもリストサーチ（list search）に限って取り扱います。データのリスト構造とはA, B, C, ……のように、データが次々と連続している構造のことを言います。代表例は配列です。配列では、ある特定のデータを指し示すために添字を用います。一般的なリスト構造では、添字が必須条件ではありません。最も単純なリストは「次のデータのありかを示す情報」があれば成り立ちます。さて、そのようなリスト構造を持つデータの集合を探索するためのアルゴリズムを、ここではリストサーチと呼びます。以降、サーチと言えば、このリストサーチを指すことにします。

代表的なサーチアルゴリズム

サーチを行うアルゴリズムの例として次のものが挙げられます。

• 線形探索法
• 二分探索法
• ハッシュテーブルを利用した探索法

線形探索法

線形探索という言葉は英語のLinear Searchの直訳です。データの集合を先頭要素から、目的の値と逐一比較します。何の工夫もありませんが、確実に目的の値の有無を探索します。順次探索（Sequential Search⁠）⁠、逐次探索（Serial Search）などとも呼ばれます。

線形探索の計算量はO(n)です。データの要素数に比例して増加します。何と言ってもコードがシンプルですから要素数が少なければ活用したいアルゴリズムです。ソートされていないデータの集合に対しても使用できるメリットがあります。

その昔、プログラミング言語が大変貧弱だった頃、配列の要素から目的の値をサーチするには注意が必要でした。プログラム実行中に、配列の要素数を超える大きさの添字を使用すると、プログラムが意図しない動きをするのです。これを防ぐため、サーチが配列の終端で確実に終わるように、目的の値と同じ値や、データとして決してあり得ない値の要素をデータの終端に追加し、これを番兵（Sentinel）と呼ぶテクニックを使ったものでした。今となっては、ほとんどの高級言語が配列であれコレクションであれ要素数を簡単に取得できるため、番兵というテクニックの出番もまれになりました。

線形探索のアルゴリズムを実装したsketchは次のとおりです。

// 線形探索   Linear Search
// 番兵無し   No Sentinel

final int    NUMBER_OF_RANDOM_DATA = 500;
final String DATA_FILE_NAME        = "RandomData.txt";
final int    DIAMITER              = 5;
final int    SEARCHING_VALUE       = 37;

ArrayList<Integer> nums = new ArrayList<Integer>();
int i = 0; // サーチ回数。drawする度にカウントアップ

void setup(){
  //ランダムなデータの読み込み
  loadData();
  //ディスプレイウインドウの設定
  size(NUMBER_OF_RANDOM_DATA,NUMBER_OF_RANDOM_DATA);
  background(0,0,0);
  frameRate(60);
  stroke(255,0,0);
}

void loadData(){
  String lines[] = loadStrings(DATA_FILE_NAME);
  for(String val : lines){
    nums.add(int(val));
  }
}


void linearSearch(){
  if (SEARCHING_VALUE == nums.get(i)) {
    println("Hit!");
    ellipse(i,nums.get(i),DIAMITER*2,DIAMITER*2);
    exit();
  } 
}

void draw(){
  println("Searching value is " + SEARCHING_VALUE);
  if (i < NUMBER_OF_RANDOM_DATA){
    //サーチ１パス
    linearSearch();
    //結果をプロット
    println("Count " + i);
    clear(); 
    for (int k=0; k < nums.size(); k++) {
      if ( k == i ) {
        ellipse(k,nums.get(k),DIAMITER*2,DIAMITER*2);
      } else {
        ellipse(k,nums.get(k),DIAMITER,DIAMITER);
      }
    }
    ++i;
  }
}

二分探索法

二分探索法は別名バイナリサーチ（Binary Search）と呼ばれます。ソート済みのデータに対して使えるアルゴリズムです。大変シンプルながら強力です。次のようなアルゴリズムで実行します。

二分探索法のアルゴリズム

• データはn個の整数、ソート済みで配列dataに格納されているとします。
• 探索する値を格納する整数変数をaとします。
• 探索範囲を表す整数変数lowとupperを用意します。
• 初期値はlow=0, upper=n-1とします。
• 探索位置を表す整数変数xは初期値(low+upper)/2とします。
• 次の手順を行います。
  1. data(x)とaを比較します。
  2. 双方が等しければ探索終了です。
  3. a<data(x)ならば、upper=x-1とします。data(x)<aならばlow=x+1とします。x=(low+upper)/2とします。upper<lowとなったら探索終了です。
  4. 1へ戻ります。

このアルゴリズムを実装するのを今回の演習とします。ソート済みのデータを作成して、サーチの様子を可視化しましょう。

二分探索法の計算量

データがn個のときの二分探索法は、k回目の探索後、探索範囲のデータ数wをw=n(1/2)(1/2)...(1/2)とk回分割することになります。これはw=n/(2^k)と書けます。探索範囲のデータ数が1のときに探索が終了しますから、1=n/(2^k)になります。以上の事から探索回数kはk=log2(n)となります。

そのため、二分探索法の計算量はO(log2(n))となり、線形探索法のO(n)と比較してnが大きい程計算量が劇的に小さいのです。どんな分布のデータであれ、ソートさえ済んでいればO(log2(n))で探索できるバイナリサーチは大変強力なのです。

ハッシュテーブルを用いたサーチ

ハッシュテーブルを用いたサーチでは、関数によって、データAを数値xに対応させておきます。それを表（ハッシュテーブル）とします。ハッシュテーブルのx番目にデータAを格納します。この対応が1対1であれば、関数の計算を一度行うだけでデータを保管しているテーブル内の位置を特定できます。

例えば、保管するデータは「氏名：電話番号」であるとします。氏名をハッシュ関数によってハッシュ値に変換します。ハッシュ値に対応するテーブル位置に氏名と電話番号を保管します。こうしておくことで、氏名を入力すれば、ハッシュ関数の計算一発で電話番号データを取り出せます。

計算量はハッシュ関数の計算を実行の1単位ととらえるならばO(1)です。そのため高速に目的のデータを取得できます（後述のハッシュ関数の例は非常に単純で実用的ではありませんが⁠）⁠。

なお、ハッシュによるデータ保管はJava言語ではHashMapクラスに実装されています。Processingユーザはハッシュ関数を実装する必要はありません。有り難くHashMapを活用させてもらいましょう。

簡単なハッシュ関数を実装したsketchは次のとおりです。ある値Aをハッシュ関数で計算した値を添字として、配列tableのその添字位置にAを保管します。こうすると、再度Aをハッシュ関数で計算し、配列tableの添字位置を参照すればAが配列table内にあるかどうかが分かります。配列に保管していない値Bをハッシュ関数で計算し、求められた添字の値の位置を参照すると、nullが返ります。

int    SEED = 193; // 適当な素数
int    DATA_NUM = 2017; // テーブルの大きさ
String table[] = new String[DATA_NUM];

String VAL1 = "ABCDE";
String VAL2 = "FGHIJ";
String VAL3 = "HOGE";

void setup(){
  println("hash(" + VAL1 + ") = " + hash(VAL1) + " is Stored."); table[hash(VAL1)] = VAL1;
  println("hash(" + VAL2 + ") = " + hash(VAL2) + " is Stored."); table[hash(VAL2)] = VAL2;
  
  println("get " + VAL2 + " from table[" + hash(VAL2) + "], it's " + table[hash(VAL2)]);
  println("get " + VAL3 + " from table[" + hash(VAL3) + "], it's " + table[hash(VAL3)]);
  
}

int hash(String s){
  long h = 0;
  char[] c = s.toCharArray();
  for(char val: c){
    h = h * SEED + Character.getNumericValue(val);
  }
  int index = (int)(h % DATA_NUM); 
  return index;
}

作業 sketchHashSearch.pdeで、保管する文字列を変更し、保管と取り出しの操作を試してみましょう。

演習

演習1（難易度：easy）

連載第10回で作成したsketchを活用して、ランダムなデータをソートして保存するsketchを作成しましょう。どのアルゴリズムを使用しても結構です。作成したソート済みデータのファイル名はSortedData.txtとしてください。

演習2（難易度：middle）

本文に掲載したアルゴリズムと、線形探索法のsketchを参考に、二分探索法を可視化するのsketchを作成しましょう。探索にはソート済みのデータファイルSortedData.txtを使用しましょう。このsketchのファイル名はBinarySearch.pdeにしてください。

まとめ

• サーチとその代表的なアルゴリズムを学習しました。
• 各アルゴリズムの計算量を求め、比較しました。

学習の確認

それぞれの項目で、Aを選択できなければ、本文や演習にもう一度取り組みましょう。

1. 線形探索法の仕組みが理解できましたか？
   1. 理解できた。気持ちよく納得した。
   2. 理解できた。しかし、今ひとつスッキリしない。
   3. 理解できない。
2. 二分探索法の仕組みが理解できましたか？
   1. 理解できた。気持ちよく納得した。
   2. 理解できた。しかし、今ひとつスッキリしない。
   3. 理解できない。
3. ハッシュテーブルを用いた探索の仕組みが理解できましたか？
   1. 理解できた。気持ちよく納得した。
   2. 理解できた。しかし、今ひとつスッキリしない。
   3. 理解できない。
4. 計算量の求め方が理解できましたか？
   1. 理解できた。気持ちよく納得した。
   2. 理解できた。しかし、今ひとつスッキリしない。
   3. 理解できない。

参考文献

• 『改訂C言語によるはじめてのアルゴリズム入門』（⁠河西朝雄 著、技術評論社⁠）⁠
  • アルゴリズムの入門書。入門者に取っては十分に辞書的な内容である。丁寧に解説された良書。
• 『はじめMath! Javaでコンピュータ数学 第75回　計算量の数学　計算量と実際のコード　その1』
  • コンピュータ数学を高校生程度の学力で分かるように解説したWeb連載です。計算量の解説の際、バイナリサーチをとりあげました。参考にしてみてください。

演習解答

1. BubbleSortAndSaveData.pde
   • バブルソートを使用してデータをソートし保存してみました。スケッチフォルダにRandomData.txtをコピーして用意してから実行しましょう。
2. BinarySearch.pde