Различные техники запоминания в Ruby - PullRequest
Новая
       4

Различные техники запоминания в Ruby

4 голосов
/ 27 февраля 2011

Если вы являетесь программистом ruby, возможно, вы столкнулись с шаблоном запоминания хеш-блоков. Для простого примера я представляю вам запомненную версию последовательности Фибоначчи: 

fib_hash = Hash.new do |h,i|
  h[i] = h[i-1] + h[i-2]
end
# establish the base cases
fib_hash[1] = 1; fib_hash[2] = 1

Конечно, это не единственный способ создать запомненную версию последовательности Фибоначчи. Вы также можете сделать следующее: 

@cache = {}; @cache[1] = 1; @cache[2] = 1
def memo_fib(n)
  @cache[n] ||= (memo_fib(n-1) + memo_fib(n-2))
end

Надеюсь, вы видите, как шаблон запоминания хеш-блоков отображается на вторую версию, которая гораздо чаще встречается во многих других языках. Я хотел бы знать, есть ли разница между двумя версиями? Я не могу избавиться от ощущения, что версия хеш-блока более эффективна, но я не могу доказать, почему.

1 Ответ

5 голосов
/ 27 февраля 2011

Ориентир в МРТ 1.8.7:

  • Блок хеширования: 0,44 секунды
  • Блок без хэша: 0,41 секунды

А в МРТ 1.9.0:

  • Блок хеширования: 0,24 секунды
  • Блок без хэша: 0,28 секунды

Эталонный тест - 100 итераций для вычисления чисел Фибоначчи от 1 до 1000 с сбросом хеша или кэша в начале каждой итерации.

Вот эталонный тест для блока хеша: 

def reset_fib_hash                                                              
  @fib_hash = Hash.new do |h,i|
    h[i] = h[i-1] + h[i-2]
  end
  # establish the base cases                                                    
  @fib_hash[1] = 1; @fib_hash[2] = 1
end

start_time = Time.now
100.times do
  reset_fib_hash
  (1..1000).each do |i|
    @fib_hash[i]
  end
end
p Time.now - start_time

Вот эталонный тест для блока без хэша: 

def reset_fib_hash
  @cache = {}; @cache[1] = 1; @cache[2] = 1
end

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

start_time = Time.now
100.times do
  reset_fib_hash
  (1..1000).each do |i|
    memo_fib(i)
  end
end
p Time.now - start_time
...