Remarque : une entrée de défi de @David_Burnham a été soumis avant la date limite mais a été mis en quarantaine par mon système de messagerie. Je ne l'ai découvert qu'après la publication du billet de blog original. Je mets à jour les résultats pour refléter les changements basés sur la nouvelle entrée.
Merci à tous ceux qui ont soumis du code pour le défi 2. La notation était un défi, car certains codes fonctionnaient mieux pour des valeurs plus petites et d'autres pour des valeurs plus grandes. Le tableau ci-dessous donne les résultats pour chaque partie du défi. Il y a eu trois courses pour estPrime , 1000 nombres impairs aléatoires à 5 chiffres non divisibles par 5, nombres impairs à 8 et 9 chiffres non divisibles par 5 et nombres impairs de 12 à 15 chiffres non divisibles par 5. Les résultats étaient basés sur les deux dernières conditions. Les points ont été répartis entre les défis, 1,5 point pour 1 St , 1 pour 2 sd , et 0,5 pour 3 rd . Les temps des soumissions les plus rapides sont également indiqués (en secondes).
@leelaim Le temps isPrime(Small) a été aussi rapide que n'importe quel autre par un membre du personnel de JMP (+3 pts.). @se poser sur Le script isPrime(Big) utilise la fonction Parallel Assign pour améliorer la vitesse. Deux des entrées ont mis en cache leurs résultats pour obtenirPrimes en utilisant Espace de noms . Cette approche est utile lorsque les résultats doivent être consultés plusieurs fois (les temps d'exécution sont toutefois basés sur des résultats non mis en cache). Ces quatre entrées ont été incluses ci-dessous.
Voici le classement après deux défis :
Le défi 3 sera mis en ligne le mercredi 1er juin.
Le défi 2 demandait de trouver des nombres premiers de deux manières possibles. Étant donné une valeur entière positive n , il fallait trouver : 1) n nombres premiers ou 2) tous les nombres premiers sous n . Commençons par 2) car il est un peu plus facile à mettre en œuvre. La méthode la plus simple pour trouver des nombres premiers est la division par essais. En commençant par 2 comme candidat et un ensemble vide de nombres premiers, vérifiez si quelque chose dans l'ensemble actuel de nombres premiers divise le nombre candidat de manière égale. Sinon, ajoutez-le à l'ensemble des nombres premiers et passez au candidat suivant. Puisqu’il n’y a rien pour commencer dans l’ensemble premier, 2 est ajouté. En vérifiant 3, il ne divise rien dans {2} et est ajouté à l'ensemble premier. Le nombre 4, cependant, divise quelque chose en {2,3} et n'est pas ajouté. Un exemple de mise en œuvre est présenté ci-dessous.
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;
);
Cette approche présente quelques avantages : elle est facile à comprendre, le code est concis et il peut être facilement adapté aux deux principaux défis de recherche. Malheureusement, c'est extrêmement lent. Trouver les nombres premiers inférieurs à 100 000 m'a pris 19,43 secondes .
Une approche légèrement plus complexe consiste à utiliser un tamis. Plutôt que de tester un nombre en primalité, il filtre les nombres en dehors de la primalité. Le plus ancien et le plus connu est le Tamis d'Ératosthène . Commencez par supposer que tout est premier. En commençant par 2 comme premier nombre premier, trouvez tous les nombres qui le divisent uniformément et supprimez-les de l'ensemble premier. Continuez avec le numéro suivant toujours dans l'ensemble premier. Vous trouverez ci-dessous une version non optimisée.
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 );
);
L’avantage le plus évident est la rapidité. Mon temps pour trouver tous les nombres premiers inférieurs à 100 000 était de 0,2811 s, environ 70 fois plus rapide et de 3,4025 s pour 1 000 000. Le code est toujours concis et facile à comprendre. Un inconvénient mineur est que vous devez créer un vecteur pour suivre les nombres non premiers (c'est-à-dire que vous ne pouvez pas agrandir la liste par concaténation - ce que nous verrons plus tard n'est pas nécessairement un avantage). Cela pose le problème de trouver n les primes sont plus difficiles car vous ne savez pas exactement de quelle taille vous aurez besoin.
Vous trouverez ci-dessous deux versions optimisées. Le premier commence par supprimer tous les multiples de deux, puis boucle uniquement sur les nombres impairs à partir de 3. Sqrt( n ) est utilisé pour la limite supérieure de la boucle externe car tous les nombres non premiers inférieurs à cela auront déjà été filtrés. Par exemple, pour trouver tous les nombres premiers inférieurs à 100, il vous suffit de passer au tamis 10. Les nombres filtrés pour tout nombre premier supérieur à 10 seront le produit de ce nombre premier par un nombre inférieur à 10, qui aura été supprimé avec un autre nombre premier (par exemple, 11*5 est supprimé avec le tamis pour 5, 11*9 avec le tamis pour 3, etc.). Ces améliorations ont réduit le temps d'exécution de plus de moitié, à 1,3545. La seconde montre l'avantage d'utiliser les opérations matricielles de JSL pour la boucle interne, avec des temps de 0,01625 pour 1 000 000 et de 2,6694 pour 100 000 000, soit une amélioration de près de 100 fois !
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 );
);
Pouvez-vous faire mieux ? Le Tamis d'Atkin est théoriquement plus efficace et a été mis en œuvre dans Exemple Primes Atkins.JSL et Primes Atkins (optimisé).JSL . La première donne une implémentation non optimisée et plus facile à comprendre (2,236 sec pour 1 000 000). Mieux que la version non optimisée d'Eratosthène. La version optimisée, cependant, ne pouvait pas battre Eratosthène optimisé (4,914 secondes pour 100 000 000). De plus, il est beaucoup plus long et complexe, du point de vue programmatique et théorique.
Qu’en est-il de la lecture d’une table de nombres ? Bien que ce ne soit pas dans l’esprit de l’écriture d’un algorithme, je n’ai pas dit que vous ne pouviez pas le faire. @Craige_Hales fourni une solution en utilisant cette approche. Compte tenu de la spécification du problème de n ne doit pas dépasser 1e8, la taille du script destiné à contenir les valeurs compressées prenait plus de 4 millions de caractères de code, 4,6 Mo d'espace disque et environ 5,5 secondes à charger, quelle que soit la taille de n . Plus lent que les autres solutions. Bien qu'il ne soit ni le plus rapide ni le plus court, j'ai inclus le script de Craige en raison de son approche unique du problème, de son utilisation de la compression et de son utilisation. Attribution parallèle .
Découverte n les nombres premiers sont un problème plus difficile. En supposant que vous utilisez un tamis, vous devrez créer un vecteur de valeurs jusqu'au n le premier. Pour ce faire, une limite supérieure pour cette valeur doit être estimée. La sous-estimation doit être évitée car elle peut nécessiter de réexécuter une partie ou la totalité de l’algorithme pour trouver des valeurs non tamisées. Valeur estimée du nième prime.jmp montre 6 estimations différentes. Est1 donne un cas où les valeurs sont sous-estimées pour les petits n . De nombreuses estimations ne s'appliquent qu'à n supérieure à une valeur spécifique et il faut veiller à fournir des estimations alternatives dans ces cas. Est2 Est bon pour n ≥ 13 et Est3 améliore cela pour des valeurs plus grandes. Malheureusement, les bonnes limites sont rarement simples. Est4 a été utilisé dans Primes soumission rapide.jsl . Bien qu'il ne fasse pas un aussi bon travail et qu'il sous-estime les très grandes valeurs de n , c'est simple et facile à retenir. Est5 a été dérivé en utilisant Non linéaire avec les valeurs réelles. Est6 s'améliore Est5 en perturbant légèrement les valeurs afin qu'aucune des valeurs du tableau ne soit sous-estimée. Il n'est pas garanti qu'il n'y ait pas de sous-estimation entre 100 et 1e8. Les autres colonnes du tableau donnent les sous/surestimations pour chaque technique.
La détermination de la primalité pourrait suivre un chemin similaire à la génération de nombres premiers. Étant donné un numéro X , tu pourrais laisser je = 2. Si Mod( n , je ) == 0 arrêter, sinon incrémenter je . Continuez jusqu'à Mod( n , je ) == 0 ou je == n . Ce code ci-dessous bénéficie uniquement de la vérification des impairs je après le test initial à je = 2 et s'arrêtant quand je > = Plafond(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;
);
Le script ci-dessus prend environ 1,4 seconde pour vérifier les 1 000 nombres à huit et neuf chiffres du tableau. Tableau des grands nombres.jmp ( Petit ).
Pour améliorer encore cela, vous pouvez générer un vecteur de nombres premiers (jusqu'à Plafond(Sqrt( n )) ) et parcourez-les.
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;
);
Cela réduit le temps de plus de moitié, à moins de 0,6 seconde.
Deux notes générales pour améliorer la vitesse : Dans les situations où une valeur matricielle doit être utilisée plus d’une fois, il est plus rapide d’attribuer la valeur à une variable, en utilisant la variable au lieu de la matrice indexée. Même si cela peut potentiellement allonger le code, cela permettra de gagner du temps. Essayez ceci en remplaçant suivantVal dans le code ci-dessus avec sa valeur matricielle indexée ( inVals[i] ). Deuxième, Lieu et la concaténation de la matrice ralentit à mesure que la taille de la matrice augmente. Si vous pouvez travailler avec une matrice triée, Local trié effectue une recherche binaire et est beaucoup plus rapide.Voir Matrice de test de vitesse opérations.jsl pour des exemples supplémentaires sur le référencement matriciel et la concaténation.
Essayer de trouver des nombres premiers dans la colonne des grands nombres ( Grand ) est plus problématique. Trouver les 10 premiers prend environ 1,9 seconde. À ce stade, vous devez vous appuyer sur un algorithme spécialisé pour les améliorations. Miller-Rabin (MR) est une technique couramment utilisée et relativement facile à mettre en œuvre pour tester la primalité. Une version déterministe est donnée dans millerRabin1.jsl . MR s'appuie sur l'exponentiation modulaire et il faut veiller à éviter les erreurs de débordement. À lui seul, MR prend 5,28 secondes pour parcourir les 1 000 Grand Nombres. Cela peut vous surprendre que MR soit plus lent que le premier algorithme isPrime ci-dessus (2,34 secondes) pour parcourir le Petit Nombres. Cela est probablement dû au fait que le calcul devient plus efficace à mesure que la taille des nombres augmente, ce qui suggère une amélioration : testez jusqu'à une certaine taille première en utilisant 2) ci-dessus. Si le nombre est premier, arrêtez. Sinon, passez à MR. Cette approche se retrouve dans millerRabin2.jsl . Des réglages ont été effectués pour trouver le nombre idéal de nombres premiers à vérifier. Cela a réduit le temps de moitié, à 2,33 secondes.
