Hinweis: Ein Challenge-Eintrag von @David_Burnham wurde vor Ablauf der Frist eingereicht, wurde jedoch von meinem E-Mail-System unter Quarantäne gestellt. Ich habe es erst entdeckt, nachdem der ursprüngliche Blogbeitrag veröffentlicht wurde. Ich aktualisiere die Ergebnisse, um Änderungen basierend auf dem neuen Eintrag widerzuspiegeln.
Vielen Dank an alle, die Code für Challenge 2 eingereicht haben. Die Bewertung war eine Herausforderung, da einige Codes bei kleineren Werten besser funktionierten und andere bei größeren Werten. Die folgende Tabelle enthält die Ergebnisse für jeden Teil der Herausforderung. 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 zwischen den Herausforderungen aufgeteilt, 1,5 Punkte für 1 st , 1 für 2 nd und 0,5 für 3 rd . Es werden auch die Zeiten für die schnellsten Einreichungen angegeben (in Sekunden).
@leelaim Die isPrime(Small)-Zeit war so schnell wie jede andere von einem JMP-Mitarbeiter (+3 Punkte). @landon Das isPrime(Big)-Skript verwendet die Parallel Assign-Funktion, um die Geschwindigkeit zu verbessern. Zwei der Einträge haben ihre Ergebnisse zwischengespeichert getPrimes verwenden Namensraum . Dieser Ansatz ist hilfreich, wenn auf die Ergebnisse mehr als einmal zugegriffen werden muss (die Laufzeiten basieren jedoch auf nicht zwischengespeicherten Ergebnissen). Alle vier dieser Einträge sind unten aufgeführt.
Hier ist die Bestenliste nach zwei Herausforderungen:
Herausforderung 3 wird am Mittwoch, 1. Juni, veröffentlicht.
In Herausforderung 2 ging es darum, Primzahlen auf zwei mögliche Arten zu finden. Gegeben sei ein positiver ganzzahliger Wert N , du musstest finden: 1) N Primzahlen oder 2) alle Primzahlen darunter N . Beginnen wir mit 2), da es etwas einfacher zu implementieren ist. Die einfachste Methode zum Finden von Primzahlen ist die Probedivision. Beginnen Sie mit 2 als Kandidat und einer leeren Primzahlmenge und prüfen Sie, ob irgendetwas aus der aktuellen Primzahlmenge die Kandidatenzahl gleichmäßig teilt. Wenn nicht, fügen Sie es der Primzahlmenge hinzu und fahren Sie mit dem nächsten Kandidaten fort. Da die Primzahlmenge zu Beginn nichts enthält, wird 2 hinzugefügt. Bei Prüfung von 3 wird nichts in {2} geteilt und zur Primzahlmenge hinzugefügt. Die Zahl 4 teilt jedoch etwas durch {2,3} und wird nicht addiert. Eine Beispielimplementierung ist unten 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 zu verstehen, der Code ist prägnant und er kann leicht an beide Herausforderungen bei der Hauptfindung angepasst werden. Leider ist es extrem langsam. Finden der Primzahlen unter 100.000 Ich brauchte 19,43 Sekunden .
Ein etwas komplexerer Ansatz ist die Verwendung eines Siebes. Anstatt eine Zahl auf Primalität zu testen, werden Testzahlen aus der Primalität herausgesiebt. Das älteste und bekannteste ist das Sieb des Eratosthenes . Gehen Sie zunächst davon aus, dass alles prim ist. Beginnen Sie mit 2 als erster Primzahl, finden Sie alle Zahlen, die sie gleichmäßig teilen, und entfernen Sie sie aus der Primzahlmenge. Fahren Sie mit der nächsten Zahl fort, die sich noch im Primsatz befindet. Unten finden 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 zum Finden aller Primzahlen unter 100.000 betrug 0,2811 Sekunden, 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 besteht darin, dass Sie einen Vektor erstellen müssen, um Nicht-Primzahlen zu verfolgen (das heißt, Sie können die Liste nicht durch Verkettung erweitern – was, wie wir später sehen werden, nicht unbedingt ein Vorteil ist). Das macht das Finden schwierig N Die Berechnung von Primzahlen ist schwieriger, da Sie nicht genau wissen, wie groß der Vektor ist, den Sie benötigen.
Nachfolgend finden Sie zwei optimierte Versionen. Der erste beginnt mit dem Entfernen aller Vielfachen von zwei und durchläuft dann nur noch die ungeraden Zahlen ab 3. Quadrat( N ) wird für die Obergrenze der äußeren Schleife verwendet, da alle Nicht-Primzahlen kleiner als dieser Wert bereits herausgesiebt 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 mal einer Zahl kleiner als 10, die mit einer anderen Primzahl entfernt wurde (zum Beispiel wird 11*5 mit dem Sieb für 5 entfernt, 11*9 mit dem Sieb für 3 usw.). Diese Verbesserungen verkürzten die Laufzeit um mehr als die Hälfte auf 1.3545. Die zweite zeigt den Vorteil der Verwendung der JSL-Matrixoperationen für die innere Schleife mit Zeiten von 0,01625 für 1.000.000 und 2,6694 für 100.000.000, was einer nahezu 100-fachen Verbesserung entspricht!
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 );
);
Können Sie es besser machen? Der Sieb von Atkin ist theoretisch effizienter und wurde in implementiert Primzahlen Atkins example.JSL Und Primzahlen Atkins (optimiert).JSL . Die erste 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 den optimierten Eratosthenes nicht schlagen (4,914 Sek. für 100.000.000). Darüber hinaus ist es programmatisch und theoretisch viel länger und komplexer.
Wie wäre es mit dem Lesen aus einer Zahlentabelle? Obwohl dies nicht im Sinne des Schreibens eines Algorithmus ist, habe ich nicht gesagt, dass dies nicht möglich ist. @Craige_Hales hat mit diesem Ansatz eine Lösung bereitgestellt. Angesichts der Problemspezifikation von N Um 1e8 nicht zu überschreiten, benötigte die Größe des Skripts 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 N . Langsamer als die anderen Lösungen. Obwohl es weder das schnellste noch das kürzeste ist, habe ich Craiges Skript wegen seiner einzigartigen Herangehensweise an das Problem, der Verwendung von Komprimierung usw. aufgenommen Parallele Zuweisung .
Finden N Primzahlen sind ein anspruchsvolleres Problem. Angenommen, Sie verwenden ein Sieb, müssen Sie einen Wertevektor bis zum erstellen N Primzahl. Dazu muss eine Obergrenze für diesen Wert geschätzt werden. Eine Unterschätzung sollte vermieden werden, da es möglicherweise erforderlich ist, einen Teil oder den gesamten Algorithmus erneut auszuführen, um ungeprüfte Werte zu finden. Geschätzter Wert von nth prime.jmp zeigt 6 verschiedene Schätzungen. Est1 gibt einen Fall an, in dem Werte für kleine Werte unterschätzt werden N . Viele Schätzungen gelten nur für N größer als ein bestimmter Wert und es muss darauf geachtet werden, in diesen Fällen alternative Schätzungen bereitzustellen. Est2 ist gut für N ≥ 13 und Est3 verbessert dies für größere Werte. Leider sind gute Grenzen selten einfach. Est4 wurde verwendet Primes Fast Submission.jsl . Es leistet zwar keine so gute Arbeit und unterschätzt bei sehr großen Werten N , es ist einfach und leicht zu merken. Est5 wurde mithilfe von Nonlinear mit den tatsächlichen Werten abgeleitet. Est6 verbessert sich Est5 indem die Werte leicht verzerrt werden, sodass keiner der Werte in der Tabelle unterschätzt wird. Es kann nicht garantiert werden, dass es zwischen 100 und 1e8 keine Unterschätzungen gibt. Die anderen Tabellenspalten geben die Unter-/Überschätzungen für jede Technik an.
Die Bestimmung der Primalität könnte einem ähnlichen Weg folgen wie die Erzeugung von Primzahlen. Eine Zahl gegeben X , du könntest lassen ich = 2. Wenn Mod( N , ich ) == 0 stoppen, andernfalls erhöhen ich . Fahren Sie fort bis Mod( N , ich ) == 0 oder ich == N . Der folgende Code profitiert davon, dass er nur ungerade prüft ich nach dem ersten Test um ich = 2 und anhalten wann ich > = Decke(Quadrat( 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 zu überprüfen Tabelle der großen Zahlen.jmp ( Klein ).
Um dies noch weiter zu verbessern, können Sie einen Vektor von Primzahlen (bis zu) generieren Decke(Quadrat( N )) ) und durchlaufen Sie sie.
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 Verbesserung der Geschwindigkeit: In Situationen, in denen ein Matrixwert mehr als einmal verwendet werden muss, ist es schneller, den Wert einer Variablen zuzuweisen, indem man die Variable anstelle der indizierten Matrix verwendet. Dadurch kann der Code zwar möglicherweise länger werden, es wird aber auch Zeit gespart. Versuchen Sie dies durch Ersetzen nextVal im obigen Code mit seinem indizierten Matrixwert ( inVals[i] ). Zweite, Ort und die Matrixverkettung verlangsamt sich, wenn die Größe der Matrix zunimmt. Wenn Sie mit einer sortierten Matrix arbeiten können, Loc sortiert führt eine binäre Suche durch und ist viel schneller.Sehen Geschwindigkeitstestmatrix operationen.jsl Weitere Beispiele zur Matrixreferenzierung und -verkettung finden Sie hier.
Ich versuche, Primzahlen in der Spalte großer Zahlen zu finden ( Groß ) ist problematischer. Das Finden der ersten 10 dauert etwa 1,9 Sekunden. An diesem Punkt müssen Sie sich für Verbesserungen auf einen speziellen Algorithmus verlassen. Miller-Rabin (MR) ist eine häufig verwendete und relativ einfach zu implementierende Technik zum Testen der Primalität. Eine deterministische Version ist in angegeben millerRabin1.jsl . MR basiert auf der modularen Potenzierung und es muss darauf geachtet werden, dass es nicht zu Überlauffehlern kommt. Allein MR benötigt 5,28 Sekunden, um alle 1000 zu durchlaufen Groß Zahlen. Es mag Sie überraschen, dass MR beim Durcharbeiten langsamer ist als der erste isPrime-Algorithmus oben (2,34 Sekunden). Klein Zahlen. Dies liegt wahrscheinlich daran, dass es mit zunehmender Zahlengröße recheneffizienter wird, was auf eine Verbesserung hindeutet: Testen Sie mit 2) oben auf eine bestimmte Primzahlgröße. Wenn die Zahl eine Primzahl ist, hören Sie auf. Andernfalls wechseln Sie zu MR. Dieser Ansatz findet sich in millerRabin2.jsl . Es wurden einige Optimierungen durchgeführt, um die ideale Anzahl der zu überprüfenden Primzahlen zu finden. Dadurch halbierte sich die Zeit auf 2,33 Sekunden.
