Özyinelemeli işlevler nasıl hafızaya alınır? Böyle bir işlev memoize nasıl</p> <pre><code>let rec gcd a b = let (q, r) = (a/b, a mod b) in if r = 0 then b else gcd b r </code></pre> <p>(Bu basitleştirilmiş, çok kırılgan tanımıdır.):

Question

bir özyinelemeli fonksiyon düşünün, Öklid algoritması tarafından tanımlanan demek? Fonksiyonun belleğe eklenmesini ekleyen bir yüksek işlevli fonksiyonun memoize : ('a -> 'b) -> ('a -> 'b) tanımlanmasının klasik yaklaşımı burada işe yaramaz, çünkü sadece ilk aramaya zaman kazandıracak.

• How do I memoize a recursive function in Lisp?
• Memoization with recursion

Bu öneriler sembol tanımını üzerine yazmak Lisp'te bulunan yeteneğine güvenmek:

Ben Lisp veya Haskell böyle işlevini memoize nasıl ayrıntıları bulduk Bir fonksiyonun ya da Haskell tarafından kullanılan “ihtiyaca göre” stratejisi ve bu nedenle OCaml'de faydasızdır.

Answer 1

kazanan stratejisi devam geçen tarzda içinde memoized için özyinelemeli işlevi tanımlamaktır:, bir argüman eklemek yinelemeli gcd_cont fonksiyonunu tanımlamak yerine

let gcd_cont k (a,b) = 
    let (q, r) = (a/b, a mod b) in 
    if r = 0 then b else k (b,r) 

, “devam” olduğu Yinelenen yerine çağırdı. Şimdi, bir devam argümanına sahip fonksiyonlar üzerinde çalışan iki yüksek-sıralı fonksiyon, call ve memo tanımlarız. Bu özel bir şey yapmaz ama f çağıran bir işlev g kurar

let call f = 
    let rec g x = 
     f g x 
    in 
    g 

: İlk fonksiyon, call tanımlanır.

let memo f = 
    let table = ref [] in 
    let compute k x = 
     let y = f k x in 
     table := (x,y) :: !table; y 
    in 
    let rec g x = 
     try List.assoc x !table 
     with Not_found -> compute g x 
    in 
    g 

Bu işlevler aşağıdaki imzaları vardır: İkinci fonksiyon memo bir işlev g uygulayan Memoization oluşturur. Kitapta https://realworldocaml.org/v1/en/html/imperative-programming-1.html#memoization-and-dynamic-programming: Burada bölümünü okumalısınız

let gcd_call a b = 
    call gcd_cont (a,b) 

let gcd_memo a b = 
    memo gcd_cont (a,b) 

Answer 2

# let memoize f = 
    let table = Hashtbl.Poly.create() in 
    (fun x -> 
     match Hashtbl.find table x with 
     | Some y -> y 
     | None -> 
     let y = f x in 
     Hashtbl.add_exn table ~key:x ~data:y; 
     y 
    );; 
val memoize : ('a -> 'b) -> 'a -> 'b = <fun> 


# let memo_rec f_norec x = 
    let fref = ref (fun _ -> assert false) in 
    let f = memoize (fun x -> f_norec !fref x) in 
    fref := f; 
    f x 
    ;; 
val memo_rec : (('a -> 'b) -> 'a -> 'b) -> 'a -> 'b = <fun> 

:

val call : (('a -> 'b) -> 'a -> 'b) -> 'a -> 'b = <fun> 
val memo : (('a -> 'b) -> 'a -> 'b) -> 'a -> 'b = <fun> 

Şimdi gcd fonksiyonun iki sürümü, memoization olmadan ilk ve memoization ikincisi tanımlar Gerçek Dünya OCaml.

Bu, memo'un nasıl çalıştığını gerçekten anlamanıza yardımcı olacaktır.