perché queste funzioni memorizzate sono diverse?

Question

Vedo che se uso memoise su una funzione in due modi diversi, ottengo due comportamenti diversi e mi piacerebbe capire perché.

# 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)) 

Strategia 1, è davvero veloce, in quanto riutilizza i risultati ricorsive, mentre stratagy 2 è solo veloce se l'ingresso esatto è stato visto prima.

Qualcuno può spiegarmi perché questo è?

Answer 1

Penso che la ragione sia semplice. Nel caso lento, la funzione fib_not_as_fast viene memorizzata. All'interno della funzione, viene chiamato fib, che è non memoised. Per essere più dettagliato: quando si calcola lo fib_not_so_fast(24), all'interno della funzione si ha fib(22) + fib(23). Entrambi questi non sono stati registrati.

In fib_fast, tuttavia, si utilizza la versione memorizzata anche nella ricorsione. Quindi, in questo caso, fib_fast(24) deve valutare fib_fast(22) + fib_fast(23). Entrambe queste chiamate di funzione sono già avvenute, quando hai calcolato fib_fast(23) e sono quindi memoise.