お手玉方式と逆転方式

本棚にずっと立て掛けてあった『珠玉のプログラミング―本質を見抜いたアルゴリズムとデータ構造』を少し読んでみました。その中で，以下のような問題がありました。

要素がn個ある配列を左方向にi要素分回転させるにはどうすればよいでしょう。例えば，n = 8でi = 3のとき，配列abcdefghをdefghabcにする回転です。(以下省略)

うまいやり方として，「お手玉方式」，「逆転方式」という手法があるみたいです。面白そうなので，Rubyで作ってみました。
simple_rotateは，左端を作業領域にコピーし残りを1つずつ左にスライドしていくようなシンプルな手法で，otedama_rotateが「お手玉方式」，reverse_rotateが「逆転方式」です。"abcdefghijklmnopqrstrvwxyz" * 10000な文字列を作り，左に100回転させてみて，速度を計ってみました。

require 'mathn'

class String
 # 単純な方法
 def simple_rotate(rotdist)
   for i in 1..rotdist
     t = self[0]
     for j in 1...self.size
       self[j - 1] = self[j]
     end
     self[self.size - 1] = t
   end
   self
 end

 # お手玉方式
 def otedama_rotate(rotdist)
   for i in 0...rotdist.gcd2(self.size)
     t = self[i]
     j = i
     loop do
       k = j + rotdist
       k -= self.size if k >= self.size
       break if k == i
       self[j] = self[k]
       j = k
     end
     self[j] = t
   end
   self
 end

 # 逆転方式
 def reverse_rotate(rotdist)
   myreverse(0, rotdist - 1)
   myreverse(rotdist, self.size - 1)
   myreverse(0, self.size - 1)
 end

 private
 def myreverse(l, r)
   while l < r
     t = self[l]
     self[l] = self[r]
     self[r] = t
     l += 1
     r -= 1
   end
   self
 end
end

def bench_mark(title, &block)
 t1 = Process.times.utime
 yield
 t2 = Process.times.utime
 return sprintf("%15s:%#5.2f", title, t2 - t1)
end

str = "abcdefghijklmnopqrstrvwxyz" * 10000

puts bench_mark("simple_rotate") { str.simple_rotate(100) }
puts bench_mark("otedama_rotate") { str.otedama_rotate(100) }
puts bench_mark("reverse_rotate") { str.reverse_rotate(100) }

実行結果

$ ruby rotation.rb
simple_rotate:11.85
otedama_rotate: 0.27
reverse_rotate: 0.27

実行速度に相当な開きがあることが分かりました。これだけ見てもアルゴリズムを学習することの大切さが分かります。