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

13.Web Application13.Web Application

Webアプリケーション作成に必要な概念を理解する Web Service Webサービスとは、大まかにいえば、Webの通信の仕組みを利用して、コンピュータ同士でさまざまなデータをやり取りし、分散処理を行うシステムです。 通信手順の取り決めのことを、「プロトコル」(Protocol)と呼びます。Webの世界では、「HTTP」(HyperText Transfer Protocol)というプロトコルで、通信が行われています。 HTTPは、WebブラウザなどのクライアントがWebサーバーにデータを要求し、それにWebサーバーが答える、という形のプロトコルです。 API アプリケーションプログラミングインタフェース (API、英: Application Programming Interface) とは、ソフトウェアコンポーネントが互いにやりとりするのに使用するインタフェースの仕様である。APIには、サブルーチン、データ構造、オブジェクトクラス、変数などの仕様が含まれる。 Webサービス大まかに言えば、以下のような流れで処理を進めます。 (1)クライアントからサーバーに対して、HTTPで接続して処理を要求します。 (2)サーバーは処理結果をクライアントに送信します。 (3)クライアントは(2)の結果を受信し、必要に応じて各種の処理を行います。 「HTTPで通信する」上位層に位置するプロトコル […]

4.Data Structure4.Data Structure

データ構造とは データ構造(データこうぞう、英: data structure)は、計算機科学において、データの集まりをコンピュータの中で効果的に扱うため、一定の形式に系統立てて格納するときの形式のことである。 ソフトウェア開発において、データ構造についてどのような設計を行うかは、プログラム(アルゴリズム)の効率に大きく影響する。そのため、さまざまなデータ構造が考え出されている。 配列 配列(はいれつ)は同じ型の変数を複数取り扱うために考案された仕組みです。配列は変数名にカッコ付きの整数を添えることで順番を決め,要素を区別します。配列によってまとめられた,一つひとつの変数を要素(ようそ)と呼びます。要素を区別するために添えた数字を添字(そえじ)と呼びます。 配列は大変シンプルで,コレクションクラスに比較すると必要とするメモリ量が少なく,アクセスが高速なことがメリットです。データを単純に格納して,順番に参照する程度の用途であれば,コレクションクラスに比較して配列のほうが有利です。 最も基本的な配列の使用例を次に示します。配列の要素数を含めて宣言し,配列の添字を明記して要素に値を代入し,添字を指定して要素の値を呼び出します。 String names[] = {“Tim Bray”,        // 0番目の要素 “Brian Kernighan”, // 1番目の要素 […]

14.REST and JSON14.REST and JSON

REST RESTは「REpresentational State Transfer」の略で、大まかに言えば、アドレス(URL)とHTTPのメソッド(GETなど)を組み合わせて、サーバー上のデータを操作する仕組みです。 RESTは、Roy Fieldingという方が、2000年に発表した博士論文で提唱されたアーキテクチャスタイルです。Roy FieldingさんはHTTP仕様の策定者の一人であったことから、HTTPはRESTの基準をよく満たしています。 RESTの例として、WordPress JSON REST API (WP API, http://wp-api.org/) あります。それを利用して、Javaなどから最新の記事の取得、記事の投稿、写真の添付などが可能です。 JSON JSON(ジェイソン、JavaScript Object Notation)は、JavaScriptにおけるオブジェクトの表記法をベースとした軽量なデータ記述言語である。 JSONの紹介 […]