Mae向きなブログ

Mae向きな日記のブログ版。ようやくこちらに移行してきました。

数学ガール/乱択アルゴリズム

数学ガール 乱択アルゴリズム (数学ガールシリーズ 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/16)

p280の内容です。

クイックソート(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)はほとんど整列済みな配列データに対する実験結果ですが,これを見ると乱択バージョンの優位が一目瞭然ですね。少し,アルゴリズムに工夫を加えることで性能にこんなにも差が現れるなんて面白いなと思います。