第4回　Internet Explorerよりも速くソートできるかな

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

2008/11/5

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

　ソートはアルゴリズムに関するテーマの中でも定番中の定番です。数値を数の大小で並べ替える。ただそれだけのことですが、ありとあらゆる手法があり、それぞれパフォーマンスやプログラムの分かりやすさなどに特徴があります。今回はさまざまなソートのアルゴリズムを紹介します。

　今日のプログラム言語の多くはソート機能を備えていて、自力でソートする機会はあまりありません。せっかく自力でソートするのですから組み込みのソートよりも高速にソートできるプログラムが作れるか、チャレンジしてみましょう。

　今回もWebブラウザ上のJavaScriptでプログラムを開発します。Internet Explorerに組み込まれているソートとのパフォーマンスを競ってみましょう。

IE組み込みのソート

　ソートのアルゴリズムを紹介する前に、JavaScriptの標準機能のソートでどれくらい時間がかかるか計測しましょう。また以後で共通に使用する関数も併せて作成します。

　本連載ではソースはコピー＆ペーストせず打ち込むことを推奨しておりますが、この部分はアルゴリズムそのものに関係ないのでコピー＆ペーストでも構わないでしょう。

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
68
69
<html>
<head>
<script type="text/javascript">
Array.prototype.clone = function() {
  function f() {}
  f.prototype = Object(this);
  return new f();
}

Array.prototype.swap = function(i,j) {
  if(i == j) { return; }
  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 + "]";
}

Array.prototype.display = function(str) {
  if (this.view_id == undefined) { return; }
  if (str == undefined) { str = this.toString(); }
  var element = document.getElementById(this.view_id);
  element.innerHTML += str + "<br>";
}

function time(func, name, view_id) {
  var start = new Number(new Date());
  func();
  var end = new Number(new Date());
  var t = end - start;

  var element = document.getElementById(view_id);
  element.innerHTML += name + "の処理時間:" + t + "<br>";
}

function compare(a , b) {
  return (a - b);
}

//表示するための配列
var arrayForDisplay = new Array(10);
for(var i = 0; i<arrayForDisplay.length; i++) { arrayForDisplay[i] = i;}
arrayForDisplay.reverse();

//時間計測用の配列
var arrayForTime = new Array(700);
for (var i = 0; i < arrayForTime.length; i++) {
  arrayForTime[i] = Math.floor(Math.random() * arrayForTime.length);
}
</script>
</head>
<body>

<span id="kumikomi"></span>
<script type="text/javascript">
var kumikomi = arrayForTime.clone();
var func = function() { kumikomi.sort(compare); }
time(func, "組み込みのソート", "kumikomi");
</script>
<!-- 末尾1 -->
</body>
</html>

　プログラムを解説します。

4〜8行目

配列をコピーする関数です。

10〜15行目

配列の中の2つの要素の値を交換する関数です。

17〜24行目

配列の中身をカンマ区切りの文字列にする関数です。

26〜31行目

配列の中身をWebブラウザに表示する関数です。

33〜41行目

関数の実行時間を計測してWebブラウザに表示する関数です。

43〜45行目

ソートする際にどういう順序でソートするかを決める関数です。ここでは数値の昇順になるようにしていますが、compare関数を変更することで降順にしたり文字列も含めたりしたソートにすることもできます。

47〜56行目

配列を2種類作成します。

1つは分かりやすくするためにソートの途中経過を表示するための配列です。要素数が多いと画面に出しても訳が分からないので、要素数は10個です。最初は9から0まで降順にしてあります。

もう1つはパフォーマンス計測用です。要素数が少ないと一瞬で処理が終わって比較にならないので700個用意します。

61〜66行目

ソートを実行してWebブラウザに実行時間を表示します。

　それでは実行してみてください。実行はいつもどおりソースをHTMLファイルとして保存してWebブラウザで開いてください。IEで警告が出た場合は実行を許可するようにしてください。

　筆者のPCでは60前後でした。配列は乱数で作成しているので実行するたびに多少時間は前後する場合があります。これが今回の目標値になります。果たしてこれより速くできるのでしょうか。

　なお、PCの性能によって時間がかかり過ぎたり、早く終わったりする場合があるかと思います。53行目のnew Array()の中の数を変更することで調整できますので、実行時間が60前後になるように調整するとよいでしょう。

選択ソート―最も単純なやり方

　選択ソートは最も単純なソートのアルゴリズムの1つです。

　一番小さい値を全体の中から選びます。それを配列の最初に格納します。次に残ったものの中から同じように一番小さい値を選び、配列の2番目に格納します。これを最後まで繰り返します。

　先ほどのソースの67行目、「末尾1」というコメントがある行の次の行に以下のソースを追加してください。

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
<hr/>
選択ソート<br/>
<span id="selection"></span>
<script type="text/javascript">
Array.prototype.getMinIdx = function(compare, l, r) {
  var min_idx = l;
  for (var i = l + 1; i < r; i++) {
    if (compare(this[i] , this[min_idx]) < 0) { min_idx = i; }
  }
  return min_idx;
}

Array.prototype.selectionSort = function(compare) {
  for (var i = 0; i < this.length-1; i++) {
    var min_idx = this.getMinIdx(compare, i, this.length);
    this.swap(i, min_idx);
    this.display();
  }
}
var selection = arrayForDisplay.clone();
selection.view_id = "selection";
selection.display();
selection.selectionSort(compare);
var selectionForTime = arrayForTime.clone();
func = function() { selectionForTime.selectionSort(compare); }
time(func, "選択ソート", "selection");
</script><!-- 末尾2 -->

　プログラムを解説します。

3行目

この位置にプログラムの出力結果を表示します。

5〜11行目

配列の中の最小の値を持つインデックスを調べて返す関数です。インデックスがlとrの間の範囲を調べます。

13〜19行目

選択ソートです。元の配列と出来上がりの配列を同じにして、配列の0番目から最小の値と入れ替えるようにしています。

　では実行してみましょう。結果はいかがだったでしょうか。

　残念ながら全く勝負にならなかったと思います。こんな単純なやり方で勝てるほど世の中甘くはありません。

 
1/3

Index
Internet Explorerよりも速くソートできるかな
Page1
IE組み込みのソート
選択ソート―最も単純なやり方
  Page2
バブルソート―泡が浮かび上がるように
選択ソートとバブルソートのパフォーマンス
  Page3
シェルソート―グループごとに挿入ソート
クイックソート―名は体を表す？
クイックソートのパフォーマンス

コーディングに役立つ！ アルゴリズムの基本
　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