5.Search

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

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

リストサーチ(list search)

データのリスト構造とはA, B, C, ……のように,データが次々と連続している構造のことを言います。代表例は配列です。

そのようなリスト構造を持つデータの集合を探索するためのアルゴリズムを,ここではリストサーチと呼びます。

探索のアルゴリズム

  • 線形探索
  • 二分探索
  • ハッシュ法

線形探索

線形探索という言葉は英語のLinear Searchの直訳です。線形探索はリストの先頭から終端に向かって目的の要素を探し出すアルゴリズムです。

目的の要素であるという判定は比較によって行います。

アルゴリズム分析

  1. リストの先頭から要素を取り出す
  2. 取り出した要素の値と探したい要素の値を比較する
    • 一致すれば探索完了
    • 一致しなければ 1. へ戻り次の要素を取り出す

かなりシンプルで理解し易いアルゴリズムです。

サンプルコード

線形探索のアルゴリズムを実装した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;
  }
}

 

参考:

  • http://www.codereading.com/algo_and_ds/algo/linear_search.html

Leave a Reply

Your email address will not be published. Required fields are marked *

CAPTCHA


Related Post

11.List11.List

List構造 コレクションクラス List構造は、要素を順番付けして管理するデータ構造です。 「ArrayList」「LinkedList」の2種類があります。 要素がインデックス(番号)順に並んでいるので、番号を指定して要素の取得、挿入、更新、削除ができます。また、Iteratorや拡張for構文を使って先頭から順番に要素を取得することも出来ます。 ArrayListは要素の取得が早いが挿入や削除が遅い、LinkedListは要素の挿入や削除は早いが取得が遅いという特徴があります。 List構造は、要素の重複は可能です。 リスト(ArrayList) ArrayList は配列を扱う一般的なクラスです。 下記などのメソッドが用意されています。 list.add(o) – オブジェクト o を配列の末尾に追加する list.add(n, o) – オブジェクトを […]

3.Algorithms3.Algorithms

アルゴリズムとは アルゴリズム(英: algorithm)とは、数学、コンピューティング、言語学、あるいは関連する分野において、問題を解くための手順を定式化した形で表現したものを言う。「算法(さんぽう)」と訳されることもある。 基本的なアルゴリズム 順次 条件判定と分岐 (if, switch) 繰り返し (while, for)   順次 順次実行構造は,上に書かれた命令が先に実行され,下に書かれた命令が後に実行される構造のことです。なるべくこのようなシンプルで自然な構造になるようコードを書くべきです。 典型的な順次実行の例として,GSWPよりサンプルコードを引用します。 // Example 03-13 from "Getting […]

12.Map12.Map

Map構造 コレクションクラス Map構造は、キーと値をセットにしたものを1つの要素として管理するデータ構造です。 「HashMap」「TreeMap」の2種類があります。 要素がキーと値で管理されているので、キーを指定して値の取得や更新、削除を行います。 Map構造は、キーによって値を管理するためキーの重複は不可です。 (同じキーがセット(put)された場合は上書きされます。) マップ(HashMap) HashMap は、名前(キー)と値の組み合わせを要素として持つ配列です。 HashMapは格納順は管理されません。キーと値にnullを使用することが可能です。 HashMap hm = new HashMap(); hm.put("Brian Kernighan","A REGULAR EXPRESSION […]