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

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

# 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 работает быстро только в том случае, если точный ввод был замечен ранее.

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


r memoization memoise
person kmace    schedule 10.09.2015    source источник

Ответы (1)


arrow_upward
6
arrow_downward

Думаю, причина проста. В медленном случае функция 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), и поэтому они запомнены.

Что действительно работает, так это запоминание функции позже, после того, как она будет определена. Итак, просто переопределение функции fib() на fib <- memoise(fib) будет работать.

person Stibu    schedule 10.09.2015
comment
Продолжение: Предположим, вы уже определили fib - как бы вы его запомнили? Подставить что-нибудь в теле функции? - person Frank; 10.09.2015
comment
@Frank - Recall полезно избегать таких ситуаций. Если вы пишете рекурсивные функции в R, вам следует использовать Recall - person Dason; 10.09.2015
comment
@ Дейсон Круто, не знал, что есть такая функция. Похоже, что пакет Memoise не предназначен для этого случая, если я правильно понимаю. Я вижу одинаковые сроки для fib <- function(n) {if (n < 2) return(1); Recall(n - 2) + Recall(n - 1)} и ffib <- memoise(fib) - person Frank; 10.09.2015
comment
Это потому, что внутренние выдумки уже были оценены? Я понимаю, что внутренние выдумки не запоминаются, но я изо всех сил пытаюсь понять, почему это не так? - person kmace; 10.09.2015
comment
Мемоизированная версия fib хранится fib_not_so_fast. Сам fib никогда не сохраняется как мемоизированная функция. - person Stibu; 10.09.2015