Фибоначчи с Рубином

Question

Это была проблема, которую я решил:

@cache={}
@cache[1]=0
@cache[2]=1

def fib(n)
  @fibs[n-1]
end

def fib_m(n)
  @cache[n] ||= fib_m(n-1) + fib_m(n-2)
end

@fibs=[]
@fibs=(1..100000).map{|n| fib_m(n)}

Но это выглядит глупо. Кажется, я удваиваю кеширование, и мне приходится жестко кодировать какой-то верхний предел. Есть ли более чистый способ сделать это?

Answer 1

Есть ли более чистый способ сделать это?

Вы можете назначить default_proc для динамического вычисления недостающих значений хеш-функции:

fib = { 0 => 0, 1 => 1 }
fib.default_proc = ->(f, n) { f[n] = f[n-1] + f[n-2] }

fib[10]
#=> 55

fib
#=> {0=>0, 1=>1, 2=>1, 3=>2, 4=>3, 5=>5, 6=>8, 7=>13, 8=>21, 9=>34, 10=>55}

Обратите внимание, что этот подход ограничен размером стека Ruby.

Answer 2

Если вы включите оптимизацию хвостовых вызовов в Ruby, вы можете достичь того же результата рекурсивно, который быстрее, меньше потребляет память и более элегантен.

RubyVM::InstructionSequence.compile_option = {
  tailcall_optimization: true,  
  trace_instruction: false  
}

def fib(curr = 1, acc = 0, n)
  n <= 0 ? acc : fib(acc, curr + acc, n - 1)
end

fib(100_000).to_s.length
#⇒ 20899