ich den Unterschied zwischen der AusführungEffizienz der strukturellen Rekursion vs Endrekursion
factorial 0 = 0
factorial n = n * factorial (n-1)
und
factorial 0 r = r
factorial n r = factorial (n-1) (r * n)
Wich ist performanter wissen?
Ich bin mir nicht sicher, ob das auch ist. Die erste wird n-1 im Mustertest für 0 auswerten, wird aber einen Stapel von Multiplikationen erzeugen, der nicht ausgeführt werden kann, bis er 0 erreicht. Die zweite erzeugt denselben Stapel, der im r Argument gespeichert ist. Der Vorteil des zweiten ist jedoch, dass Sie das r Argument strikt machen können und im Konstanten Raum rein tail rekursiv sein können, da seine Multiplikationsreihenfolge mit der Aufrufreihenfolge übereinstimmt.
Wir können die erste Version als factorial n = foldr (*) 1 [n,n-1..1] und die zweite als factorial n = foldl (*) 1 [n,n-1..1] interpretieren. Daher ist der Unterschied in der Strenge für r der gleiche wie zwischen foldl und foldl'. Aber wenn die Liste lang ist und die Operation abkürzen kann, indem das zweite Argument nicht untersucht wird, erhält die foldr Version einen bemerkten Vorteil.
Die zweite Version wird durch die GHC-Bedarfsanalyse für typische numerische Typen korrekt optimiert Verwenden Sie "-O" oder "-O2". – dfeuer
Es ist am besten, dass Sie einige Messungen/Benchmarks mit Kriterium durchführen und einige Heap-Profile ausführen. Es gibt ein Kapitel in Resl World Haskell über Heap-Profile und Kriterium hat eine gute Dokumentation. Und es ist eine einfache Aufgabe für einen Anfänger, nicht mit – epsilonhalbe
überwältigt zu werden. Eine Sache, die ich euch ermutigen würde, herumzuspielen, ist das Hinzufügen von Varianten mit Strictness-Annotationen (mit 'BangPatterns') und verschiedenen Optimierungsstufen' -O0' .. '- O2' und Varianten mit Typ-Signaturen. – epsilonhalbe
Haben Sie irgendwelche Benchmarks gemacht, bevor Sie diese Frage gestellt haben? – AJFarmar