連載
» 2009年01月07日 00時00分 公開

Firebugで探索アルゴリズムを見ていこうコーディングに役立つ! アルゴリズムの基本(6)(2/4 ページ)

[山下寛人,オイシックス株式会社]

逐次探索―キーを総当りで探す力業

 それでは最も単純なアルゴリズム、逐次探索を紹介しましょう。単にキーを総当たりで比較して一致したらそれに対応する値を返すというものです。

 先ほどのプログラムの65行目、「ここから」のコメントの次の行に以下のコードを追加してください。

<div id="seq">逐次探索<br></div><hr>
<script type="text/javascript">
Array.prototype.sequential_search = function(compare, n) {
  for(var i = 0; i < this.length; i++) {
    this.display("search index:" + i);
    if(compare(this[i].key, n) == 0) { return this[i].value; }
  }
 
  return null;
}
 
var seq = array.clone();
seq.view_id = "seq";
seq.display(seq);
seq.display("find: " + seq.sequential_search(compare, 5));
</script><!-- 末尾1 -->

 3行目から10行目が逐次探索のプログラムです。

 引数compareはキーの一致条件を定義する関数です。数値なので数値が等しいときに0を返すようにしていますが、カスタマイズすることもできます。

 4行目からfor文で配列の要素数分ループして、キーが検索条件nに一致するかどうか調べています。

デバッガで逐次探索を見る

 とても簡単なプログラムですが、練習のためにデバッガを使ってみましょう。

 HTMLファイルをFirefoxで開きます。逐次探索の結果が表示されると思います。「表示」→「Firebug」をクリックします。

「表示」→「Firebug」をクリック

 ウィンドウの下の部分にFirebugが出てきたら、「スクリプト」をクリックします。

ウィンドウの下の部分の「スクリプト」をクリック

 「スクリプトパネルは停止しています」と表示された場合は、「スクリプト」にチェックを入れ、「ローカルファイルで選択された機能を有効にします」をクリックします。

「スクリプトパネルは停止しています」と表示された場合は、「スクリプト」にチェックを入れ、「ローカルファイルで選択された機能を有効にします」をクリック

 スクリプトのソースが表示されます。下にスクロールして71行目(if文がある行)まで進め、左の「71」をクリックします。赤い丸が表示されます。ここがブレークポイントになります(if文をブレークポイントにしてもうまくいかない場合があるようです。その場合は上下の行や改行を入れてブレークポイントを設定してみてください)。

71行目の行番号「71」をクリックし、ブレークポイントとする

 Firefoxのリロードボタンをクリックします。プログラムの実行が設定したブレークポイントで停止します。

 ソースの右側にはそのときの変数の内容が表示されます。「this」の左のプラス記号をクリックすると、配列の内容も表示されます。

ソースの右側にはそのときの変数の内容が表示される

 探索するキーnの値は5、iの値は0、それに対応するkeyは1で一致しません。

 再開ボタン(水色の右向きの三角)をクリックします。iの値が1に変わります。さらに再開ボタンをクリックするとiの値が増えていきます。

 画面には「search index:」という行が表示されていきます。iが4のときにもう一度再開ボタンをクリックすると探索が成功になり、処理が最後まで終了になります。

Copyright © ITmedia, Inc. All Rights Reserved.

RSSについて

アイティメディアIDについて

メールマガジン登録

@ITのメールマガジンは、 もちろん、すべて無料です。ぜひメールマガジンをご購読ください。