Hinweis: Ein Challenge-Beitrag von @David_Burnham wurde vor Ablauf der Frist eingereicht, aber von meinem E-Mail-System unter Quarantäne gestellt. Ich habe ihn erst nach der Veröffentlichung des ursprünglichen Blogbeitrags entdeckt. Ich aktualisiere die Ergebnisse, um die Änderungen aufgrund des neuen Beitrags zu berücksichtigen.
Vielen Dank an alle, die Code für Challenge 2 eingereicht haben. Die Punktevergabe war eine Herausforderung, da manche Codes bei kleineren und andere bei größeren Werten besser funktionierten. Die folgende Tabelle zeigt die Ergebnisse für jeden Teil der Challenge. Es gab drei Läufe für isPrime , 1000 5-stellige zufällige ungerade Zahlen, die nicht durch 5 teilbar sind, 8- und 9-stellige ungerade Zahlen, die nicht durch 5 teilbar sind, und 12- bis 15-stellige ungerade Zahlen, die nicht durch 5 teilbar sind. Die Ergebnisse basierten auf den letzten beiden Bedingungen. Die Punkte wurden auf die Challenges aufgeteilt, 1,5 Punkte für den 1. , 1 für den 2. und 0,5 für den 3. Platz . Die Zeiten für die schnellsten Einsendungen werden ebenfalls angegeben (in Sekunden).
@leelaim isPrime(Small) Die Zeit war so schnell wie jede andere von einem JMP-Mitarbeiter (+3 Punkte). @landon isPrime(Big) Das Skript verwendet die Funktion Parallel Assign zur Verbesserung der Geschwindigkeit. Zwei der Einträge haben ihre Ergebnisse für getPrimes mit Namespace zwischengespeichert. Dieser Ansatz ist hilfreich, wenn die Ergebnisse mehrmals abgerufen werden müssen (die Laufzeiten basieren jedoch auf nicht zwischengespeicherten Ergebnissen). Alle vier Einträge sind unten aufgeführt.
Hier ist die Bestenliste nach zwei Herausforderungen:
Herausforderung 3 wird am Mittwoch, den 1. Juni, veröffentlicht.
In Aufgabe 2 mussten Primzahlen auf zwei Arten gefunden werden. Bei einem positiven ganzzahligen Wert n mussten 1) n Primzahlen oder 2) alle Primzahlen unter n gefunden werden. Beginnen wir mit 2), da dies etwas einfacher zu implementieren ist. Die einfachste Methode zum Finden von Primzahlen ist die Probedivision. Ausgehend von 2 als Kandidat und einer leeren Menge von Primzahlen wird geprüft, ob irgendetwas aus der aktuellen Menge der Primzahlen die Kandidatenzahl ohne Rest teilt. Wenn nicht, wird es zur Menge der Primzahlen addiert und mit dem nächsten Kandidaten fortgefahren. Da die Primzahlmenge zu Beginn nichts enthält, wird 2 addiert. Beim Prüfen von 3 stellt sich heraus, dass diese nichts in {2} teilt und zur Primzahlmenge addiert wird. Die Zahl 4 teilt jedoch etwas in {2,3} und wird nicht addiert. Unten ist eine Beispielimplementierung dargestellt.
getPrimes2 = Function( {n}, {primeSet,i,j},
primeSet = [];
For(i=2,i<=n,i++,
For(j=2,j<=N Row(primeSet),j++,
If(Mod(i,j)==0, Break());
);
If(j>N Row(primeSet),primeSet = primeSet |/ i);
);
primeSet;
);
Dieser Ansatz bietet einige Vorteile: Er ist leicht verständlich, der Code ist prägnant und lässt sich problemlos an beide Primzahlfindungsaufgaben anpassen. Leider ist er extrem langsam. Für die Primzahlen unter 100.000 habe ich 19,43 Sekunden benötigt .
Ein etwas komplexerer Ansatz ist die Verwendung eines Siebes. Anstatt eine Zahl auf Primzahleigenschaft zu testen, testen Siebe Zahlen aus der Primzahleigenschaft. Das älteste und bekannteste ist das Sieb des Eratosthenes . Gehen Sie davon aus, dass alles Primzahlen sind. Beginnen Sie mit 2 als erster Primzahl. Suchen Sie alle Zahlen, die diese Zahl gleichmäßig teilen, und entfernen Sie sie aus der Primzahlmenge. Fahren Sie mit der nächsten Zahl fort, die noch in der Primzahlmenge ist. Unten sehen Sie eine nicht optimierte Version.
getPrimes2 = Function( {n}, {primeSet,i,j},
primeSet = J( n, 1, 1 );
primeSet[1] = 0;
For( i = 2, i <= n, i++,
For( j = i, j <= n / i, j++,
primeSet[j * i] = 0
)
);
Loc( primeSet );
);
Der offensichtlichste Vorteil ist die Geschwindigkeit. Meine Zeit für das Finden aller Primzahlen unter 100.000 betrug 0,2811 Sekunden, also etwa 70-mal schneller, und 3,4025 Sekunden für 1.000.000. Der Code ist dennoch prägnant und leicht verständlich. Ein kleiner Nachteil ist, dass Sie einen Vektor erstellen müssen, um Nicht-Primzahlen zu verfolgen (d. h. Sie können die Liste nicht durch Verkettung erweitern – was, wie wir später sehen werden, nicht unbedingt ein Vorteil ist). Dies erschwert das Finden von n Primzahlen, da Sie nicht genau wissen, wie groß der benötigte Vektor sein muss.
Nachfolgend sind zwei optimierte Versionen aufgeführt. Die erste entfernt zunächst alle Vielfachen von zwei und durchläuft dann nur die ungeraden Zahlen ab 3. Sqrt( n ) wird als Obergrenze der äußeren Schleife verwendet, da alle kleineren Nicht-Primzahlen bereits herausgefiltert wurden. Um beispielsweise alle Primzahlen unter 100 zu finden, müssen Sie nur bis 10 sieben. Die herausgesiebten Zahlen für jede Primzahl größer als 10 sind das Produkt dieser Primzahl multipliziert mit einer Zahl kleiner als 10, die mit einer anderen Primzahl entfernt wurde (beispielsweise wird 11*5 mit dem Sieb für 5 entfernt, 11*9 mit dem Sieb für 3 usw.). Diese Verbesserungen verkürzen die Laufzeit um mehr als die Hälfte auf 1,3545. Das zweite Beispiel zeigt den Vorteil der Verwendung der Matrixoperationen von JSL für die innere Schleife mit Zeiten von 0,01625 für 1.000.000 und 2,6694 für 100.000.000, eine fast 100-fache Verbesserung!
getPrimes2 = Function( {n}, {primeSet,i,j},
primeSet = J( n, 1, 1 );
primeSet[4::n::2] = 0;
primeSet[1] = 0;
For( i = 3, i <= Sqrt( n ), i+=2,
For( j = i, j <= n / i, j++,
primeSet[j * i] = 0
)
);
Loc( primeSet );
);
getPrimes2 = Function( {n}, {primeSet,i,j,upper},
primeSet = J( n, 1, 1 );
primeSet[4::n::2] = 0;
primeSet[1] = 0;
i = 3;
upper = Sqrt(n);
For(i=3,i<=upper,i+=2,
If(primeSet[i] == 1,
primeSet[(i*2)::n::i] = 0;
);
);
Loc( primeSet );
);
Geht das noch besser? Das Atkins-Sieb ist theoretisch effizienter und wurde in Primes Atkins Beispiel.JSL und Primes Atkins (optimiert).JSL implementiert. Ersteres bietet eine nicht optimierte und leichter verständliche Implementierung (2,236 Sekunden für 1.000.000). Besser als die nicht optimierte Version von Eratosthenes. Die optimierte Version konnte jedoch die optimierte Version von Eratosthenes nicht schlagen (4,914 Sekunden für 100.000.000). Darüber hinaus ist sie sowohl programmatisch als auch theoretisch deutlich länger und komplexer.
Wie wäre es mit dem Lesen aus einer Zahlentabelle? Das entspricht zwar nicht dem Schreiben eines Algorithmus, aber ich habe nicht gesagt, dass das nicht möglich ist. @Craige_Hales hat eine Lösung mit diesem Ansatz vorgeschlagen. Angesichts der Problemspezifikation, dass n 1e8 nicht überschreiten darf, benötigte das Skript zur Aufnahme der komprimierten Werte über 4 Millionen Zeichen Code, 4,6 MB Speicherplatz und etwa 5,5 Sekunden zum Laden, unabhängig von der Größe von n . Langsamer als die anderen Lösungen. Obwohl es weder die schnellste noch die kürzeste ist, habe ich Craiges Skript aufgrund seiner einzigartigen Herangehensweise an das Problem, der Verwendung von Komprimierung und Parallele Zuweisung aufgenommen.
Das Finden von n Primzahlen ist ein größeres Problem. Angenommen, Sie verwenden ein Sieb, dann müssen Sie einen Vektor von Werten bis zur n -ten Primzahl erstellen. Dazu muss eine Obergrenze für diesen Wert geschätzt werden. Eine Unterschätzung sollte vermieden werden, da sonst möglicherweise der gesamte oder ein Teil des Algorithmus erneut ausgeführt werden muss, um nicht gesiebte Werte zu finden. „Estimate value of nth prime.jmp“ zeigt sechs verschiedene Schätzungen. „Est1“ zeigt einen Fall, in dem Werte für kleine n unterschätzt werden. Viele Schätzungen gelten nur für n, die größer als ein bestimmter Wert sind, und in diesen Fällen muss darauf geachtet werden, alternative Schätzungen bereitzustellen. „Est2“ ist gut für n ≥ 13 und „Est3“ ist für größere Werte eine Verbesserung. Leider sind gute Grenzen selten einfach. „Est4“ wurde in „Primes fast submission.jsl“ verwendet. Obwohl es keine so gute Arbeit leistet und für sehr große n- Werte unterschätzt, ist es einfach und leicht zu merken. „Est5“ wurde mittels „Nonlinear“ mit den tatsächlichen Werten abgeleitet. Est6 verbessert Es ist5 durch leichtes Verfälschen der Werte, sodass keiner der Werte in der Tabelle unterschätzt wird. Es ist nicht garantiert, dass zwischen 100 und 1e8 keine Unterschätzungen auftreten. Die anderen Tabellenspalten geben die Unter-/Überschätzungen für jede Technik an.
Die Bestimmung der Primzahleigenschaft könnte ähnlich wie die Generierung von Primzahlen erfolgen. Bei einer gegebenen Zahl x könnte man i = 2 setzen. Wenn Mod( n , i ) == 0 , stoppen, andernfalls i erhöhen. Weitermachen, bis Mod( n , i ) == 0 oder i == n . Der folgende Code profitiert davon, dass nach dem ersten Test bei i = 2 nur ungerade i -Werte geprüft werden und gestoppt wird, wenn i > = Ceiling(Sqrt( n )) .
isPrime = Function({inVals},{i,j,outVec,nextVal,uBound},
outVec = J(N Row(inVals),1,-1);
For(i=1,i<=N Row(inVals),i++,
nextVal = inVals[i];
If(Mod(nextVal,2) == 0,
outVec[i] == 0;
,//ELSE
j = 3;
uBound = Ceiling(Sqrt(nextVal));
While(j < uBound & Mod(nextVal,j) != 0, j+=2);
If(j >= uBound, outVec[i] = 1,outVec[i] = 0);
)
);
outVec;
);
Das obige Skript benötigt etwa 1,4 Sekunden, um alle 1.000 acht- und neunstelligen Zahlen in der Tabelle Tabelle der großen Zahlen.jmp ( Klein ) zu überprüfen.
Um dies weiter zu verbessern, können Sie einen Vektor von Primzahlen (bis zu Ceiling(Sqrt( n )) ) generieren und diese durchlaufen.
getPrimes = Function( {n}, {primeSet,i,j,upper},
primeSet = J( n, 1, 1 );
primeSet[4::n::2] = 0;
primeSet[1] = 0;
i = 3;
upper = Sqrt(n);
For(i=3,i<=upper,i+=2,
If(primeSet[i] == 1,
primeSet[(i*2)::n::i] = 0;
);
);
Loc( primeSet );
);
isPrime = Function({inVals},{i,j,outVec,primeVec,nextVal},
outVec = J(N Row(inVals),1,-1);
primeVec = getPrimes(Ceiling(Sqrt(Max(inVals))));
For(i=1,i<=N Row(inVals),i++,
nextVal = inVals[i];
j=1;
While(j < N Row(primeVec) & Mod(nextVal,primeVec[j]) != 0, j++);
If(j >= N Row(primeVec), outVec[i]=1,outVec[i]=0);
);
outVec;
);
Dadurch verkürzt sich die Zeit um mehr als die Hälfte auf unter 0,6 Sekunden.
Zwei allgemeine Hinweise zur Geschwindigkeitssteigerung: Wenn ein Matrixwert mehr als einmal verwendet werden muss, ist es schneller, den Wert einer Variablen zuzuweisen und diese anstelle der indexierten Matrix zu verwenden. Dies kann zwar den Code verlängern, spart aber Zeit. Versuchen Sie dies, indem Sie nextVal im obigen Code durch den indexierten Matrixwert ( inVals[i] ) ersetzen. Zweitens werden Ort und die Matrixverkettung mit zunehmender Größe der Matrix langsamer. Wenn Sie mit einer sortierten Matrix arbeiten können, führt Loc sortiert eine binäre Suche durch und ist deutlich schneller. Weitere Beispiele zur Matrixreferenzierung und -verkettung finden Sie in „Speed testing matrix operations.jsl“ .
Der Versuch, Primzahlen in der Spalte mit den großen Zahlen ( Groß ) zu finden, ist problematischer. Das Finden der ersten 10 dauert etwa 1,9 Sekunden. An diesem Punkt sind Sie auf einen speziellen Algorithmus angewiesen, um Verbesserungen zu erzielen. Miller-Rabin (MR) ist eine weit verbreitete und relativ einfach zu implementierende Technik zum Testen auf Primzahlen. Eine deterministische Version finden Sie in millerRabin1.jsl . MR beruht auf modularer Exponentiation und es muss darauf geachtet werden, Überlauffehler zu vermeiden. Allein benötigt MR 5,28 Sekunden, um alle 1000 Big- Zahlen zu verarbeiten. Es mag Sie überraschen, dass MR beim Verarbeiten der Klein -Zahlen langsamer ist als der erste isPrime-Algorithmus oben (2,34 Sekunden). Das liegt wahrscheinlich daran, dass der Rechenaufwand mit zunehmender Zahlengröße zunimmt, was eine Verbesserung nahelegt: Testen Sie bis zu einer Primzahl einer bestimmten Größe mithilfe von 2) oben. Wenn die Zahl eine Primzahl ist, beenden Sie. Andernfalls wechseln Sie zu MR. Dieser Ansatz befindet sich in millerRabin2.jsl . Um die optimale Anzahl der zu prüfenden Primzahlen zu ermitteln, wurden einige Anpassungen vorgenommen. Dadurch wurde die Zeit auf 2,33 Sekunden halbiert.
