Memoisierung eines einzelnen Parameters in einer Multiparameter-Funktion in Haskell

Question

Ich lösen this programming problem, und ich überschreite das Zeitlimit mit meiner aktuellen Lösung. Ich glaube, dass die Lösung meines Problems die Memoisierung ist. Allerdings verstehe ich die Memoization-Lösungen nicht dokumentiert here.

Hier ist die primäre Funktion in meiner aktuellen Lösung.

maxCuts :: Int -> Int -> Int -> Int -> Int 
maxCuts n a b c 
    | n == 0 = 0 
    | n < 0  = -10000 
    | otherwise = max (max amax bmax) cmax 
    where 
     amax = 1 + maxCuts (n - a) a b c 
     bmax = 1 + maxCuts (n - b) a b c 
     cmax = 1 + maxCuts (n - c) a b c 

Diese Funktion dauert zu lange, wenn b und c relativ zu n klein sind. Ich würde einfach die Lösung kopieren, die sie für die faktorielle Funktion verwendet haben, aber diese Funktion benötigt nur einen Parameter. Ich habe vier Parameter, aber ich möchte nur die Memoization auf den ersten Parameter, n. Beachten Sie, dass sich ab und c in den rekursiven Aufrufen nicht ändern.

Answer 1

Ihre Funktion Definition wie folgt umschreiben:

maxCuts :: Int -> Int -> Int -> Int -> Int 
maxCuts n a b c = maxCuts' n where 
    maxCuts' n 
      | n == 0 = 0 
      | n < 0  = -10000 
      | otherwise = max (max amax bmax) cmax 
      where 
       amax = 1 + maxCuts' (n - a) 
       bmax = 1 + maxCuts' (n - b) 
       cmax = 1 + maxCuts' (n - c) 

Jetzt haben Sie eine einargumentigen Funktion Sie memoize können.

Answer 2

Beiseite: Ist Ihr Algorithmus nicht gerade etwas wie div n (minimum [a,b,c])?

Wie Sie bereits erwähnt haben, ändern sich die Parameter a, b und c nicht, also schreiben Sie zuerst die Funktion neu, um den Parameter n am Ende zu platzieren.

Wenn Sie sich entscheiden, eine Liste zu verwenden, die Funktion es Werte erfordert ein wenig Pflege memoize sicher GHC machen die abgebildeten Liste speichern:

import Debug.Trace 

maxCuts' :: Int -> Int -> Int -> Int -> Int 
maxCuts' a b c n = memoized_go n 
    where 
    memoized_go n 
     | n < 0 = -10000 
     | otherwise = mapped_list !! n 

    mapped_list = map go [0..] 

    go n | trace msg False = undefined 
     where msg = "go called for " ++ show n 
    go 0 = 0 
    go n = maximum [amax, bmax, cmax] 
     where 
     amax = 1 + memoized_go (n-a) 
     bmax = 1 + memoized_go (n-b) 
     cmax = 1 + memoized_go (n-c) 

test1 = print $ maxCuts' 1 2 3 10 

Notiere die zirkuläre Abhängigkeit der Definitionen: memoized_go abhängt mapped_list was von go abhängt, was von memozied_go abhängt.

Da Listen nur nicht-negative Indizes zulassen, muss der Fall n < 0 in einem separaten Schutzmuster behandelt werden. Die trace Aufrufe zeigen, dass go nur einmal pro Wert n aufgerufen wird. Betrachten wir zum Beispiel versuchen, dies zu tun, ohne mapped_list zu definieren:

maxCuts2 :: Int -> Int -> Int -> Int -> Int 
maxCuts2 a b c n = memoized_go n 
    where 
    memoized_go n 
     | n < 0 = -10000 
     | otherwise = (map go [0..]) !! n 
    -- mapped_list = map go [0..] 
    go n | trace msg False = undefined 
     where msg = "go called for " ++ show n 
    go 0 = 0 
    go n = maximum [amax, bmax, cmax] 
     where 
     amax = 1 + memoized_go (n-a) 
     bmax = 1 + memoized_go (n-b) 
     cmax = 1 + memoized_go (n-c) 

test2 = print $ maxCuts2 1 2 3 11 

Lauf test2 zeigt, dass go mehrfach für den gleichen Wert von n genannt wird.

aktualisiert

zu vermeiden Um große unevaluierten Thunks zu schaffen, würde ich BangPatterns verwenden für amax, bmax und cmax:

{-# LANGUAGE BangPatterns #-} 

maxCuts' ... = 
    ... 
    where 
    !amax = 1 + ... 
    !bmax = 1 + ... 
    !cmax = 1 + ...