【3/18〜】Amazon、VMwareが語る『クラウドの未来』 スラッシュドット    はてなブックマーク  Yahoo!ブックマークに登録  印刷

第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.01.00.91

Coding Edge フォーラム 新着記事

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

RSSフィード

スキルアップ/キャリアアップ(JOB@IT)

お勧め求人情報

キャリアアップ 〜JOB@IT
@IT Special -PR-
  上司や部下、部署内メンバーとの情報共有
を“ガラッ”と変えるコラボツールとは?

New!
  おばかアプリ選手権、第4弾開催中!!
ムダにカッコよくてくだらない作品求ム!

  社内ファイルサーバを“クラウド”に統合
VPN直結「クラウド型ストレージ」を紹介

  Twitterのアカウントはなぜ突破された?
メールによる新手の攻撃手法とその対策

  もう仮想化のお試しフェイズは終わりだ!
Hyper-V 2.0が基幹システムも仮想化

  美人!? まあまあ? 気になる いやし系!!
PV急増で「美人時計」がとった手段とは?

  クライアント企業から求められる人材
⇒IT技術と経営戦略を併せ持つ「戦略家」

  .NET編集長が実践する「技術情報検索術」
サンプル・コードを簡単に探す“技”は?

  業務効率と情報セキュリティ対策を両立!
手間なく確実に機密情報を守る方法とは?

  直属上司が海外にいるのエンジニアに見る
【実例】場所に捉われないワークスタイル

  「仮想化工房」のマイスターが選んだのは
VMware、Hyper-V、そしてVirtageだった!

  進化を続ける富士通ストレージETERNUS DX
製品開発者の自信を裏付けるものとは何か

  運用管理の課題を“2つの観点”から分析
ユーザー満足度の高い「仮想環境」とは?

  【CTC事例】約30の基幹システムを統合!
膨大なバッジジョブを制御した方法は?

  仮想化すればコストは削減できるか?
仮想化に必要な「3つの視点」を解説する

  その数、なんと400台以上! グループ内
サーバの「統合管理」によるメリットは?