Einfache Tipps für Haskell-Leistung erhöht (auf ProjectEuler Probleme)?

9

Ich bin neu beim Programmieren und Lernen von Haskell, indem ich Projekte Euler-Probleme lese und durcharbeite. Natürlich ist es am wichtigsten, einen besseren Algorithmus zu verwenden, um die Leistung bei diesen Problemen zu verbessern. Es ist jedoch für mich klar, dass es andere einfache und einfach zu implementierende Möglichkeiten gibt, die Leistung zu verbessern. Eine kursorische Suche brachte diese Frage und diese Frage , die die folgenden Tipps geben:

  • Verwenden Sie die ghc flags -O2 und -fllvm.
  • Verwenden Sie den Typ Int anstelle von Integer, da es nicht mit der Box versehen ist (oder sogar Integer anstelle von Int64). Dazu müssen die Funktionen eingegeben werden, damit der Compiler nicht spontan entscheiden kann.
  • Verwenden Sie rem, nicht mod, für Divisionstests.
  • Verwenden Sie gegebenenfalls Schwartzsche Transformationen .
  • Verwendung eines Akkumulators in rekursiven Funktionen (eine Tail-Recursion-Optimierung, glaube ich).
  • Memoisierung (?)

(Eine Antwort erwähnt auch die Umwandlung von Arbeitern / Wrappern, aber das scheint ziemlich weit fortgeschritten zu sein.)

Frage: Welche anderen einfachen Optimierungen kann man in Haskell machen, um die Leistung bei Problemen mit dem Projekt Euler zu verbessern? Gibt es andere Haskell-spezifische (oder funktionale programmierungsspezifische?) Ideen oder Funktionen, die verwendet werden könnten, um Lösungen für Project Euler-Probleme zu beschleunigen? Umgekehrt, worauf sollte man achten? Was sind einige häufige, aber ineffiziente Dinge zu vermeiden?

    
Potato 14.07.2012, 07:05
quelle

4 Antworten

13

Hier sind einige gute Folien von Johan Tibell, auf die ich mich häufig beziehe:

Haskell-Leistungsmuster

    
jtobin 14.07.2012 12:37
quelle
6

Ein einfacher Vorschlag ist die Verwendung von hlint , einem Programm, das Ihren Quellcode prüft und Vorschläge zur Syntaxverbesserung macht. Dies erhöht möglicherweise nicht die Geschwindigkeit, da es höchstwahrscheinlich bereits vom Compiler oder der Lazy Evaluation ausgeführt wird. Aber es könnte in einigen Fällen dem Compiler helfen. Außerdem wird es Sie zu einem besseren Haskell-Programmierer machen, da Sie bessere Methoden lernen werden, und es könnte einfacher sein, Ihr Programm zu verstehen und es zu analysieren.

Beispiele aus Ссылка wie:

%Vor%

und

%Vor%

Ich denke, die größten Verbesserungen, die Sie in Project Euler-Problemen machen können, sind das Verständnis des Problems und das Entfernen unnötiger Berechnungen. Selbst wenn Sie nicht alles verstehen, können Sie ein paar kleine Fehler beheben, die Ihr Programm doppelt so schnell laufen lassen. Angenommen, Sie suchen nach Primzahlen bis zu 1.000.000, dann können Sie natürlich filter isPrime [1..1000000] . Aber wenn Sie ein wenig nachdenken, dann können Sie das gut erkennen, keine gerade Zahl ist eine Primzahl, da haben Sie (ungefähr) die Hälfte der Arbeit entfernt. Stattdessen macht [1,2] ++ filter isPrime [3,5..999999]

    
Viktor Mellgren 14.07.2012 12:30
quelle
5

Es gibt einen ziemlich großen Teil des Haskell-Wikis über die Leistung.

Ein ziemlich häufiges Problem ist zu wenig (oder zu viel) Strenge (dies wird durch die Abschnitte abgedeckt, die in den Allgemeinen Techniken aufgeführt sind Abschnitt der Performance-Seite oben). Zu viel Faulheit bewirkt, dass eine große Anzahl von Thunks angesammelt wird, zu viel Strenge kann dazu führen, dass zu viel bewertet wird.

Diese Überlegungen sind besonders wichtig beim Schreiben von rekursiven Schwanzfunktionen (d. h. solche mit einem Akkumulator); Und je nachdem, wie die Funktion verwendet wird, ist eine rekursive Tail-Funktion in Haskell manchmal weniger effizient als die entsprechende nicht-tail-rekursive Funktion, selbst bei den optimalen Strictness-Annotationen.

Wie durch diese neue Frage demonstriert wurde, kann Sharing auch dazu beitragen großer Unterschied zur Leistung (in vielen Fällen kann dies als eine Form der Memoisierung angesehen werden).

    
huon 14.07.2012 07:38
quelle
3

Beim Projekt Euler geht es hauptsächlich darum, clevere algorithmische Lösungen für die Probleme zu finden. Sobald Sie den richtigen Algorithmus haben, ist die Mikrooptimierung selten ein Problem, da selbst eine einfache oder interpretierte Implementierung (z. B. Python oder Ruby) innerhalb der Geschwindigkeitsbeschränkungen gut ablaufen sollte. Die wichtigste Technik, die Sie benötigen, ist das Verständnis der Lazy Evaluation, so dass Sie Thunk-Buildups vermeiden können.

    
solrize 15.07.2012 03:59
quelle

Tags und Links