Почему эти запомненные функции отличаются?

Question

Я вижу, что если я использую memoise для функции двумя разными способами, я получаю два разных поведения, и я хотел бы понять, почему.

# Non Memoised function
fib <- function(n) {
  if (n < 2) return(1)
  fib(n - 2) + fib(n - 1)
}

system.time(fib(23))
system.time(fib(24))

library(memoise)

# Memoisation stragagy 1
fib_fast <- memoise(function(n) {
  if (n < 2) return(1)
  fib_fast(n - 2) + fib_fast(n - 1)
})

system.time(fib_fast(23))
system.time(fib_fast(24))

# Memoisation strategy 2
fib_not_as_fast <- memoise(fib)

system.time(fib_not_as_fast(23))
system.time(fib_not_as_fast(24))

Стратегия 1 действительно быстрая, так как она использует рекурсивные результаты, тогда как стратегия 2 быстра, если точный ввод был замечен ранее.

Может кто-нибудь объяснить мне, почему это?

Answer 1

Я думаю, что причина проста. В медленном случае функция fib_not_as_fast запоминается. Внутри функции, fib называется, что не запомнилось. Чтобы быть более подробным: когда вы рассчитываете fib_not_so_fast(24)внутри функции у вас есть fib(22) + fib(23), Оба из них не были запомнены.

В fib_fastоднако запомненную версию вы также используете в рекурсии. Итак, в этом случае, fib_fast(24) необходимо оценить fib_fast(22) + fib_fast(23), Оба этих вызова функции уже произошли, когда вы рассчитали fib_fast(23) и таким образом запоминаются.