Nota: un challenge entry di @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 del blog. Sto aggiornando i risultati per riflettere i cambiamenti basati sul nuovo entry.
Grazie a tutti coloro che hanno inviato il codice per la sfida 2. Il punteggio è stato una sfida, poiché alcuni codici hanno funzionato meglio per valori più piccoli e altri per valori più grandi. La tabella seguente fornisce i risultati per ogni parte della sfida. Ci sono state tre prove per èPrimo , 1000 numeri dispari casuali a 5 cifre non divisibili per 5, numeri dispari a 8 e 9 cifre non divisibili per 5 e numeri dispari da 12 a 15 cifre non divisibili per 5. I risultati si basavano sulle due condizioni finali. I punti sono stati divisi tra le sfide, 1,5 punti per il 1 ° , 1 per il 2 ° e 0,5 per il 3 ° . Sono indicati anche i tempi per gli invii più rapidi (in secondi).
@leelaim isPrime(Small) il tempo è stato il più veloce di qualsiasi altro membro dello staff JMP (+3 punti). @landon isPrime(Big) lo script usa la funzione Parallel Assign per migliorare la velocità. Due delle voci hanno memorizzato nella cache i loro risultati per ottenerePrimi usando Spazio dei nomi . Questo approccio è utile quando è necessario accedere ai risultati più di una volta (i tempi di esecuzione sono basati su risultati non memorizzati nella cache, tuttavia). Tutte e quattro queste voci sono state incluse di seguito.
Ecco la classifica dopo due sfide:
La sfida 3 verrà pubblicata mercoledì 1 giugno.
La sfida 2 chiedeva 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ù facile da implementare. Il metodo più semplice per trovare i numeri primi è la divisione per tentativi. Iniziando con 2 come candidato e un insieme vuoto di numeri primi, controlla se qualcosa dall'insieme corrente di numeri primi divide il numero candidato in modo uniforme. In caso contrario, aggiungilo all'insieme di numeri primi e continua con il candidato successivo. Poiché non c'è nulla nell'insieme dei numeri primi per iniziare, viene aggiunto 2. Controllando 3, non divide nulla in {2} e viene aggiunto all'insieme dei numeri primi. Il numero 4, tuttavia, divide qualcosa in {2,3} e non viene aggiunto. 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;
);
Questo approccio presenta alcuni vantaggi: è facile da capire, il codice è conciso e può essere facilmente adattato per entrambe le sfide di ricerca dei numeri primi. Sfortunatamente, è estremamente lento. Trovare i numeri primi sotto 100.000 mi ha preso 19,43 secondi .
Un approccio leggermente più complesso è quello di usare un crivello. Invece di testare un numero in primalità, i crivelli testano i numeri fuori dalla primalità. Il più antico e noto è il Crivello di Eratostene . Inizia assumendo che tutto sia primo. Iniziando con 2 come primo numero primo, trova tutti i numeri che lo dividono in modo uniforme e rimuovili dall'insieme dei numeri primi. Continua con il numero successivo ancora nell'insieme dei numeri primi. 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ù ovvio è la velocità. Il mio tempo per trovare tutti i numeri primi inferiori a 100.000 è stato di 0,2811 sec, circa 70 volte più veloce, e di 3,4025 sec per 1.000.000. Il codice è ancora conciso e facile da capire. Uno svantaggio minore è che devi creare un vettore per tracciare i numeri non primi (ovvero, non puoi far crescere l'elenco tramite concatenazione, il che, come vedremo più avanti, non è necessariamente un vantaggio). Ciò rende il problema di trovare n numeri primi più difficile perché non sai esattamente quanto grande sarà il vettore di cui avrai bisogno.
Di seguito sono riportate due versioni ottimizzate. La prima inizia rimuovendo tutti i multipli di due, quindi esegue un ciclo solo sui numeri dispari da 3 in poi. Sqrt( n ) viene utilizzato per il limite superiore del ciclo esterno perché tutti i non primi inferiori a quello saranno già stati setacciati. Ad esempio, per trovare tutti i numeri primi inferiori a 100, è necessario solo setacciare fino a 10. I numeri setacciati 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 un altro numero primo (ad esempio, 11*5 viene rimosso con il setaccio per 5, 11*9 con il setaccio per 3, ecc.). Questi miglioramenti riducono il tempo di esecuzione di oltre la metà a 1,3545. Il secondo mostra il vantaggio di utilizzare le operazioni di 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 crivello di Atkin è teoricamente più efficiente ed è stato implementato in Esempio di Atkins Primes.JSL e Primes Atkins (ottimizzato).JSL . Il primo fornisce un'implementazione non ottimizzata e più facile da capire (2,236 sec per 1.000.000). Meglio della versione non ottimizzata di Eratostene. La versione ottimizzata, tuttavia, non è riuscita a battere Eratostene ottimizzato (4,914 sec per 100.000.000). Inoltre, è molto più lungo e complesso, sia a livello di programmazione che teorico.
Che ne dici di leggere da una tabella di numeri? Sebbene non sia nello spirito di scrivere un algoritmo, non ho detto che non si potrebbe. @Craige_Hales ha fornito una soluzione usando questo approccio. Data la specifica del problema di n che non deve superare 1e8, la dimensione dello script per contenere i valori compressi ha richiesto oltre 4 milioni di caratteri di codice, 4,6 MB di spazio su disco e circa 5,5 secondi per il caricamento, indipendentemente dalla dimensione di n . Più lento delle altre soluzioni. Sebbene non sia né il più veloce né il più breve, ho incluso lo script di Craige per il suo approccio unico al problema, l'uso della compressione e Assegnazione parallela .
Trovare n numeri primi è un problema più impegnativo. Supponendo di usare un crivello, dovrai creare un vettore di valori fino al primo n -esimo. Per fare questo, è necessario stimare un limite superiore per quel valore. La sottostima dovrebbe essere evitata poiché potrebbe richiedere di rieseguire parte o tutto l'algoritmo per trovare valori non setacciati. Stima del valore del primo n-esimo.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 maggiori di un valore specifico e in questi casi è necessario prestare attenzione a fornire stime alternative. Est2 è valido per n ≥ 13 ed Est3 lo migliora per valori maggiori. Sfortunatamente, i buoni limiti sono raramente semplici. Est4 è stato utilizzato in Primes invio veloce.jsl . Sebbene non faccia un buon lavoro e sottostimi per valori molto grandi di n , è semplice e facile da ricordare. Sono 5 è stato derivato utilizzando Nonlinear con i valori effettivi. Est6 migliora Sono 5 perturbando leggermente i valori in modo che nessuno dei valori nella tabella sia sottostimato. Non è garantito che non esistano sottostime tra 100 e 1e8. Le altre colonne della tabella indicano le sottostime/sovrastime per ogni tecnica.
La determinazione della primalità potrebbe seguire un percorso simile alla generazione di numeri primi. Dato un numero x , potresti lasciare i = 2. Se Mod( n , i ) == 0 fermati, altrimenti incrementa i . Continua finché Mod( n , i ) == 0 o i == n . Questo codice qui sotto trae vantaggio dal controllo solo dispari i dopo il test iniziale a i = 2 e dall'arresto quando 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;
);
Lo script sopra riportato impiega circa 1,4 secondi per controllare tutti i 1.000 numeri di otto e nove cifre nella tabella Tabella dei numeri grandi.jmp ( Piccolo ).
Per migliorare ulteriormente il tutto, è possibile generare un vettore di numeri primi (fino a Ceiling(Sqrt( 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;
);
In questo modo il tempo si riduce di oltre la metà, scendendo a meno di 0,6 secondi.
Due note generali per migliorare la velocità: in situazioni in cui un valore di matrice deve essere utilizzato più di una volta, è più veloce assegnare il valore a una variabile, utilizzando la variabile anziché la matrice indicizzata. Sebbene ciò possa potenzialmente allungare il codice, farà risparmiare tempo. Prova a sostituire prossimoVal nel codice sopra con il suo valore di matrice indicizzata ( inVals[i] ). In secondo luogo, Posto e la concatenazione di matrici rallentano man mano che le dimensioni della matrice aumentano. Se riesci a lavorare con una matrice ordinata, Posizione ordinata esegue una ricerca binaria ed è molto più veloce. Consulta Speed testing matrix operations.jsl per ulteriori esempi sul riferimento e la concatenazione di matrici.
Cercare di trovare numeri primi nella colonna dei numeri grandi ( Grande ) è più problematico. Per trovare i primi 10 ci vogliono circa 1,9 secondi. A questo punto, devi affidarti a un algoritmo specializzato per i miglioramenti. Miller Rabin (MR) è una tecnica comunemente usata e relativamente facile da implementare per testare la primalità. Una versione deterministica è fornita in millerRabin1.jsl . MR si basa sull'esponenziale modulare e bisogna fare attenzione a non incorrere in errori di overflow. Da solo, MR impiega 5,28 secondi per elaborare tutti i 1000 numeri Grande . Potresti sorprenderti che MR sia più lento del primo algoritmo isPrime sopra (2,34 secondi) nell'elaborare i numeri Piccolo . Ciò è probabilmente dovuto al fatto che diventa più efficiente dal punto di vista computazionale man mano che i numeri aumentano di dimensione, il che suggerisce un miglioramento: testare un numero primo di una certa dimensione usando 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 dimezzato il tempo, a 2,33 secondi.
