Processingで学ぶ 実践的プログラミング専門課程

第11回 サーチ

この記事を読むのに必要な時間:およそ 3.5 分

導入

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

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

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

展開

サーチとは

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

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

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

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

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

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

線形探索法

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

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

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

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

線形探索のsketch。LinearSearch.pde

// 線形探索   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){
    //サーチ1パス
    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/(2k)と書けます。探索範囲のデータ数が1のときに探索が終了しますから,1=n/(2k)になります。以上の事から探索回数kはk=log2(n)となります。

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

著者プロフィール

平田敦(ひらたあつし)

地方都市の公立工業高等学校教諭。趣味はプログラミングと日本の端っこ踏破旅行。やがては結城浩氏のような仕事をしたいと妄想している。

Twitter : @hirata_atsushi

コメント

コメントの記入