Haskell: Code läuft zu langsam

Question

ich einen Code haben, der eine Motzkin Nummer wie berechnet:

module Main where 

    -- Program execution begins here 
    main :: IO() 
    main = interact (unlines . (map show) . map wave . (map read) . words) 

    -- Compute Motzkin number 
    wave :: Integer -> Integer 
    wave 0 = 1 
    wave 1 = 1 
    wave n = ((3 * n - 3) * wave (n - 2) + (2 * n + 1) * wave (n - 1)) `div` (n + 2) 

Aber die Ausgabe auch nur eine einfache Zahl wie 30 dauert eine Weile zurück.

Irgendwelche Optimierungsideen ??

Answer 1

Mit n = 30, müssen Sie wave 29 und wave 28 berechnen, was wiederum berechnen muss wave 28, wave 27 zweimal und wave 26 und so weiter, das geht schnell in die Milliarden.

Sie können den gleichen Trick verwenden, die bei der Berechnung der Fibonacci-Zahlen verwendet:

wave 0 = 1 
wave 1 = 1 
wave n = helper 1 1 2 
    where 
     helper x y k | k <n  = helper y z (k+1) 
        | otherwise = z 
        where z = ((3*k-3) * x + (2*k+1) * y) `div` (k+2) 

Dies läuft in linearer Zeit, und die Helfer, die für jeden k die Werte für wave (k-2) und wave (k-1) bereit.

Answer 2

hier ist eine memoized Version

wave = ((1:1:map waveCalc [2..]) !!) 
    where waveCalc n = ((2*n+1)*wave (n-1) + (3*n-3)*wave (n-2)) `div` (n+2) 

Answer 3

Es gibt eine Standard-Trick ist, die Fibonacci-Zahlen für die Berechnung, die sich leicht auf Ihr Problem angepasst werden kann. Die naive Definition für Fibonacci-Zahlen ist:

fibFunction :: Int -> Integer 
fibFunction 0 = 1 
fibFunction 1 = 1 
fibFunction n = fibFunction (n-2) + fibFunction (n-1) 

Dies ist jedoch sehr kostspielig: da alle Blätter der Rekursion sind 1, wenn fib x = y, dann müssen wir y rekursive Aufrufe durchführen! Da die Fibonacci-Zahlen exponentiell anwachsen, ist dies ein schlechter Zustand. Aber mit der dynamischen Programmierung können wir die Berechnungen teilen, die in den zwei rekursiven Aufrufen benötigt werden. Das gefällige Ein-Liner für dieses sieht wie folgt aus:

fibList :: [Integer] 
fibList = 1 : 1 : zipWith (+) fibList (tail fibList) 

Dies kann zunächst ein wenig verwirrend aussehen; Hier dient das fibList Argument zu zipWith als die Rekursion auf zwei Indizes, während das tail fibList Argument als die Rekursion auf einem Index agiert, der uns die und fib (n-1) Werte gibt. Die beiden 1 s am Anfang sind natürlich die Basisfälle. Es gibt other good questions here on SO, die diese Technik im Detail erklären, und Sie sollten diesen Code und diese Antworten studieren, bis Sie das Gefühl haben, dass Sie verstehen, wie es funktioniert und warum es sehr schnell ist.

Bei Bedarf kann die Signatur vom Typ Int -> Integer unter Verwendung von (!!) wiederhergestellt werden.

Lassen Sie uns versuchen, diese Technik auf Ihre Funktion anzuwenden. Wie bei der Berechnung von Fibonacci-Zahlen benötigen Sie die vorherigen und vorletzten Werte. und benötige zusätzlich den aktuellen Index. Dies kann durch Einschließen von [2..] in den Anruf zu zipWith erfolgen. Hier ist, wie es aussehen würde:

waves :: [Integer] 
waves = 1 : 1 : zipWith3 thisWave [2..] waves (tail waves) where 
    thisWave n back2 back1 = ((3 * n - 3) * back2 + (2 * n + 1) * back1) `div` (n + 2) 

Nach wie vor kann man die Funktionsversion mit (!!) oder genericIndex erholen (wenn man wirklich Integer Indizes benötigt).Wir können bestätigen, dass es die gleiche Funktion berechnet (aber schneller und weniger Speicher benötigt wird) in GHCI:

> :set +s 
> map wave [0..30] 
[1,1,2,4,9,21,51,127,323,835,2188,5798,15511,41835,113634,310572,853467,2356779,6536382,18199284,50852019,142547559,400763223,1129760415,3192727797,9043402501,25669818476,73007772802,208023278209,593742784829,1697385471211] 
(6.00 secs, 3,334,097,776 bytes) 
> take 31 waves 
[1,1,2,4,9,21,51,127,323,835,2188,5798,15511,41835,113634,310572,853467,2356779,6536382,18199284,50852019,142547559,400763223,1129760415,3192727797,9043402501,25669818476,73007772802,208023278209,593742784829,1697385471211] 
(0.00 secs, 300,696 bytes) 

Answer 4

Vielen Dank allen für Ihre Antworten. Basierend auf meinem Verständnis von Memoization, ich habe neu geschrieben, den Code als:

mwave :: Int -> Int 
mwave = (map wave [0..] !!) 
    where wave 0 = 1 
     wave 1 = 1 
     wave n = ((3 * n - 3) * mwave (n - 2) + (2 * n + 1) * mwave (n - 1)) `div` (n + 2) 

digits :: Int -> Int 
digits n = (mwave n) `mod` 10^(100::Int) 

keine Gedanken darüber, wie die Antwort auf Ausgang 100 Modulo 10 ^?