Firebugで探索アルゴリズムを見ていこう：コーディングに役立つ！アルゴリズムの基本（6）（1/4 ページ）

プログラマたるものアルゴリズムとデータ構造は知っていて当然の知識です。しかし、教科書的な知識しか知らなくて、実践的なプログラミングに役立てることができるでしょうか（編集部）

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

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

　今回紹介するのは探索のアルゴリズムです。探索もアルゴリズムのテーマとしてはメジャーなもので、とても重要な用語や考え方が出てきます。

　あるデータの集合があったとします。それぞれのデータには、個々を識別するためのIDが付いています。このIDをキーと呼びます。このキーに対応するデータを探すのが探索です。

　データベースを知っている方なら主キーで検索する動作だと思ってください。例えば、商品のリストがあり、それぞれの商品に商品コードが付いています。商品コード「7100」に対応する商品データ「トマト」を検索するプログラムを考えましょう。実際にデータベースのインデックスは今回紹介するアルゴリズムを基礎としています。

Firebugで探索の様子を見てみよう

　プログラムの動作を見るためにデバッガを使ってみます。デバッガを使うとプログラムを途中で止めて少しずつ進めながら、変数の動きを見ることができます。

　FirefoxのプラグインにFirebugというものがあります。JavaScriptのデバッガや、DOM、CSSの開発をサポートする機能が非常に充実しているWeb開発に欠かせないプラグインです。一般的なデバッガの使い方、Firebugの使い方も併せて習得しましょう。

　まず、Firefoxをインストールしてください。次にFirebugをインストールします。Firebugのインストールは非常に簡単です。下記のページで「Firefoxへインストール」をクリックしてください。あとはボタンをクリックするだけでインストールできます。Firefoxを再起動するよう指示されるので再起動してください。

　なお、本稿執筆時点ではFirefoxはバージョン3.0.4、Firebugはバージョン1.2.1となっています。


	関連リンク：
	Firebug https://addons.mozilla.org/ja/firefox/addon/1843

下準備

　まず、ベースとなるHTMLファイルを作成しましょう。以下の内容のファイルを作り、拡張子を.htmlにして保存してください。汎用メソッド、探索対象のデータを作成しています。

<html>
<head>
<script type="text/javascript">
 
//clone：ディープコピー
Array.prototype.clone = function() {
  function f() {}
  f.prototype = Object(this);
  return new f();
}
 
//swap：配列の要素を入れ替える
Array.prototype.swap = function(i,j) {
  var tmp = this[i];
  this[i] = this[j];
  this[j] = tmp;
} 
 
Array.prototype.toString = function() {
  var str = "";
  for(var i=0; i < this.length; i++) {
    if (i != 0) { str += ","; }
    str += this[i];
  }
  return "[" + str + "]";
 
}
 
function Item(key, value) {
  this.key = key;
  this.value = value;
}
 
Item.prototype.toString = function() {
  return "{" + this.key + ":" + this.value + "}";
}
 
Array.prototype.pushItem = function(key, value) {
  this.push(new Item(key, value));
}
 
//display：画面表示
Array.prototype.display = function(str) {
  var element = document.getElementById(this.view_id);
  element.innerHTML += str + "<br>";
}
 
//配列生成
var array = [];
array.pushItem(1, "one");
array.pushItem(2, "two");
array.pushItem(3, "three");
array.pushItem(4, "four");
array.pushItem(5, "five");
array.pushItem(6, "six");
array.pushItem(7, "seven");
 
function compare(a, b) {
  return (a - b);
}
</script>
</head>
 
<body>
<!-- ここから -->
</body>
</html>

　詳細は探索アルゴリズムそのものとあまり関係がないので省略します。29行目から32行目はItemクラスを定義しています。これが探索対象となる1件のデータを表しています。キーと値で構成されています。

　今回は数値からそれに対応する英語の文字列を探索するプログラムを作成します。

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

　　　　　　 1|2|3|4 次のページへ

SpecialPR