Ich habe Project Euler begonnen und bin zu Problem Nummer 9 . Da ich Project Euler verwendet habe, um Haskell zu lernen, entschied ich mich, List Comprehensions zu verwenden (wie in Learn You A Haskell ). Ich mache das und GHCI braucht eine Weile, um das Triplett herauszufinden, was ich aufgrund der Berechnungen für normal halte. Jetzt, gestern bei der Arbeit (ich arbeite noch nicht professionell als Programmierer) sprach ich mit einem Freund, der VBA kennt und er wollte versuchen, die Antworten in VBA zu finden. Ich dachte, es wäre auch eine lustige Herausforderung, und ich mache ein paar grundlegende for-Schleifen und if-Aussagen, aber was mich dazu brachte, war, dass es viel schneller war als Haskell.
Meine Frage ist: Sind Haskells Listenverständnis unglaublich ineffizient? Zuerst dachte ich, es wäre nur, weil ich im interaktiven Modus von GHC war, aber dann wurde mir klar, dass VBA auch interpretiert wird.
Bitte beachten Sie, dass ich meinen Code nicht gepostet habe, weil es eine Antwort auf das Projekt euler ist. Wenn es meine Frage beantwortet (wie ich etwas falsch mache), werde ich gerne den Code veröffentlichen.
[Bearbeiten]
Hier ist mein Haskell Listenverständnis:
[(a,b,c) | c <- [1..1000], b <- [1..c], a <- [1..b], a+b+c=1000, a^2+b^2=c^2]
Ich denke, ich könnte den Bereich auf c gesenkt haben, aber ist das das, was es wirklich verlangsamt?
Es gibt zwei Dinge, die Sie mit diesem Problem tun könnten, die Ihren Code verlangsamen könnten. Einer ist, wie Sie Werte für a, b und c versuchen. Wenn Sie alle möglichen Werte für a, b, c von 1 bis 1000 durchlaufen, werden Sie viel Zeit aufwenden. Um einen Hinweis zu geben, können Sie a + b + c = 1000 verwenden, wenn Sie es für c neu anordnen. Der andere ist, dass wenn Sie nur ein Listenverständnis verwenden, es jeden möglichen Wert für a, b und c verarbeiten wird. Das Problem sagt Ihnen, dass es nur eine eindeutige Zahlengruppe gibt, die das Problem erfüllt. Wenn Sie also Ihre Antwort ändern:
%Vor%zu:
%Vor%Haskells faule Bewertung bedeutet, dass es aufhört, nachdem die erste Antwort gefunden wurde. Dies ist das Haskell-Äquivalent zum Aufbrechen Ihrer VBA-Schleife, wenn Sie die erste Antwort finden. Als ich diese beiden Tipps benutzte, hatte ich eine Antwort, die sehr schnell (unter einer Sekunde) in ghci abgeschlossen wurde.
Nachtrag: Ich vermisste zuerst die Bedingung a & lt; b & lt; c. Sie können dies auch in Ihren Listen-Comprehensions verwenden; Es gilt, Dinge zu sagen wie folgt:
%Vor%Betrachten Sie diese vereinfachte Version Ihres Listenverständnisses:
%Vor%Dies ergibt alle möglichen Kombinationen von a, b und c. Es ist ungefähr so, als würde man sagen: "Wie viele Wege können drei eintausendseitige Würfel landen?" Die Antwort lautet 1000 * 1000 * 1000 = 1.000.000.000 verschiedene Kombinationen. Wenn die Generierung jeder Kombination 0,001 Sekunden in Anspruch nimmt, dauert es 1.000.000 Sekunden (~ 11,5 Tage), bis alle Kombinationen abgeschlossen sind. (OK, 0,001 Sekunden ist eigentlich ziemlich langsam für einen Computer, aber Sie bekommen die Idee)
Wenn Sie Ihrem Listenverständnis Prädikate hinzufügen, benötigt es immer noch die gleiche Zeit für die Berechnung. Tatsächlich dauert es länger , da es das Prädikat für jede der 1 Milliarde Kombinationen, die es berechnet, überprüfen muss.
Betrachte nun dein Verständnis. Es sieht so aus, als ob es viel schneller sein sollte, oder?
%Vor%Es gibt 1000 Möglichkeiten für c. Wie viele gibt es für b und a? Nun, die durchschnittliche Wahl für c ist 500. Für alle Möglichkeiten von c gibt es dann durchschnittlich 500 Möglichkeiten für b (da b zwischen 1 und c liegen kann). Ebenso gibt es für alle Wahlmöglichkeiten von c und b durchschnittlich 250 Wahlmöglichkeiten für a. Das ist sehr hand-wellig, aber ich bin mir ziemlich sicher, dass es genau ist. Also 1000 Auswahlmöglichkeiten für c * 1000/2 Auswahlmöglichkeiten für b * 1000/4 Auswahlmöglichkeiten für a = 1 Milliarde / 8 ~ = 100 Millionen. Es ist 8x schneller, aber wenn du darauf achtest, wirst du feststellen, dass es sich tatsächlich um die gleiche große-oh-Komplexität handelt wie die vereinfachte Version oben. Wenn wir "vereinfachte" gegenüber "verbesserten" Versionen des gleichen Problems vergleichen, aber von [1..100000] statt von [1..1000], wäre das "verbesserte" immer noch nur 8x schneller als das "vereinfachte".
Versteh mich nicht falsch, 8x ist eine wundervolle Konstante-Faktor-Beschleunigung. Aber wenn Sie nicht ein paar Stunden warten wollen, um die Lösung zu bekommen, müssen Sie einen besseren Big-Oh bekommen.
Wie Neil bemerkt, ist die Methode, um die Komplexität dieses Problems zu reduzieren, für einen gegebenen b und c der a , der a+b+c=1000 erfüllt. Auf diese Weise versuchen Sie nicht, eine Menge von a s auszufallen. Dieser Wille lässt die Groß-Oh-Komplexität fallen; Sie werden nur etwa 1000 * 500 * 1 = 500.000 Kombinationen anstelle von ~ 100.000.000 in Betracht ziehen.
Sobald Sie die Lösung für das Problem gefunden haben, können Sie sich auf der Project Euler-Website andere Versionen von Haskell-Lösungen ansehen, um eine Vorstellung davon zu bekommen, wie andere das Problem gelöst haben. Übrigens, hier ist ein Link zu dem referenzierten Problem: Ссылка
Zusätzlich zu dem, was alle anderen über das Generieren von weniger Elementen in den Generatoren gesagt haben, können Sie auch anstelle von Integer als Typ der Zahlen Int verwenden. Der Standardwert ist Integer, aber Ihre Zahlen sind klein genug, um in einen Int.
zu passen(Auch zum Nitpick haben Haskell-Listen-Comprehensions keine Geschwindigkeit. Haskell ist eine Sprachdefinition mit sehr wenig operativer Semantik. Eine bestimmte Haskell-Implementierung könnte jedoch langsame Listen-Comprehensions enthalten.)
Tags und Links haskell vba performance list-comprehension