『数学ガール 乱択アルゴリズム (数学ガールシリーズ 4)』を読んでます。数学ガールシリーズも本書で4冊目ですが，乱択アルゴリズムでは擬似コードでアルゴリズムが紹介されています。読者の多くの方はプログラミング言語に親しまれている方だと思いますが，ひょっとして，本書を通して初めてプログラムに触れるという方もいらっしゃるかもしれないということで，何個かプログラムにしてみました。Rubyで書いています。
Rubyがインストールされていないという方は，Googleなどで「Ruby インストール」と検索してインストールしてください。
番兵付きリニアサーチ・アルゴリズム(p48)
本では，2行目が n+1，3行目が1となっていますが，多くのプログラミング言語は配列の添字を0から数え始めますので，それぞれ，nと0に変更しています。
あと，本では手続きの名前を`-'で区切っていますが，これでは引き算の意味になってしまいますので，`_'に変更しています。
def sentinel_linear_search(a, n, v) a[n] = v # 添字0からはじまるから k = 0 # 同上 while a[k] != v k = k + 1 end if k <= n return "見つかる" end return "見つからない" end array = [31, 41, 59, 26, 53] puts sentinel_linear_search(array, array.size, 26)
上記をsentinel_linear_search.rbという名前で保存し，以下のように実行します。
$ ruby sentinel_linear_search.rb 見つかる
サイコロ勝負(p111)
本で紹介されている1行1行と以下の1行1行を比べてみると対応関係がよく分かると思います。
def dice_game() a = rand(6)+1 b = rand(6)+1 if a > b return "アリスの勝ち" elsif a < b return "ボブの勝ち" end return "引き分け" end
上記をdice_game.rbという名前で保存して，今度は，irbを使って実行してみます。
$ irb -I. -rdice_game ruby-1.9.2-p180 :001 > dice_game => "アリスの勝ち" ruby-1.9.2-p180 :002 > dice_game => "ボブの勝ち" ruby-1.9.2-p180 :003 > dice_game => "ボブの勝ち" ruby-1.9.2-p180 :004 > quit
他にもアルゴリズムが紹介されていますので，実際にプログラムを作成し実行することでアルゴリズムやプログラミング言語への理解がより深まるのではと思います。Rubyだと擬似言語の1行1行に対応させやすいのでお薦めです。
第1章では，モンティ・ホールの問題が紹介されていますが，シミュレーションしてみると本に書かれているような結果になりますね。
追記
行列の計算(2011/03/15)
p269の問題7-2は行列の冪乗ですが，これもRubyで簡単に確認できます。
$ irb -rmatrix ruby-1.9.2-p180 :001 > Matrix[[1,1],[1,0]]**10 => Matrix[[89, 55], [55, 34]] ruby-1.9.2-p180 :003 > quit
クイックソート(2011/03/17)
p391のクイックソートです。本の中では，l,rと書かれているところをleft, rightに変更しています。
def quicksort(a, left, right) if left < right p = left k = left + 1 while k <= right if (a[k] < a[left]) a[p+1], a[k] = a[k], a[p+1] p += 1 end k += 1 end a[left], a[p] = a[p], a[left] quicksort(a, left, p - 1) quicksort(a, p + 1, right) end end ary = [5, 1, 7, 2, 6, 4, 8, 3] p ary quicksort(ary, 0, ary.length - 1) p ary
上記をqsort.rbというファイル名で保存し，実行すると以下のように配列のデータが整列されます。
$ ruby qsort.rb [5, 1, 7, 2, 6, 4, 8, 3] [1, 2, 3, 4, 5, 6, 7, 8]
次に，p424で紹介されている乱択クイックソートを作成し，p391のクイックソートと実行速度を比較してみたいと思います。Rubyはオブジェクト指向(OOP)スクリプト言語ですので，Arrayクラスを拡張して作ってみました。ファイル名をoop_qsort.rbとしています。
class Array def qsort! quicksort(0, self.length - 1) end def quicksort(left, right) if left < right p = left k = left + 1 while k <= right if (self[k] < self[left]) self[p+1], self[k] = self[k], self[p+1] p += 1 end k += 1 end self[left], self[p] = self[p], self[left] quicksort(left, p - 1) quicksort(p + 1, right) end end def rqsort! randomized_quicksort(0, self.length - 1) end def randomized_quicksort(left, right) if left < right r = rand(right - left + 1) + left self[left], self[r] = self[r], self[left] p = left k = left + 1 while k <= right if (self[k] < self[left]) self[p+1], self[k] = self[k], self[p+1] p += 1 end k += 1 end self[left], self[p] = self[p], self[left] randomized_quicksort(left, p - 1) randomized_quicksort(p + 1, right) end end end
以下がp391のクイックソートとp424の乱択クイックソートの速度比較を行うベンチマークです。ファイル名をspeed_test.rbとしました。
require 'benchmark' require 'oop_qsort' RAND_MAX = 100000 Benchmark.bm(20) do |b| ary1 = Array.new(RAND_MAX) { rand(RAND_MAX) } ary2 = Marshal.load(Marshal.dump(ary1)) ary3 = Array.new(RAND_MAX*0.95) { |i| i } + Array.new(RAND_MAX*0.05) { rand(RAND_MAX) } ary4 = Marshal.load(Marshal.dump(ary3)) b.report("(1)quicksort") { ary1.qsort! } b.report("(2)random_quicksort") { ary2.rqsort! } b.report("(3)quicksort") { ary3.qsort! } b.report("(4)random_quicksort") { ary4.rqsort! } end
テスト内容は，
- 大きさ1000000のランダムなデータ配列(ary1, ary2)をソートする時間を比較
- 大きさ1000000のうち，最初の950000はソート済みで，あとの50000個の要素がランダムである配列(ary3, ary4)をソートする時間を比較
です。
ary2はary1を，ary4はary3をそれぞれコピーしています。以下が実行結果です。
$ ruby -I. speed_test.rb (1)quicksort 24.430000 0.060000 24.490000 ( 24.523673) (2)random_quicksort 24.520000 0.060000 24.580000 ( 24.551150) (3)quicksort 116.330000 0.280000 116.610000 (116.642262) (4)random_quicksort 26.070000 0.070000 26.140000 ( 26.099962)
(1),(2)は1000000個の要素がすべてランダムな配列データをソートした結果です。ほとんど実行時間に差は見られません。
(3),(4)はほとんど整列済みな配列データに対する実験結果ですが，これを見ると乱択バージョンの優位が一目瞭然ですね。少し，アルゴリズムに工夫を加えることで性能にこんなにも差が現れるなんて面白いなと思います。
