2009-11-10

Benchmark::Report.#reportとBenchmark.#measure

Benchmark::Repot.#reportのコード

require 'benchmark'

puts Benchmark::CAPTION
puts Benchmark.measure { "a"*1_000_000 }

=>

    user     system      total        real
1.166667   0.050000   1.216667 (  0.571355)

Benchmark.#measureのコード

require 'benchmark'

n = 50000
Benchmark.bm do |x|
  x.report { for i in 1..n; a = "1"; end }
  x.report { n.times do   ; a = "1"; end }
  x.report { 1.upto(n) do ; a = "1"; end }
end

=>

      user     system      total        real
  1.033333   0.016667   1.016667 (  0.492106)
  1.483333   0.000000   1.483333 (  0.694605)
  1.516667   0.000000   1.516667 (  0.711077)

#report、#measureではBenchmark::Tmsオブジェクトが返ってくる。Reportでは実行結果が標準出力されるが、＃measureではそれがないのが大きな違い。Tmsを使うことでその後の処理が自由になるのが特徴。

2009-11-08

カプセル化されたオブジェクト

プレーヤーとコンピューターで3回勝負のじゃんけんをします。その時の処理を言葉で書くと以下の考え方になります。

プレーヤの勝数が3以上であれば「プレーヤーの勝利」と表示、コンピュータの勝数が3以上であれば「コンピュータの勝利」と表示する

これを、カプセル化で考えると以下の考えになります。

プレーヤーが勝利していたら、「プレーヤーの勝利」を表示させる
コンピュータが勝利していたら、「コンピュータの勝利」と表示させる

カプセル化されたオブジェクトを呼び出す場合は、使役形となるのがポイントです。

カプセル化とは、プログラムをどうモジュールに分割するかという問題に対する解決方法の1つ。

2009-11-06

classについて

classには以下の役割がある。
+ オブジェクトが持つデータの情報を変数・定数にまとめる
+ オブジェクトが持つ手続きをメソッドにまとめる
+ インスタンスを作成するためのnewクラスメソッドの提供
クラスを定義することで、抽象的な概念を分類し名前を付けて利用する事が出来る。

インスタンス変数: オブジェクト処理対象となるデータを格納する変数で、オブジェクトと同じ寿命を持つ。

Rubyでは「@」で始まる変数をインスタンス変数とする。インスタンス変数の初期化はinitializeメソッド内で行う。

属性: 外部に公開するオブジェクトの状態

オブジェクトの状態はオブジェクト自身が管理しており、外部に紹介していない。インスタンス変数もオブジェクトの状態として、中に含まれている。インスタンス変数を外部へ紹介したい場合は、そのための設定するメソッドがある。値を参照するメソッド(リーダメソッド)、値を設定する(ライタメソッド)、二つを合わせたメソッド(アクセサメソッド)だ。

class Player
  def initialize()
    @point = 0
    @choice = nil
  end

  attr_accessor :choice
  attr_reader :point
end
player=Player.new()
player.choice = "hoge"
player.point = 1

※「attr_accessor :choice」の「:choice」はシンボル
choiceは値が変更できるが、pointは変更できない。このように、外部からインスタンス変数を簡単に操作することができる。

上記のようなクラスでは、値だけを持つオブジェクトが作られる。これを、値オブジェクトという。

2009-11-02

sortのブロックを使う素晴らしさ

sort関数では、引数にブロックを使います。なんでかと言うと、様々な順序で並び変えができるようにするためです。
例えばsort関数を使わないで自作でクイックソートの関数を作ります。以下はその一部分です。

def partitioning(data, pivot, left, right)
  while true
    while data[left] < pivot
      left +=1
    end
    while data[right] > pivot
      right -= 1
    end
    break if left >= right
    wk = data[left]
    data[left] = data[right]
    data[right] = wk
    left += 1
    right -= 1
  end
  return left, right
end

実行結果

ソート結果：[1, 3, 4, 9]

上記のように昇順になっています。これを降順にするには、

"data[left] < pivot" -> "data[left] > pivot"
"data[right] > pivot" -> "data[right] < pivot"

と書き換える必要があります。
sort関数を使うと

array = [1, 3, 4, 9]
sort{|x,y| x <=> y} #昇順
sort{|x,y| y <=> x} #降順

メソッドを書き直す必要がなくなります。

2009-11-02

ってなんじゃ

Rubyのインスタンスメソッドに<=>というメソッドがあります。見た時なんじゃコレとか思った。

<=>: self と other を ASCII コード順で比較して、 self が大きい時には正の整数、等しい時には 0、小さい時には負の整数を返します。

レシーバはstringからファイルの更新時刻・クラス/モジュールの比較もできるらしい。
ブロック引数を用いて比較する時は、要素同士のブロックを比較する。

irb(main):004:0* a = [5, 2, 6, 1, 19]
=> [5, 2, 6, 1, 19]
irb(main):005:0> a.sort() {|x,y| x<=>y}
=> [1, 2, 5, 6, 19]
irb(main):006:0> a.sort() {|x,y| y<=>x}
=> [19, 6, 5, 2, 1]
irb(main):007:0> a.sort() {|x,y| x<=>x}
=> [5, 2, 6, 1, 19]

2009-10-30

2分探索プログラム

2分探索のアルゴリズム

もし、探索開始よりも探索終了点の方が前にあった場合、探索失敗
探索領域の中間点のデータを調べる
中間データが探索データそのもの：探索成功
中間データが探索データより小さい：中間点より右側(中間点+1)を新たな探索開始点として自分自身を呼び出す。
中間データが探索データより大きい：中間点より左側(中間点-1)を新たな探索開始点として自分自身を呼び出す。

私の中では、1つ目が出て来なさそう。注意しよう。
2分探索のコード

# +data_to_find+::
#  検索対象データ
# +data+::
# 検索するデータが入った配列
# +startIdx+::
#  検索開始位置
# +endIdx+::
# 探索終了位置
#
# === 戻り値
# 見つかった位置を返す(先頭が0)。もし見つからなかったら-1を返す


  return -1 if startIdx > endIdx
  centerIdx = (startIdx + endIdx) / 2
  return centerIdx if data[centerIdx] == data_to_find
  if data[centerIdx] > data_to_find
    bsearch(data_to_find, data, startIdx, centerIdx - 1)
  else
    bsearch(data_to_find, data, centerIdx + 1, endIdx)
  end

data = []とかdata = [1]を試してみると最初のreturn ifの力は大きい。

2009-10-28

Rubyでクイックソート

最近、「van勉だぃありぃ〜読んでるよ」とか言われるから、なんか書くの恥ずかしくなった。

クイックソートをするメソッド書きました。

def qsort(data, left, right)
  return if left >= right # 位置から文字の長さを判別
  pivot = data[(left + right) / 2]
  l, r = partitioning(data, pivot, left, right)
  qsort(data, left, l - 1)
  qsort(data, r + 1, right)
end

クイックソートは

枢軸出す
枢軸以下のグループと枢軸以上のグループに分ける
各グループをさらにクイックソートしていく

以上の流れで行います。
私は3番目の各グループをさらにクイックソートしていく部分で悩んだんですけど、2つのグループを再帰呼び出しすればいいんですね。勉強になりました。

ソートするメソッドは以下。

def partitioning(data, pivot, left, right)
  while true
    while data[left] < pivot
      left +=1
    end
    while data[right] > pivot
      right -= 1
    end
    break if left >= right
    wk = data[left]
    data[left] = data[right]
    data[right] = wk
    left += 1
    right -= 1
  end
  return left, right
end

pratitioningメソッドは、qsortメソッド内で書こうと思っていました。でも、ソート処理が難しかったのでメソッド化して取り出しました。全体のコードを書いてから、後で難しい部分を作る。この方法をトップダウンな開発方法と呼ぶらしいです。
逆に、難しそうな処理を先に作ってしまい、後から本体となるプログラミングする方法をボトムアップな開発方法とう呼ぶ。