おはようございます
Rubyの高速アルゴリズムを学んでいて、メモ化再帰を見よう見まねで作って実践してみたのですが、かえって処理速度が遅くなりました........
書き方が間違っているのか、そもそもこの方法に向き不向きがあるのかわからないので、是非ともよろしくお願いいたします。
ruby
1require 'benchmark' 2 3#偶数 4N = 30 5 6#メモ化したもの 7@memo = {} 8def pair(n) 9 return @memo[n] if @memo.has_key?([n]) 10 return 1 if n == 0 || n == 2 11 12 sets = 0.step(n-2,2).map{|m| [n-2-m, m]} 13 sum = 0 14 sets.each do |set| 15 sum += pair(set[0]) * pair(set[1]) 16 end 17 return @memo[n] = sum 18end 19 20#通常 21def pair2(n) 22 return 1 if n == 0 || n == 2 23 24 sets = 0.step(n-2,2).map{|m| [n-2-m, m]} 25 sum = 0 26 sets.each do |set| 27 sum += pair2(set[0]) * pair2(set[1]) 28 end 29 return sum 30end 31 32time1 = Benchmark.realtime do 33 p pair(N) 34end 35time2 = Benchmark.realtime do 36 p pair2(N) 37end 38 39puts time1 #7.035736680991249 40puts time2 #3.0549034029972972 41
回答1件
あなたの回答
tips
プレビュー
バッドをするには、ログインかつ
こちらの条件を満たす必要があります。
2016/06/29 01:27