Nota: una voce di sfida da @David_Burnham è stato inviato prima della scadenza ma è stato messo in quarantena dal mio sistema di posta elettronica. L'ho scoperto solo dopo la pubblicazione del post originale sul blog. Sto aggiornando i risultati per riflettere le modifiche basate sulla nuova voce.
Grazie a tutti coloro che hanno inviato il codice per la Sfida 2. Il punteggio era una sfida, poiché alcuni codici funzionavano meglio per valori più piccoli e altri per valori più grandi. La tabella seguente fornisce i risultati per ciascuna parte della sfida. C'erano tre corse per èPrime , 1000 numeri dispari casuali di 5 cifre non divisibili per 5, numeri dispari di 8 e 9 cifre non divisibili per 5 e numeri dispari di 12-15 cifre non divisibili per 5. I risultati erano basati sulle due condizioni finali. I punti sono stati divisi tra le sfide, 1,5 punti per 1 st , 1 su 2 nd e 0,5 per 3 rd . Vengono forniti anche i tempi per gli invii più veloci (in secondi).
@leelaim Il tempo di isPrime(Small) è stato il più veloce di qualsiasi altro membro dello staff JMP (+3 punti). @atterrare su Lo script isPrime(Big) utilizza la funzione Parallel Assign per migliorare la velocità. Due delle voci hanno memorizzato nella cache i risultati per getPrimes utilizzando Spazio dei nomi . Questo approccio è utile quando è necessario accedere ai risultati più di una volta (tuttavia, i tempi di esecuzione si basano su risultati non memorizzati nella cache). Tutte e quattro queste voci sono state incluse di seguito.
Ecco la classifica dopo le due sfide:
La sfida 3 verrà pubblicata mercoledì 1 giugno.
La sfida 2 richiedeva di trovare i numeri primi in due modi possibili. Dato un valore intero positivo N , dovevi trovare: 1) N numeri primi o 2) tutti i numeri primi sotto N . Cominciamo con 2) poiché è un po' più semplice da implementare. Il metodo più semplice per trovare i numeri primi è la divisione delle prove. Partendo con 2 come candidato e un insieme vuoto di numeri primi, controlla se qualcosa nell'attuale insieme di numeri primi divide equamente il numero candidato. In caso contrario, aggiungilo all'insieme dei numeri primi e continua con il candidato successivo. Poiché non c'è nulla nel primo set con cui iniziare, viene aggiunto 2. Controllando 3, non divide nulla in {2} e viene aggiunto al set primo. Il numero 4, però, divide qualcosa in {2,3} e non viene sommato. Di seguito è mostrato un esempio di implementazione.
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;
);
Ci sono alcuni vantaggi in questo approccio: è facile da capire, il codice è conciso e può essere facilmente adattato per entrambe le sfide di ricerca primaria. Sfortunatamente, è estremamente lento. Trovare i numeri primi inferiori a 100.000 Mi ci sono voluti 19,43 secondi .
Un approccio leggermente più complesso consiste nell'utilizzare un setaccio. Invece di testare un numero nella primalità, i setacci testano i numeri fuori dalla primalità. Il più antico e conosciuto è il Setaccio di Eratostene . Inizia supponendo che tutto sia primo. Cominciando con 2 come primo numero primo, trova tutti i numeri che lo dividono equamente e rimuovili dal gruppo dei numeri primi. Continuare con il numero successivo ancora nel primo set. Di seguito è riportata una versione non ottimizzata.
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 );
);
Il vantaggio più evidente è la velocità. Il tempo che ho impiegato per trovare tutti i numeri primi inferiori a 100.000 è stato di 0,2811 secondi, circa 70 volte più veloce, e di 3,4025 secondi per 1.000.000. Il codice è ancora conciso e di facile comprensione. Uno svantaggio minore è che è necessario creare un vettore per tenere traccia dei numeri non primi (ovvero, non è possibile aumentare l'elenco tramite concatenazione, cosa che vedremo in seguito non è necessariamente un vantaggio). Ciò pone il problema della ricerca N i numeri primi sono più difficili perché non sai esattamente quanto grande sarà il vettore di cui avrai bisogno.
Di seguito sono riportate due versioni ottimizzate. Il primo inizia rimuovendo tutti i multipli di due, quindi ripete solo i numeri dispari da 3 in poi. Quadrato( N ) viene utilizzato per il limite superiore del ciclo esterno perché tutti i numeri non primi inferiori a quello saranno già stati eliminati. Ad esempio, per trovare tutti i numeri primi inferiori a 100, è sufficiente filtrare fino a 10. I numeri eliminati per qualsiasi numero primo maggiore di 10 saranno il prodotto di quel numero primo per un numero inferiore a 10, che sarà stato rimosso con qualche altro numero primo (ad esempio, 11*5 viene rimosso con il crivello per 5, 11*9 con il setaccio per 3, ecc.). Questi miglioramenti hanno ridotto il tempo di esecuzione di oltre la metà a 1.3545. Il secondo mostra il vantaggio di utilizzare le operazioni della matrice JSL per il ciclo interno, con tempi di 0,01625 per 1.000.000 e 2,6694 per 100.000.000, un miglioramento di quasi 100 volte!
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 );
);
Puoi fare di meglio? IL Setaccio di Atkin è teoricamente più efficiente ed è stato implementato in Esempio di Primes Atkins.JSL E Primes Atkins (ottimizzato).JSL . Il primo fornisce un'implementazione non ottimizzata e più semplice da comprendere (2,236 secondi per 1.000.000). Meglio della versione non ottimizzata di Eratostene. La versione ottimizzata, tuttavia, non poteva battere Eratostene ottimizzato (4,914 secondi per 100.000.000). Inoltre, è molto più lungo e complesso, dal punto di vista programmatico e teorico.
Che ne dici di leggere da una tabella di numeri? Sebbene questo non sia nello spirito della scrittura di un algoritmo, non ho detto che non potresti. @Craige_Hales ha fornito una soluzione utilizzando questo approccio. Data la specifica del problema di N per non superare 1e8, la dimensione dello script per contenere i valori compressi richiedeva oltre 4 milioni di caratteri di codice, 4,6 MB di spazio su disco e circa 5,5 secondi per caricarsi, indipendentemente dalla dimensione del N . Più lento delle altre soluzioni. Sebbene non sia né il più veloce né il più breve, ho incluso lo script di Craige per via del suo approccio unico al problema, dell'uso della compressione e della Assegnazione parallela .
Trovare N i numeri primi sono un problema più impegnativo. Supponendo che tu usi un setaccio, dovrai creare un vettore di valori fino a N l'esimo primo. Per fare ciò, è necessario stimare un limite superiore per tale valore. La sottostima dovrebbe essere evitata poiché potrebbe richiedere la riesecuzione di parte o dell'intero algoritmo per trovare valori non setacciati. Valore stimato dell'ennesimo prime.jmp mostra 6 stime diverse. Est1 fornisce un caso in cui i valori sono sottostimati per piccoli N . Molte stime si applicano solo a N maggiore di un valore specifico e in questi casi è necessario prestare attenzione nel fornire stime alternative. Est2 va bene per N ≥ 13 e Est3 migliora quello per valori più grandi. Sfortunatamente, i buoni limiti sono raramente semplici. Est4 è stato utilizzato in Primes fast submission.jsl . Anche se non fa un lavoro altrettanto buono e sottovaluta valori molto grandi di N , è semplice e facile da ricordare. Est5 è stato derivato utilizzando Non lineare con i valori effettivi. Est6 migliora Est5 perturbando leggermente i valori in modo che nessuno dei valori della tabella sia sottostimato. Non è garantito che non esistano sottostime tra 100 e 1e8. Le altre colonne della tabella riportano le sotto/sovrastimate per ciascuna tecnica.
La determinazione della primalità potrebbe seguire un percorso simile alla generazione dei numeri primi. Dato un numero X , potresti lasciare io = 2. Se Mod( N , io ) == 0 fermarsi, altrimenti incrementare io . Continua fino a Mod( N , io ) == 0 O io == N . Questo codice riportato di seguito trae vantaggio solo dal controllo dispari io dopo il test iniziale a io = 2 e fermarsi quando io > = Soffitto(Quadrato( 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;
);
Lo script qui sopra impiega circa 1,4 secondi per controllare tutti i 1.000 numeri a otto e nove cifre nella tabella Tabella dei grandi numeri.jmp ( Piccolo ).
Per migliorare ulteriormente questo aspetto, è possibile generare un vettore di numeri primi (fino a Soffitto(Quadrato( N )) ) e scorrerli.
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;
);
Ciò riduce il tempo di oltre la metà fino a meno di 0,6 secondi.
Due note generali per migliorare la velocità: Nelle situazioni in cui è necessario utilizzare un valore di matrice più di una volta, è più veloce assegnare il valore a una variabile, utilizzando la variabile anziché la matrice indicizzata. Sebbene ciò possa potenzialmente rendere il codice più lungo, farà risparmiare tempo. Prova questo sostituendo successivoVal nel codice sopra con il suo valore di matrice indicizzata ( inVals[i] ). Secondo, Loc e la concatenazione della matrice è lenta man mano che la dimensione della matrice cresce. Se riesci a lavorare con una matrice ordinata, Posizione ordinata esegue una ricerca binaria ed è molto più veloce.Vedere Matrice di test di velocità Operations.jsl per ulteriori esempi sul riferimento a matrici e sulla concatenazione.
Cercando di trovare i numeri primi nella colonna dei numeri grandi ( Grande ) è più problematico. Per trovare i primi 10 occorrono circa 1,9 secondi. A questo punto, devi fare affidamento su un algoritmo specializzato per i miglioramenti. Miller-Rabin (MR) è una tecnica comunemente usata e relativamente facile da implementare per testare la primalità. Viene fornita una versione deterministica millerRabin1.jsl . MR si basa sull'esponenziazione modulare ed è necessario prestare attenzione per evitare di incorrere in errori di overflow. Di per sé, la MR impiega 5,28 secondi per elaborare tutti e 1000 Grande numeri. Potrebbe sorprenderti che MR sia più lento del primo algoritmo isPrime sopra (2,34 secondi) nel lavorare attraverso il Piccolo numeri. Ciò è probabilmente dovuto al fatto che diventa più efficiente dal punto di vista computazionale man mano che i numeri aumentano di dimensione, suggerendo un miglioramento: testare fino a una certa dimensione primaria utilizzando il punto 2) sopra. Se il numero è primo, fermati. Altrimenti passa a MR. Questo approccio può essere trovato in millerRabin2.jsl . Sono state eseguite alcune regolazioni per trovare il numero ideale di numeri primi da controllare. Ciò ha ridotto il tempo a metà, a 2,33 secondi.
