J'essaie de faire un programme Java décent qui génère les nombres premiers de 1 à n (principalement pour les problèmes d'Euler du projet).
Pour le moment, mon algorithme est le suivant:
initialise Un éventail de booléens (ou un biparray si n est suffisamment grand), de sorte qu'ils sont tous fausses et un tableau d'INTS pour stocker les nombres premiers trouvés.
Définir un entier, S égal au plus bas, (c'est-à-dire 2)
tandis que s est <= sqrt (n)
définir tous les multiples de S (à partir de S ^ 2) sur true dans le tableau / bitarray.
Recherchez le prochain index le plus petit dans le tableau / bitarray qui est faux, utilisez-le comme la nouvelle valeur de s.
Entrée ultérieure.
passer par le tableau / bitarray, et pour chaque valeur fausse, placez l'index correspondant dans la matrice PRIMES.
Maintenant, j'ai essayé de sauter des nombres non de la forme 6K + 1 ou 6K + 5, mais cela ne me donne que A ~ 2x accélère, tandis que j'ai vu des programmes courir des ordres de magnitudes plus rapidement que le mien (bien que le code très convolué), tel que celui ici
Que puis-je faire pour améliorer?
EDIT: D'accord, voici mon code actuel (pour N of 1e7): s'exécute vers environ 350 ms sur ma machine 2.0GHz.
9 Réponses :
Je parie que la performance de Java est terrible lorsqu'il s'agit de bits ... Algorithmiquement, le lien que vous signalez doit être suffisant
Le problème est que je n'ai pas de cote ce qui se passe dans le lien.
Quoi spécifiquement ne comprenez-vous pas?
Le code source dans le lien Primes_Sieve.C à une distance de descente semble être presque illisible <. <.
La page HTML contient des informations utiles bien que
Hmm ... une idée de la manière dont on met efficacement implémenter le contenu qu'il indique sous la sous-position "Choisir une taille de tamis appropriée". Et la VM de Java met-elle des choses dans le cache de la CPU si elle décide, si le "tamisage séquentiel" utilise un tamis suffisamment petit pour s'adapter à la taille du cache?
Quelle est votre raison de penser que la performance de Java serait terrible lorsqu'il s'agit de bits?
Je pensais à l'origine que JVM n'était pas au courant des possibles instructions spéciales du processeur comme PopCount, mais maintenant, je pense que j'avais mal:
Vous pouvez faire l'étape de "Mettre l'index correspondant dans la matrice PRIMES" pendant que vous les détectez, en tirant une course à travers la matrice, mais c'est à peu près tout ce que je peux penser en ce moment.
Je ne suis pas sûr que cela soit possible dans le code que j'ai posté ci-dessus. Pouvez-vous élaborer un peu?
J'ai posté ceci avant votre code. Donc, je n'aurais pas connu. Je faisais juste votre description.
Avez-vous essayé Googling, par ex. Pour "Java Prime Numbers". J'ai fait et ai creusé cette simple amélioration:
http://www.anyexample.com/programming/java /java_prime_number_check_%28primality_test%29.xml
Sûrement, vous pouvez en trouver plus sur Google.
Il existe des méthodes plus efficaces de génération de nombres premiers que de l'application séquestionnelle d'une vérification de la primalité.
Bien sûr, mais le problème «Comment générer le problème du premier Nime» n'est pas vraiment nouveau et Google devrait être plus que suffisant pour trouver des améliorations de tous les types imaginables.
tandis que s est
Une erreur souvent dans de tels algorithmes n'est pas une racine carrée précalisable. int limit = sqrt(N);
while (s <= limit) {
SQRT (N) utilise probablement des logarithmes naturels pour calculer la valeur qui sera plus lente que de faire (S s
Nope, je précise la racine carrée de n
Ouais tu as fait, mais je pense que tu vas être légèrement plus rapide pendant (n * n <= l) au lieu de (n <= sqrt)
Essayé avec le code ci-dessus (pour n = 1e7); Il n'y avait pas de changement de vitesse notable
J'ai reçu un 3x ScopeUp (avec les hacks biteux). C'est génial: D
L'optimiseur ne s'occuperait-il pas de précisition de la racine carrée?
Utilisation du Bitset utilisera Moins de mémoire. L'algorithme de tamis est plutôt trivial, vous pouvez simplement "définir" les positions de bits sur le bitset , puis itérer pour déterminer les nombres premiers.
Il est effectivement plus lent avec Bitset. L'initialisation avec le nouveau bitset (L + 1) prend 2 fois aussi longtemps que le nouveau booléen [L + 1] et les boucles sont un peu plus lentes qu'avec Boolean [] aussi. Je pense que le ralentissement est causé par les frais généraux des appels de méthode définis (i), obtenez (i) et NextClearbit (i) au lieu d'accéder à des valeurs de la matrice.
Remarquez comment je n'ai pas mentionné la vitesse: p
Avez-vous également rendu le tableau plus petit en sautant des nombres non de la forme 6K + 1 et 6K + 5?
Je n'ai testé que d'ignorer des nombres de forme 2K et qui m'a donné ~ 4x Speed up (440 ms -> 120 ms):
Intéressant ... Pour moi, cela donne <2x accélère (350ms -> 190ms) mais c'est toujours bon, en particulier, on peut en particulier la question que cela peut être combiné avec d'autres optimisations. Merci! ^ _ ^
Voici de ma bibliothèque Euler Project ... c'est une légère variation du tamis des eratosthènes ... Je ne suis pas sûr, mais je pense que c'est appelé le tamis d'Euler.
1) Il utilise un bitset (SO 1 / 8ème la mémoire) 2) utilise uniquement le bitset pour des nombres impairs ... (un autre 1 / 2ème d'où 1 / 16ème) P>
Remarque: la boucle interne (pour les multiples) commence à "N * N" plutôt que "2 * n "et aussi des multiples d'incrément" 2 * n "ne sont traversés que ... d'où la vitesse supérieure. p> et voici la fonction pour vérifier si un numéro est Prime ... P> public boolean isPrime(int num)
{
if( num < maxLimit)
{
if( (num & 1) == 0)
return ( num == 2);
else
return primeList.get(num>>1);
}
return false;
}
J'ai récemment écrit une implémentation simple des tamis, pour le plaisir de celui-ci à l'aide de Bitset (tout le monde dit de ne pas, mais c'est le meilleur du chemin de l'étagère de stocker des données énormes efficaces). La performance semble être plutôt bonne pour moi, mais je travaille toujours à l'améliorer. avec des limites plus petites (disons 10 000 000 qui a pris 0,077479S), nous obtenons beaucoup plus rapidement que l'OP .
Voici mon code pour le tamis d'Erastothènes et c'est le plus efficace que je puisse faire:
Alors que Java n'est pas le choix le plus rapide ici, nous pourrions repérer des problèmes de performance si vous publiez votre code (complet mais compact).
Au fait, la mise en œuvre du tamis des eratosthènes n'est pas complexe du tout :)