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

TinyWebDB API Tester HD

AppInventorはAndoridのApp作りに簡単な環境です。WordPressをWebコンテンツを作るに最適な環境。

WP-TinyWebDB-APIは、両者の長所を連携し、WordPressをAppInventorのTinyWebDBサービスとして利用するためのAPIを、WordPressのプラグインとして提供したもの。

TinyWebDB API Tester (HD版) は設置しているAPIをテストするためのものである。

https://play.google.com/store/apps/details?id=appinventor.ai_chen_waseda.TinyWebDB_API_HD

TINIWEBDB-API5.2-512x512

孤帆远影 HD

孤帆远影(安卓HD版)包含十万首网络诗词,便于您欣赏,收藏。

主要功能:
1. 显示十万首中任意一首
2. 朗读 (须安装中文TTS)

计划功能:
1. 评论
2. 投稿
3. 余韵
4. 聚友

https://play.google.com/store/apps/details?id=appinventor.ai_chen420.PoemDB2

Screenshot_2013-06-11-01-46-24

孤帆远影

孤帆远影(安卓版)是孤帆远影诗词网站(http://poemdb.org)的安卓客户端,便于您通过安卓手机欣赏,收藏。

主要功能:
1. 显示孤帆远影诗词网站单页内容
2. 朗读 (须安装中文TTS)
3. 收藏单页内容便于脱机显示
4. 跳转孤帆远影诗词网站对应网页

https://play.google.com/store/apps/details?id=appinventor.ai_chen420.PoemDB

360手机助手截图01

TANNKA

短歌は、日本で最も古い定型詩で、日本最古の歌集として有名な『万葉集』は8世紀に編集されたものです。
31音の言外に感じられるものを余情といい、短歌一首の内容は、この余情をも含めたものというべきである。

TANNKAはスマートフォンで短歌を鑑賞するためのアプリです。

基本機能:
1. 短歌WordPressサイトと連携、サイトの和歌を表示
2. 短歌と余情を Twitter へ投稿
3. 短歌読み上げ (N2 TTSなど読み上げツールが別途必要)
4. 短歌ローカル保存する(オフラインでも使える)

計画機能:
1. 短歌に余情、コメントの保存
2. コミュニティ形成

リリースできない状態が長引き、興味がある方から意見を頂くために、公開しました。

https://play.google.com/store/apps/details?id=appinventor.ai_chen420.Tannka

tanka-512