Nochmals vielen Dank an alle, die teilgenommen haben, und vielen Dank für Ihre Geduld mit diesem späten Beitrag. Jeder konnte die Herausforderungen meistern. Sowohl die größten hinzugefügten Zahlen (ca. 2 Millionen Ziffern) als auch die größte Liste mit 1.000 Ziffern (ca. 2.000 Elemente) wurden von Nicht-JMP-Mitarbeitern gemeistert @David_Burnham . Bei den Personaleinträgen betrugen die größten zwei Zahlen, die unter 5 Sekunden hinzugefügt wurden, etwa 22 Millionen ( @brady_brady Und @Craige_Hales ) und die größte Liste umfasste etwa 61.500 Elemente ( Herausforderung 3 Beispiel 3.JSL ). Diese Skripte wurden unten veröffentlicht.
Hier sind die Gesamtpunktzahlen für drei Herausforderungen:
Beginnen wir mit Operationen mit zwei Zahlen. Herausforderung 3 Beispiel 1 – slow.JSL stellt eine Implementierung bereit, die den meisten Einträgen ähnelt:
- Bestimmen Sie, ob die Zahlen gleiche (Addition) oder entgegengesetzte (Subtraktion) Vorzeichen haben.
- Analysieren Sie die Zahlenzeichenfolge.
- Führen Sie die Additions-/Subtraktionsoperationen durch.
- Verketten Sie die Ergebnisse, um die Antwort zu erstellen.
Ob Additions- und Subtraktionsoperationen in einer einzelnen Funktion oder in mehreren Funktionen ausgeführt werden, ist eine Frage des Stils und sollte sich nur auf die Klarheit und Lesbarkeit des Programms, nicht aber auf die Ausführungszeit auswirken. Was jedoch einen großen Unterschied machen wird, ist die Art und Weise, wie Eingabezahlen analysiert und wieder zusammengesetzt werden. Analysieren der Eingabezeichenfolgen vor dem Durchlaufen der einzelnen Ziffern ( Herausforderung 3 Beispiel 1 – schneller.JSL ) anstatt innerhalb der Schleife beschleunigt den Vorgang um etwa das Fünffache (2,28 Sek. vs. 0,464 Sek. für das Addieren von 2 Zahlen mit 16.000 Ziffern). Das Entfernen der einzelnen Zeichenfolgenverkettungen aus den Schleifen durch Sammeln der Ergebnisse in einer Liste und anschließendes Verketten der Elemente am Ende beschleunigt die Arbeit um mehr als das Zehnfache (0,04054 Sek.) – siehe (Herausforderung 3 Beispiel 1 – schnellste.JSL).
Bevor wir darüber sprechen, wie wir dies noch schneller machen können, sollten wir über das Hinzufügen von Zahlen zu einer Liste sprechen. Fast jeder löste dieses Problem, indem er die Liste einzeln durchging und jedes Element zu einer laufenden Summe addierte. Obwohl dies letztendlich nicht der schnellste Ansatz war, konnte er außergewöhnlich schnell durchgeführt werden ( Herausforderung 3 – Hales.JSL 51.000 1000-stellige Zahlen in weniger als 5 Sekunden hinzugefügt). Wie bei den meisten Vorgängen liegt der Schlüssel zur Geschwindigkeitsverbesserung darin, die Anzahl der Vorgänge zu minimieren, wenn alle Bedingungen gleich bleiben. Im bereitgestellten Beispiel Herausforderung 3 Beispiel 2.JSL bestand die Lösung darin, die Carry/Borrow-Operationen von einem Satz für jedes Zahlenpaar auf insgesamt drei Sätze zu reduzieren. Dies wurde erreicht durch:
- Laden der Eingabezahlen in zwei Matrizen, eine für positive Zahlen und eine für negative Zahlen.
- Fügen Sie jede Matrix separat hinzu mit V Summe , führen Sie einen Satz Übertragsoperationen für die beiden Ergebnismatrizen durch.
- Subtrahieren Sie die kleinere Zahl von der größeren Zahl. Führen Sie einmal eine Reihe von Ausleihvorgängen durch, um die Ergebnisse zu erhalten. Die endgültige Subtraktion wird unter Verwendung des oben erläuterten Zwei-Zahlen-Algorithmus durchgeführt.
Sowohl Zwei-Zahlen- als auch Listenoperationen können noch schneller durchgeführt werden, indem bei den Übertrags-/Ausleihoperationen mehr als eine Ziffer gleichzeitig berücksichtigt wird. Dies wurde in beiden Fällen durchgeführt Herausforderung 3 – Hales.JSL Und Herausforderung 3 – Brady.JSL . Während die natürliche Neigung darin besteht, mit einer Zahl zu addieren/subtrahieren/tragen/leihen, kann das Verfahren mit etwas Einfallsreichtum auf so viele Zahlen wie möglich verallgemeinert werden, vorausgesetzt, dass kein Überlauf auftritt. In JMP , das wären 14 Ziffern für den Zwei-Zahlen-Fall und 14 – Etage(Log10( listSize – 1)) Ziffern , Wo listSize ist die Anzahl der Elemente in der Eingabeliste im Listenfall. Um zu verstehen, warum das so ist, erinnern Sie sich daran, dass der Überlauf etwa um 9e16 auftritt. Das Addieren der beiden größten 15-stelligen Zahlen (fünfzehn Neunen) führt zu einem Überlauffehler. Das Addieren der beiden größten 14-stelligen Zahlen funktioniert nicht. Ebenso führt das Addieren von 9.999.999.999.999 zu sich selbst zu einem Überlauf, wenn es zwischen 11 und 100 Mal (um genau zu sein 91 Mal) ausgeführt wird.
Als Beispiel dafür, wie dies funktionieren könnte, betrachten Sie das Hinzufügen von drei Zahlen, wobei jede Zahl in 14er-Registern angeordnet ist:
11 99999999999999
22 99999999999999
33 99999999999999
Durch Summieren der Werte aus dem ersten Register (die 14 9er) erhalten Sie
2 99999999999997
Wenn Sie die 2 tragen und das zweite Register summieren, erhalten Sie
68
Die endgültige Zahl ist
68 99999999999997
Die Anwendung dieses Ansatzes ist in angegeben Herausforderung 3 Beispiel 3.JSL . Die durchschnittliche Verarbeitungszeit für das Addieren von zwei 2-Millionen-stelligen Zahlen verbessert sich von 4,7 auf 0,82 Sekunden, was einer mehr als fünffachen Geschwindigkeitsverbesserung entspricht. Zusätzliche Optimierungen können die Geschwindigkeit um ein weiteres Zweifaches verbessern, wie gezeigt wird Herausforderung 3 – Hales.JSL Und Herausforderung 3 – Brady.JSL Die zum Addieren von 10.000 1000-stelligen Zahlen erforderliche Zeit wird von 4,5 auf 0,88 Sekunden (5X) reduziert. Dies führt zum schnellsten Ansatz zum Hinzufügen von Listen.
20. Juli 2020: Noch eine Fehlerbehebung, diesmal um Herausforderung 3 Beispiel 3.JSL . Warnmeldungen hinzugefügt, wenn ein Matrixargument für alle drei Dateien von Beispiel 1 verwendet wird (erst implementiert in Beispiel 2).
17. Juli 2020: Ich habe einen weiteren Fehler in den Skripten von Challenge 3 Beispiel 1 gefunden und alle drei wurden behoben und ersetzt.
16. Juli 2020 : Ich habe die Skripte ersetzt Herausforderung 3 Beispiel 1 – slow.JSL Und Herausforderung 3 Beispiel 1 – schneller.JSL weil sie am Ende eine Zeile enthielten, die ein Problem verursachte (sie verweisen auf eine Tabelle, die ich zum Testen des Codes verwendet habe). Wenn Sie diese Dateien heruntergeladen und das Problem nicht selbst behoben haben, ersetzen Sie bitte Ihre älteren Kopien.
