第6回　Firebugで探索アルゴリズムを見ていこう

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

2009/1/7

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

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

　あるデータの集合があったとします。それぞれのデータには、個々を識別するための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にして保存してください。汎用メソッド、探索対象のデータを作成しています。

01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
<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/4

Index
Firebugで探索アルゴリズムを見ていこう
Page1
Firebugで探索の様子を見てみよう
下準備
  Page2
逐次探索―キーを総当りで探す力業
デバッガで逐次探索を見る
  Page3
二分探索―半分ずつ絞り込んで効率アップ
二分探索のソースコード
デバッガで二分探索を見る
  Page4
計算量を考える
逐次探索の時間計算量
二分探索の時間計算量
選択ソートの時間計算量
ハッシュテーブル
ハッシュテーブルのソースコード
デバッガでハッシュテーブルを見る

コーディングに役立つ！ アルゴリズムの基本
　Coding Edgeお勧め記事
いまさらアルゴリズムを学ぶ意味
コーディングに役立つ！ アルゴリズムの基本（1）　コンピュータに「3の倍数と3の付く数字」を判断させるにはどうしたらいいか。発想力を鍛えよう
Zope 3の魅力に迫る
Zope 3とは何ぞや？（1）　Pythonで書かれたWebアプリケーションフレームワーク「Zope 3」。ほかのソフトウェアとは一体何が違っているのか？
貧弱環境プログラミングのススメ
柴田 淳のコーディング天国　高性能なIT機器に囲まれた環境でコンピュータの動作原理に触れることは可能だろうか。貧弱なPC上にビットマップの直線をどうやって引く？
Haskellプログラミングの楽しみ方
のんびりHaskell（1）　関数型言語に分類されるHaskell。C言語などの手続き型言語とまったく異なるプログラミングの世界に踏み出してみよう
ちょっと変わったLisp入門
Gaucheでメタプログラミング（1）　Lispの一種であるScheme。いくつかある処理系の中でも気軽にスクリプトを書けるGaucheでLispの世界を体験してみよう
　　Coding Edgeフォーラムフィード　 2.0／1.0／0.91

TechTargetジャパン

Coding Edge フォーラム 新着記事

＠ITメールマガジン　新着情報やスタッフのコラムがメールで届きます（無料）

RSSフィード

＠IT 新着記事

キャリアアップ

＠IT Sepcial
→ ＠IT Special ヘ

イベントカレンダー

PickUpイベント

- PR -
もっと見る

お勧め求人情報

ホワイトペーパー（TechTargetジャパン）

＠IT Sepcial
→ ＠IT Special ヘ
ソリューションFLASH