13日の金曜日

たまたま、以下の日記を見つけて読んでみて、自分ならどうやって13日の金曜の数を数えるかなーと思った。
http://d.hatena.ne.jp/yarb/20090105/p1
問題は「それぞれの年の13日の金曜日の日数を計算して列挙する」。

初めはこう書いた(ruby1.8)

require 'date'
def friday?(date)
  date.wday == 5
end

def jason(from,to)
  (from..to).inject(Hash.new(0)) do |h,y|
    h[y] = (1..12).inject(0){ |c,m| friday?(Date.new(y,m,13))? (c+1) : c}
    h
  end
end

jason(1990,2010).sort.each{ |y,n| puts("#{y}:#{n}")}

でも、1.9ならこんな風に書かないなと思った。

1.9ならObject#tapとEnumerable#countを使うかもしれない。

def jason(from,to)
  Hash.new(0).tap do |h|
    (from..to).each{ |y| h[y] = (1..12).count{ |m| friday?(Date.new(y,m,13))}}
  end
end

jason(1990,2010).each{ |y,n| puts("#{y}:#{n}")}

そのあと、別に列挙するだけならhashに格納する必要ないかもとか思った。

map使おう

def jason(from, to)
  (from..to).map{ |y| [y, (1..12).count{|m| friday?(Date.new(y,m,13))}]}
end

jason(1990,2010).each{ |(y,n)| puts("#{y}:#{n}")}

ArrayとHashの違い

mapを使って結果を格納すると年を利用したO(1)の探索が使えない。*1
もしすべての実行結果を列挙しないとすると、目的の年にjasonが現れた日の数を知るのにO(N)のコストがかかってしまう。そう考えると、Hashに格納した方がいいのかもしれない。*2

Cからプログラミングを始めた人だと、上みたいな書き方はしないのかもしれない。

たぶん、出力部分も含めてループで書くような気がする。

def jason(from,to) #cを求める時にinjectを使う人もいるかもしれない。
  (from..to).each do |y|
    c = 0
    (1..12).each { |m| c += 1 if friday?(Date.new(y,m,13))}
    puts("#{y}:#{c}")
  end
end

jason(1990,2010)

メモリ効率はいいんだけど何だか使いづらい。
もちろん、題意から考えれば列挙するだけで充分なんだけど、計算する部分と結果を出力する部分が一緒になっていると気持ちが悪い。出力と計算は分離させておきたいなーと思う。

あと、（今回の問題はそうでもないけど）コストの高い計算処理をしたい場合には遅延評価的なものが使いたくなるような気がする。*3

すべての計算結果を格納しておく必要ないかも

そもそも、全部の答えをあらかじめ格納して置く必要はないかもしれない。今回みたいな多くても100くらいの要素数の場合には全部の計算結果を格納した状態でも対応できるけど、要素数が数万とか数十万くらいになると全部の計算結果を格納しておくようにすると、メモリを無駄遣いすることになる。

必要な時に計算して、答えをキャッシュしておくようにすればいいかもしれない。例えば、こんな感じに

class Jason
  def initialize
    @mem = { }
    @month = (1..12).to_a
  end

  def appeared_number(year)
    @mem[year] || calc(year)
  end

  private
  def calc(year)
  　@month.count{ |month| friday?(Date.new(year,month,13))}.tap do |re|
      puts "calc #{year}"
      @mem[year] = re
    end
  end
end

j = Jason.new
puts(j.appeared_number(1990))
puts(j.appeared_number(1990))

# >> calc 1990
# >> 2
# >> 2

実際のところrubyのHash.newはブロックをとれるのでこんな面倒なことしなくてもいい。

jason = Hash.new do |h,y| 
  puts("calc #{y}")
  h[y] = (1..12).count{ |m| friday?(Date.new(y,m,13))}
end

puts jason[1990]
puts jason[1990]
# >> calc 1990
# >> 2
# >> 2

そう考えると、こんな感じに書くのがいい気がする。

jason = Hash.new{|h,y| h[y] = (1..12).count{ |m| friday?(Date.new(y,m,13))} }
(1990..2000).each{ |y| puts("#{y}:#{jason[y]}")}

*1:javascriptだと疎な配列を作るので、そんなこともないけど、

*2:計算した方がコストが安い場合には、わざわざ格納しておく必要もないかも。その場その場で毎回計算すればいいのかもしれない。

*3:言語レベルの遅延評価じゃなくても、iteratorオブジェクトを返す程度で充分