Help us understand the problem. What is going on with this article?

メモ化を知った

More than 5 years have passed since last update.

はじめに

あんまりRuby関係ないんですが、一応、The RSpec Bookを読んでいて知ったのがきっかけなので…。

あらすじ

The RSpec Book のletの解説には以下のように記述されています。

sample.rb
   describe "テストコードはてきとう" do
     let(:test) { "TEST" }
     it "test let" do
       test.should == "TEST"
     end
   end

メソッドが最初に呼び出されたときに戻り値がキャッシュされ、それ以降、同じスコープ内でメソッドが呼び出されるたびにキャッシュされた値が返されることを意味します。

これをメモ化というそうです。で、メモ化って?

一番簡単なメモ化

調べてみると、だいたいフィボナッチ数を求める例が多い。なのでn番目のフィボナッチ数を求めるメソッドを書いてみる。

普通に書いた場合

fib1.rb
def f(n)
  if n <= 1 then
    n
  else
    f(n-1) + f(n-2)
  end
end

実行していくと、己のPCスペックではf(30) = 832040 くらいからマシンがもたついてきた。

これを メモ化 してみる。

メモ化した場合

fib2.rb
# こっちは変わらず
def f(n)
  if n <= 1 then
    n
  else
    f(n-1) + f(n-2)
  end
end
def f_memo(n)
  @cache ||= []
  @cache[n] ||= f(n)
end

実行すると、最初の一発目は同じくらい遅いんだけど、一回実行すればキャッシュとして @cache に格納されるので二回目以降はバク速で求められる。

||= とは

上の例の @cache[n] ||= f(n)@cache[n] = @cache[n] || f(n) と同義。@cache[n]が真ならば@cache[n]を返す。偽ならnのフィボナッチ数を求める。 @cache[n]が真ならば、f(n)は評価しない、実行しない 。だから早い。

||=の例。

irb(main):001:0> a          # 未定義の時はエラー
NameError: undefined local variable or method `a' for main:Object
from (irb):1
from C:/rubies/Ruby-193-p0/bin/irb:12:in `<main>'
irb(main):002:0> a ||= 500  # a || 500 a は偽なので500
=> 500
irb(main):003:0> a
=> 500
irb(main):004:0> b = 0
=> 0
irb(main):005:0> b
=> 0
irb(main):006:0> b ||= 500  # b || 500 b は真なので0のまま
=> 0
irb(main):007:0> b
=> 0

…って所まで調べて、初めてのRubyを読み返してみたらバッチリ書いてあるし!!

初期化イディオム として紹介されていました。。。

Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
Comments
No comments
Sign up for free and join this conversation.
If you already have a Qiita account
Why do not you register as a user and use Qiita more conveniently?
You need to log in to use this function. Qiita can be used more conveniently after logging in.
You seem to be reading articles frequently this month. Qiita can be used more conveniently after logging in.
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
ユーザーは見つかりませんでした