昨日のつづき…

昨日は，『珠玉のプログラミング―本質を見抜いたアルゴリズムとデータ構造』で紹介されていた以下の問題を

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

Stringクラスを拡張し，3つの手法(単純な方法,お手玉方式,逆転方式)で作って，速度比較を行ってみました。
しかし，Arrayクラスのインスタンスに対しても回転させる必要性が起こったら…と考えとき，あっ，こんなときにMix-inを使えばいいんだなと思いつきました。

rotation.rb

left_rotate!が左方向への破壊的な回転，right_rotate!が右方向への破壊的な回転です。昨日の実験から，単純な方法は効率が非常に悪いことは分かっていましたので，今回は，「逆転方式」を用いました。

module Rotation
  def left_rotate!(rotdist)
    myreverse(0, rotdist - 1)
    myreverse(rotdist, self.size - 1)
    myreverse(0, self.size - 1)
  end

  def left_rotate(rotdist)
    a = self.dup
    a.left_rotate!(rotdist)
  end

  def right_rotate!(rotdist)
    left_rotate!(self.size - rotdist)
  end

  def right_rotate(rotdist)
    a = self.dup
    a.right_rotate!(rotdist)
  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

use_rotation.rb

Rotationモジュールを使ってみます。

require 'rotation'

class String
  include Rotation
end

str = "abcdefghijklmnopqrstrvwxyz"
puts str.left_rotate!(3)
puts str.right_rotate!(3)

class Array
  include Rotation
end

ary = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
ary.left_rotate!(3).each do |ele|
  print ele
end
puts

ary.right_rotate!(3).each do |ele|
  print ele
end
puts

実行結果

$ ruby use_rotation.rb
defghijklmnopqrstrvwxyzabc
abcdefghijklmnopqrstrvwxyz
3456789012
0123456789