質問をすることでしか得られない、回答やアドバイスがある。

15分調べてもわからないことは、質問しよう!

新規登録して質問してみよう
ただいま回答率
85.50%
Ruby

Rubyはプログラミング言語のひとつで、オープンソース、オブジェクト指向のプログラミング開発に対応しています。

Q&A

解決済

1回答

1886閲覧

rubyでメモ化再帰(?)を使ったら遅くなってしまいました

dialbird

総合スコア379

Ruby

Rubyはプログラミング言語のひとつで、オープンソース、オブジェクト指向のプログラミング開発に対応しています。

0グッド

0クリップ

投稿2016/06/29 01:14

おはようございます

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

気になる質問をクリップする

クリップした質問は、後からいつでもMYページで確認できます。

またクリップした質問に回答があった際、通知やメールを受け取ることができます。

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

guest

回答1

0

ベストアンサー

@memo.has_key?([n])では、[n]という「配列全体」をキーにしたものを探してしまうため、数字だけで入れたものは見つかりません。@memo.has_key?(n)としましょう。

なお、Ruby特有の技ですが、Hash#default_procを使うことで、メモ化を簡潔に書くことができます

投稿2016/06/29 01:23

maisumakun

総合スコア145123

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

dialbird

2016/06/29 01:27

maisumakunさん 昨日に引き続き、迅速なご返答、恐縮です ありがとうございます。そのような便利なものもあるとは........。 早速使ってみます。
guest

あなたの回答

tips

太字

斜体

打ち消し線

見出し

引用テキストの挿入

コードの挿入

リンクの挿入

リストの挿入

番号リストの挿入

表の挿入

水平線の挿入

プレビュー

15分調べてもわからないことは
teratailで質問しよう!

ただいまの回答率
85.50%

質問をまとめることで
思考を整理して素早く解決

テンプレート機能で
簡単に質問をまとめる

質問する

関連した質問