Hoffentlich hattest du Spaß damit Herausforderung 4 . Wenn Sie in Zukunft eine Idee für etwas haben, das sich gut für eine Challenge eignet, lassen Sie es mich bitte wissen. Ich bin immer auf der Suche nach gutem Material!
Glückwunsch, @landon !Sie hatten die schnellsten Einträge (ohne Mitarbeiter) sowohl für die 100 Paare von 1.000 Ziffern (9,88 Sek.) als auch für die längste Ziffer (7.150). Es war nicht nur das einzige Skript, das in der Lage war, alle 100 Zahlenpaare mit 1.000 Ziffern in weniger als 10 Sekunden zu lesen (der nächstnächste konnte nur 10 schaffen), sondern es konnte auch zwei Zahlen multiplizieren, die 3,5-mal größer waren als der nächstnächste Eintrag! Darüber hinaus war es mit knapp über 1.000 Zeichen das kürzeste aller Skripte (für Mitarbeiter und Nicht-Mitarbeiter). Ich habe es in die folgenden Skripte eingefügt. Die Gesamtpunktzahl nach vier Herausforderungen beträgt:
Bevor wir über das Multiplizieren großer Zahlen sprechen, sprechen wir über das Entpacken oder Vektorisieren einer Ziffernfolge – also das Umwandeln einer Ziffernfolge in einen Zahlenvektor. Wie wir letzten Monat gesehen haben, analysiert man eine Ziffernfolge einzeln mit Substr in einer Schleife ist schmerzhaft langsam. Damit bleiben uns zwei allgemeine Alternativen: 1) Zerlegen der Zeichenfolge in einzelne Einheiten und anschließendes Zusammenfügen in eine Form, die in einen Vektor umgewandelt werden kann (mit Analysieren , zum Beispiel) oder 2) mit Mustervergleich. Meine anfängliche Neigung wäre, Ansatz 1 zu verwenden. Ich habe mich jahrelang geweigert, etwas über die JSL-Mustervergleichsfunktionen zu lernen. Der Aufwand war zu groß, die Informationen und Beispiele zu dürftig und ich war zu faul. Ich dachte, ich hätte alles, was ich brauchte Regex Funktion, etwas, das ich sehr gut kannte. Nicht mehr.
Diese Herausforderungen haben mir die Augen für die Geschwindigkeit und Effizienz des Mustervergleichs geöffnet. Wie mir erklärt wurde von @Craige_Hales , dem für diese Funktionen verantwortlichen Entwickler und regelmäßigen Teilnehmer der Herausforderungen, sind die Mustervergleichsroutinen in JSL die Grundlage dafür Regex ist gebaut. Um ihre Effizienz zu demonstrieren, führen Sie den Code aus Vektorisierungsbeispiel.JSL , das vier verschiedene Methoden der Vektorisierung vergleicht. Ich habe auch eine kurze Funktion zum Generieren einer langen Folge von Zufallszahlen in das Skript eingefügt. Bei einer Zeichenfolge mit 10.000 Zahlen ist das Parsen der Ziffern einzeln in einer Schleife bei weitem am langsamsten und dauert auf meinem Rechner etwa 11 Sekunden. Benutzen Wörter Und Concat-Liste Die Ziffern zu dekonstruieren und in eine Zeichenfolge umzuwandeln, die in einen Vektor analysiert werden kann, ist um Welten besser (0,0965 Sek.).
Machen Sie das Gleiche mit Regex Und Analysieren ist etwas besser als das (0,08543). Der Mustervergleich reduziert diese Zeit um das erstaunliche Vierfache (0,02179)! Während die Zeitunterschiede für 50.000 Ziffern winzig sind, dauern beide Parsing-Ansätze bei Betrachtung von 5.000.000 Ziffern etwa 10 Minuten, während der Mustervergleich 2 Sekunden dauert und im Gegensatz zu den anderen Methoden nahezu linear skaliert! Wenn Sie mehr über den Mustervergleich in JSL erfahren möchten, schauen Sie sich die von geschriebenen Skripte an @Craige_Hales oder @David_Burnham (Wer hat ein paar eigene Blogbeiträge mit weiteren Informationen und Beispielen .)
Weiter zu den Multiplikationsroutinen. Für die gesamte Vektorisierung wird der Mustervergleich verwendet. Darüber hinaus werden im ersten Beispiel die schnellsten Additionsalgorithmen aus der letzten Herausforderung verwendet. Der erste Ansatz ( multiplyBig Slow.JSL ) verwendet nichts über das hinaus, was wir bisher in den Herausforderungen gelernt haben. Es multipliziert jeweils zwei Ziffern und stellt sicher, dass abhängig von der Position des Multiplikanden und Multiplikators Nullen hinzugefügt werden (z. B. das Hinzufügen von fünf Nullen, wenn eine Ziffer der Hunderterstelle mit einer Ziffer der Zehnerstelle multipliziert wird). Obwohl die Funktion die Eingaben so anordnet, dass die erste größer ist, hat dies keinen Vorteil. Es wird die gleiche Anzahl an Operationen durchgeführt. Dies wird sich jedoch im letzten Beispiel ändern. Die Funktion ist langsam und benötigt fast 30 Sekunden, um einen Satz von 100 100-stelligen Zahlen durchzugehen.
In multiplyBig Faster.JSL Die Anzahl der Ziffern in einem Register wird von eins auf sieben erhöht, was ungefähr der Hälfte der Ziffern entspricht, die JSL ohne Überlauf darstellen kann. Der Grund für diese Wahl wird deutlich, wenn wir zwei große siebenstellige Zahlen multiplizieren, deren Ergebnis bis zu vierzehn Stellen betragen kann. Da ein siebenstelliges Register 14 Ziffern enthalten kann, muss die im letzten Beispiel verwendete Additionsroutine geändert werden, sodass alles, was über die 7. Ziffer hinausgeht, in das nächste Register übertragen wird. Trotzdem ist der resultierende Code erheblich kürzer, da nur positive Zahlen berücksichtigt werden müssen. Darüber hinaus verbessern sich die Ergebnisse erheblich, wenn 100 Zahlenpaare mit jeweils 100 Ziffern multipliziert werden (0,04375 Sek.). Diese Implementierung leistet auch bei der Multiplikation von 100 1000-stelligen Paaren gute Arbeit (1,54 Sek.).
Mit einer einfachen Änderung können Sie noch schneller vorankommen. Anstatt jeweils ein Register zu multiplizieren, multiplyBig Fastest.JSL verwendet JSL-Matrixoperationen, um jedes Register in der kürzeren Zahl mit der gesamten größeren Zahl zu multiplizieren. Dieser Ansatz ist schneller als der vorherige und beträgt 0,3015 Sekunden für 100 Paare mit je 1.000 Ziffern, was einer Verbesserung um das Fünffache entspricht.
Und Sie können noch schneller fahren. Die Datei multiplyBig – Brady.JSL , während es bei der Multiplikation von 1.000-stelligen Zahlen etwas langsamer ist, war überlegen, wenn die Größe der Zahlen etwa 2.000-stellige Zahlen und mehr erreichte. Dies wurde erreicht, indem die Reihenfolge der Operationen geändert wurde, sodass die Multiplikationen und Additionen in derselben Schleife durchgeführt werden konnten. Die Details dahinter gehen über das hinaus, was ich behandeln möchte, aber @brady_brady Er teilt mir mit, dass er gerne einen kurzen Beitrag verfassen würde, den ich bei Interesse zu diesem Beitrag hinzufügen kann. Schneller? Vielleicht. Es gibt zwei bemerkenswerte Multiplikationsalgorithmen, die typischerweise in der Kryptologie verwendet werden und die Anzahl der Multiplikationsoperationen von O(n) reduzieren 2 ) Zu An 1,58 ) oder untere . Da sie mehr Additionsoperationen mit großen Zahlen erfordern, ist es schwer zu sagen, ob sie in JSL schneller wären. Zum Zeitpunkt dieses Beitrags habe ich es versucht, konnte jedoch keine schnelle JSL-Version eines dieser Algorithmen implementieren.
1. Aug. 2020: Dank an @Craige_Hales für das Einfangen eines Käfers multiplyBig Fastest.JSL . Ich habe das Problem behoben. Ich habe auch Craiges multiplyBig-Skript hinzugefügt, was ich eigentlich tun wollte, aber vergessen habe. Er verwendet Nachschlagetabellen, um den Algorithmus zu beschleunigen (mit einigen Einschränkungen). Sein Drehbuch ist wie üblich gründlich kommentiert.
