Ich habe den Code der Implementierung von (^) der Standard-Haskell-Bibliothek gelesen:
%Vor%Nun ist dieser Teil, in dem g definiert ist, mir seltsam, warum sollte man es nicht einfach so implementieren:
%Vor%Aber in der Tat sagen 3 ^ 1000000 ein, dass (^) etwa 0,04 Sekunden schneller als Expo ist.
Warum ist
(^)schneller alsexpo?
Eine Funktion ist tail-rekursiv, wenn der Rückgabewert eines rekursiven Aufrufs ohne weitere Verarbeitung unverändert zurückgegeben wird. In expo , f ist nicht tail-rekursiv, da otherwise = x * f x (y-1) : Der Rückgabewert von f wird vor der Rückgabe mit x multipliziert. Sowohl f als auch g in (^) sind tail-rekursiv, da ihre Rückgabewerte unverändert zurückgegeben werden.
Warum ist das wichtig? Tail-rekursive Funktionen können viel effizienter als allgemeine rekursive Funktionen implementiert werden. Da der Compiler für einen rekursiven Aufruf keinen neuen Kontext (Stapelrahmen, was Sie haben) erstellen muss, kann er den Kontext des Aufrufers als Kontext des rekursiven Aufrufs wiederverwenden. Dies spart viel Aufwand beim Aufruf einer Funktion, ähnlich wie das Einfügen einer Funktion effizienter ist als das Aufrufen der Funktion.
Als die Person, die den Code geschrieben hat, kann ich Ihnen sagen, warum es komplex ist. :) Die Idee besteht darin, tail-rekursiv zu sein, um Schleifen zu erhalten und auch die minimale Anzahl von Multiplikationen durchzuführen. Ich mag die Komplexität nicht. Wenn Sie also einen eleganteren Weg finden, reichen Sie bitte einen Fehlerbericht ein.
Immer wenn man in der Standard-Bibliothek eine Brot-und-Butter-Funktion sieht und diese merkwürdig umgesetzt wird, liegt der Grund fast immer darin, "weil es so eine spezielle performance-kritische Optimierung auslöst [möglicherweise in einer anderen Version des Compilers] ".
Diese seltsamen Problemumgehungen sind normalerweise, um den Compiler zu "zwingen", zu bemerken, dass eine bestimmte, wichtige Optimierung möglich ist (z. B. um zu erzwingen, dass ein bestimmtes Argument als streng angesehen wird, um eine Worker / Wrapper-Transformation zu erlauben). Typischerweise hat jemand sein Programm kompiliert, es ist episch langsam, hat sich bei den GHC-Entwicklern beschwert und sie haben sich den kompilierten Code angeschaut und gedacht: "Oh, GHC sieht nicht, dass es diese dritte Arbeitsfunktion inline ... wie kann ich repariere das?" Wenn Sie den Code nur geringfügig umformulieren, wird die gewünschte Optimierung ausgelöst.
Sie sagen, Sie haben es getestet und es gibt nicht viel Geschwindigkeitsunterschied. Du hast nicht für welchen Typ gesagt. (Ist der Exponent Int oder Integer ? Was ist mit der Basis? Es ist durchaus möglich, dass es in einem obskuren Fall einen signifikanten Unterschied macht.)
Gelegentlich werden Funktionen auch seltsam implementiert, um Strenge / Faulheitsgarantien zu gewährleisten. (Zum Beispiel sagt die Bibliotheksspezifikation, dass sie auf eine bestimmte Art und Weise arbeiten muss, und ihre Implementierung auf die offensichtlichste Art und Weise würde die Funktion strenger / weniger streng machen als die Spezifikationsansprüche.)
Ich weiß nicht, was los ist mit dieser spezifischen -Funktion, aber ich würde vorschlagen, @chi ist wahrscheinlich auf etwas.
Tags und Links haskell performance