Ich hoffe, ihr hattet Spaß mit Challenge 4. Wenn ihr in Zukunft eine Idee für eine gute Challenge habt, lasst es mich gerne wissen. Ich bin immer auf der Suche nach gutem Material!
Herzlichen Glückwunsch, @landon ! Du hattest die schnellsten (nicht-personalisierten) Beiträge sowohl für die 100 Paare mit 1.000 Ziffern (9,88 Sek.) als auch für die längste Ziffer (7.150). Es war nicht nur das einzige Skript, das alle 100 Paare mit 1.000 Ziffern in unter 10 Sekunden lesen konnte (das nächstbeste schaffte nur 10), sondern konnte auch zwei Zahlen multiplizieren, die 3,5-mal größer waren als der nächstbeste Eintrag! Außerdem war es mit knapp über 1.000 Zeichen das kürzeste aller Skripte (personalisiert und nicht-personalisiert). Ich habe es in die folgenden Skripte aufgenommen. Die Gesamtpunktzahl nach vier Herausforderungen lautet:
Bevor wir über die Multiplikation großer Zahlen sprechen, wollen wir über das Entpacken oder Vektorisieren einer Ziffernfolge sprechen – also darüber, wie man eine Ziffernfolge in einen Zahlenvektor umwandelt. Wie wir letzten Monat gesehen haben, ist das Parsen einer Ziffernfolge einzeln mit Substr in einer Schleife unglaublich langsam. Damit haben wir zwei allgemeine Alternativen: 1) die Zeichenfolge in einzelne Einheiten zerlegen und diese dann wieder in eine Form zusammensetzen, die in einen Vektor umgewandelt werden kann (beispielsweise mit Parse ) oder 2) Mustervergleich verwenden. Ich würde zunächst zu Ansatz 1 tendieren. Jahrelang habe ich mich dagegen gesträubt, etwas über die Mustervergleichsfunktionen von JSL zu lernen. Der Aufwand war zu groß, die Informationen und Beispiele zu spärlich und ich war zu faul. Ich dachte, mit der Regulärer Ausdruck -Funktion, die ich sehr gut kannte, hätte ich alles, was ich brauchte. Damit ist jetzt Schluss.
Diese Herausforderungen haben mir die Augen für die Geschwindigkeit und Effizienz der Mustererkennung geöffnet. Wie mir @Craige_Hales , der für diese Funktionen verantwortliche Entwickler und regelmäßiger Teilnehmer der Herausforderungen, erklärt hat, bilden die Mustererkennungsroutinen in JSL die Grundlage, auf der Regulärer Ausdruck aufbaut. Um ihre Effizienz zu demonstrieren, führen Sie den Code in Vektorisierungsbeispiel.JSL aus, der vier verschiedene Vektorisierungsmethoden vergleicht. Ich habe im Skript auch eine kurze Funktion zum Generieren einer langen Zeichenfolge aus Zufallszahlen eingefügt. Bei einer Zeichenfolge aus 10.000 Zahlen ist das Parsen der Ziffern einzeln in einer Schleife bei weitem am langsamsten und dauert auf meinem Computer etwa 11 Sekunden. Die Verwendung von Words und Concat-Liste zum Zerlegen und Rekonstruieren der Ziffern in eine Zeichenfolge, die in einen Vektor geparst werden kann, ist um Welten besser (0,0965 Sek.).
Dasselbe Ergebnis mit „Regulärer Ausdruck“ und „Parse“ ist etwas besser (0,08543). Mustervergleich verkürzt diese Zeit um das Vierfache (0,02179)! Während die Zeitunterschiede bei 50.000 Ziffern minimal sind, dauern beide Parse-Ansätze bei 5.000.000 Ziffern etwa 10 Minuten, während Mustervergleich 2 Sekunden benötigt und im Gegensatz zu den anderen Methoden nahezu linear skaliert! Wenn Sie mehr über Mustervergleich in JSL erfahren möchten, werfen Sie einen Blick auf die Skripte von @Craige_Hales oder @David_Burnham ( der selbst einige Blogbeiträge mit weiteren Informationen und Beispielen verfasst hat).
Weiter zu den Multiplikationsroutinen. Für alle Vektorisierungen wird Mustervergleich verwendet. Außerdem werden im ersten Beispiel die schnellsten Additionsalgorithmen aus der letzten Challenge verwendet. Der erste Ansatz ( multiplicateBig Slow.JSL ) verwendet nichts über das hinaus, was wir bisher in den Challenges gelernt haben. Er multipliziert Ziffern jeweils zwei auf einmal und stellt sicher, dass je nach Position des Multiplikanden und Multiplikators Nullen hinzugefügt werden (z. B. werden fünf Nullen hinzugefügt, wenn eine Ziffer aus der Hunderterstelle mit einer Ziffer aus der Zehnerstelle multipliziert wird). Obwohl die Funktion die Eingaben so ordnet, dass die erste größer ist, hat dies keinen Vorteil. Es wird die gleiche Anzahl von Operationen ausgeführt. Dies wird sich im letzten Beispiel jedoch ändern. Die Funktion ist langsam und benötigt fast 30 Sekunden, um einen Satz von 100 100-stelligen Zahlen zu verarbeiten.
In multiplyBig Faster.JSL wird die Anzahl der Ziffern in einem Register von eins auf sieben erhöht, ungefähr die Hälfte der Anzahl Ziffern, 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 Ziffern umfassen kann. Da ein siebenstelliges Register 14 Ziffern enthalten kann, muss die im letzten Beispiel verwendete Additionsroutine so geändert werden, dass alles über die siebte Ziffer hinaus in das nächste Register übertragen wird. Trotzdem ist der resultierende Code erheblich kürzer, da nur positive Zahlen berücksichtigt werden müssen. Zudem verbessern sich die Ergebnisse bei der Multiplikation von 100 100-stelligen Zahlenpaaren erheblich (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 arbeiten. Anstatt jeweils ein Register zu multiplizieren, verwendet multiplyBig Fastest.JSL JSL-Matrixoperationen, um jedes Register der kürzeren Zahl mit der gesamten größeren Zahl zu multiplizieren. Dieser Ansatz ist schneller als der vorherige und benötigt für 100 Paare mit je 1.000 Ziffern nur 0,3015 Sekunden – eine fünffache Verbesserung.
Und es geht noch schneller. Die Datei multiplyBig – Brady.JSL war beim Multiplizieren von 1000-stelligen Zahlen zwar etwas langsamer, war aber bei Zahlen ab 2000 Stellen überlegen. Dies wurde durch eine Änderung der Operationsreihenfolge erreicht, sodass Multiplikationen und Additionen in derselben Schleife ausgeführt werden konnten. Die Details hierzu würden meinen Rahmen sprengen, aber @brady_brady teilte mir mit, dass er gern eine kurze Beschreibung verfasst, die ich bei Interesse diesem Post hinzufügen kann. Schneller? Vielleicht. In der Kryptologie werden typischerweise zwei bemerkenswerte Multiplikationsalgorithmen verwendet, die die Anzahl der Multiplikationsoperationen von O( n² ) auf O(n 1,58 ) oder weniger reduzieren. Da sie mehr Additionsoperationen mit großen Zahlen erfordern, ist schwer zu sagen, ob sie in JSL schneller wären. Zum Zeitpunkt dieses Posts habe ich versucht, eine schnelle JSL-Version dieser Algorithmen zu implementieren, konnte dies aber nicht.
1. August 2020: Danke an @Craige_Hales für den Fehler in multiplyBig Fastest.JSL . Ich habe das Problem behoben. Außerdem habe ich Craiges multiplyBig-Skript hinzugefügt, was ich eigentlich vorhatte, aber vergessen hatte. Er verwendet Nachschlagetabellen, um den Algorithmus zu beschleunigen (mit einigen Einschränkungen). Sein Skript ist wie immer ausführlich kommentiert.
