読者です 読者をやめる 読者になる 読者になる

素人がプログラミングを勉強していたブログ

プログラミング、セキュリティ、英語、Webなどのブログ since 2008

連絡先: すかいぷ:javascripter_  か javascripter あっと tsukkun.net skypeのほうがいいです

配列から最小値、最大値を検索する

ruby
=begin
Reducer
配列等のイテレータから適切な値をスキャンして抜き出すクラス。O(n)である。
Reducer#reduce(iter)
iterはempty?とeachメソッドを実装している必要がある。
Reducer#update?(left, right)
抽象メソッドである。
サブクラスでオーバーライドして使用する。
値を更新する場合にtrueを返し更新しない場合はfalseを返す。
=end
class Reducer
  def reduce(iter)
    return nil if iter.empty?
    cur = nil
    iter.each.with_index {|value, index|
      if index.zero?
        cur = value
      else
        cur = value if update?(value, cur)
      end
    }
    return cur
  end

  private
  def update?(left, right)
    throw NotImplementedError.new
  end
end

=begin
ArrayMinFinder
配列から最小値を探すクラス。O(n)である。
=end
class ArrayMinFinder < Reducer
  private
  def update?(left, right)
    return left < right
  end
end

=begin
ArrayMaxFinder
配列から最大値を探すクラス。O(n)である。
=end
class ArrayMaxFinder < Reducer
  private
  def update?(left, right)
    return left > right
  end
end

=begin
ArrayUtils
配列操作に便利なメソッドを集めたユーティリティクラス。
クラスメソッドを使用するのでインスタンス化しない。
ArrayUtils.min(array)
配列から最小値を検索する。配列が空の場合nilを返す。
ArrayUtils.max(array)
配列から最大値を検索する。配列が空の場合nilを返す。

=end

class ArrayUtils
  @arrayMinFinder = ArrayMinFinder.new
  @arrayMaxFinder = ArrayMaxFinder.new

  def self.min(array)
    return @arrayMinFinder.reduce(array)
  end

  def self.max(array)
    return @arrayMaxFinder.reduce(array)
  end
end

p ArrayUtils.max([]) # 0
p ArrayUtils.max([1]) # 1
p ArrayUtils.max([0, 1, 2]) # 2

普通は上記のように書くが、Rubyの先進的ユーザは

p [].max, [1].max, [0,1,2].max

と書くようだ。

さて、上記コードについて。
minもmaxも、配列を走査して現在の値より大きい/小さければ値を更新する、という動作である。
こういった場合、コードの重複を避けるためにTemplate Methodというパターンが使える。
上記コードでは共通部分はReducerというクラスにまとめてあり、子のクラスで大きいか小さいかの判定を行う、いわばコードの差分であるupdate?メソッドを作成する。
すると重複を排除でき、共通のバグを発見した場合一箇所を修正するだけでよくなる。
それから、arrayMinFinderやarrayMaxFinderを直接利用するのではなくArrayUtilsというクラスを作成した。
ArrayUtils内部でarrayMinFinder/arrayMaxFinderを保持しmin/maxメソッドでそれに処理を移譲する。
これによって、arrayMinFinder.reduceなどのメソッド等、内部情報を隠蔽できる。コンポジションと呼ばれるテクニックである。
また、ArrayUtilsはクラスメソッドを使用しているのでnewでインスタンスを作る必要はない。このようなクラスは静的クラスと呼ばれている。

まとめ: コードはわかりやすく簡潔に書くべきである。