Stockage efficace des nombres premiers

StackOverflow https://stackoverflow.com/questions/1032427

Question

Pour une bibliothèque, j'ai besoin de stocker les premiers nombres premiers jusqu'à une limite L. Cette collection doit avoir un temps de recherche O (1) (pour vérifier si un nombre est premier ou non) et ce doit être simple, étant donné un nombre, pour trouver le prochain nombre premier (en supposant qu'il soit inférieur à L).

Etant donné que L est fixe, un tamis Eratostene pour générer la liste convient. À l’heure actuelle, j’utilise un tableau booléen compact pour stocker la liste, qui ne contient que des entrées pour les nombres impairs compris entre 3 et L (inclus). Cela prend (L-2) / 2 bits de mémoire. J'aimerais pouvoir augmenter L de manière statique sans utiliser plus de mémoire.

Existe-t-il une structure de données utilisant moins de mémoire avec des propriétés similaires? Ou avec au moins le temps de recherche constant? (les nombres impairs peuvent alors être énumérés jusqu'à ce que nous obtenions un nombre premier)

(la langue dans laquelle j'ai écrit ceci est Factor , mais cette question serait la même dans toutes les langues matrices de bits compactes intégrées ou facilement programmables)

Était-ce utile?

La solution

Vous pouvez vérifier explicitement davantage de nombres premiers pour supprimer la redondance.

Pour le moment, vous ne faites cela que pour deux, en vérifiant explicitement la divisibilité par deux, puis en ne mémorisant que les nombres impairs, qu'ils soient premiers ou non.

Pour 2 et 3, vous obtenez les reliquats de 0 à 5, dont seulement 1 et 5 ne sont pas divisibles par deux ou trois et peuvent conduire à un nombre premier, vous êtes donc au tiers.

Pour 2, 3 et 5, vous obtenez 8 numéros sur 30, ce qui est agréable à stocker dans un octet.

Ceci est expliqué plus en détail ici .

Autres conseils

Une alternative aux bitmaps et aux roues compactés - mais tout aussi efficace dans certains contextes - consiste à stocker les différences entre les nombres premiers consécutifs. Si vous oubliez le chiffre 2 comme d'habitude, toutes les différences sont égales. En enregistrant la différence / 2, vous pouvez obtenir jusqu'à 2 ^ 40 régions (juste avant 1999066711391) à l'aide de variables de la taille en octets.

Les nombres premiers jusqu’à 2 ^ 32 n’exigent que 194 Mo, contre 256 Mo pour un bitmap compact. Itérer sur les nombres premiers stockés en delta est beaucoup plus rapide que pour le stockage sur roues, qui inclut la roue modulo-2 appelée bitmap à odds-only.

Pour les plages à partir de 1999066711391, une plus grande taille de cellule ou un stockage de longueur variable sont nécessaires. Ce dernier peut être extrêmement efficace même si des schémas très simples sont utilisés (par exemple, continuez d’ajouter jusqu’à ce qu’un octet & Lt; 255 soit ajouté, comme dans LZ4 - en raison de la fréquence extrêmement faible des intervalles supérieurs à 510/2.

Par souci d'efficacité, il est préférable de diviser la plage en sections (pages) et de les gérer à la manière d'un arbre B.

Le codage entropique des différences (codage de Huffmann ou arithmétique) réduit les besoins de stockage permanent à un peu moins de la moitié, ce qui est proche de l’optimum théorique et supérieur aux listes ou disques compressés avec les meilleurs conditionneurs disponibles.

Si les données sont stockées non compressées, elles restent beaucoup plus compactes que les fichiers de nombres binaires ou textuels, d’un ordre de grandeur ou plus. Avec un index de style B-Tree en place, il est facile de simplement mapper des sections dans la mémoire si nécessaire et de les parcourir à une vitesse fulgurante.

Pour le moment, vous considérez 2 comme un cas spécial et créez ensuite un tableau dans lequel chaque nombre impair est associé à un élément du tableau (certains nombres impairs étant premiers). Vous pouvez améliorer ceci en traitant 2 et 3 comme des cas spéciaux reconnaissant que le reste des nombres premiers sont sous la forme 6n + 1 ou 6n-1 (c'est-à-dire pour tous les nombres premiers p où p & Gt; 3, p mod 6 = 1 ou 5). Cela peut être plus généralisé - voir Wikipedia . Pour tous les nombres premiers p & Gt; 5, p mod 30 = 1, 7, 11, 13, 17, 19, 23 ou 29. Vous pouvez continuer avec cela et réduire la mémoire nécessaire aux dépens du temps de traitement (bien que ce soit toujours O (1), juste un O (1)) plus lent.

Peut-être recherchez-vous une structure de données trie qui ne contient que les nombres premiers . Au lieu d'utiliser des caractères comme index, vous pouvez utiliser les chiffres entiers. Cette Judy-Array est une implémentation de ce logiciel.

Cependant, ils ne répondent pas à votre exigence O (1), ils sont extrêmement efficaces en mémoire pour des clés similaires (comme la plupart des parties de chiffres) et assez rapide pour rechercher avec un O (m) (m = clé- longueur) au maximum.

Si vous recherchez un nombre premier dans l'arborescence pré-générée, vous pouvez parcourir l'arbre jusqu'à ce que vous le trouviez ou que vous soyez déjà sur le nœud situé à côté du nombre premier et suivant.

Étant donné que la mémoire est si peu chère, je ne pense pas que vous puissiez faire mieux en termes de rapidité que votre système actuel.

S'il existe une meilleure solution, je suppose qu'elle tirerait parti du théorème des nombres premiers qui montre que lorsque L devient plus grand, la limite de

& # 960; (L) / (L / ln (L)) est proche de 1.

Peut-être une meilleure solution aurait-elle une solution d'emballage adaptative dans une structure de données semblable à une ignorer la liste .

Pourquoi pas une sorte de table de hachage?

Vous auriez besoin d'une très bonne fonction de hachage (quelque chose comme n mod p, où p n'est pas un multiple des q premiers nombres premiers - choisissez <=> suffisamment haut pour minimiser le nombre de collisions ).

Pourquoi pas un arbre d'intervalle? http://www.geeksforgeeks.org/interval-tree/

Ce n'est peut-être pas O (1) mais c'est vraiment rapide. Comme peut-être O (log (p (n))) où p (n) est le nombre de nombres premiers jusqu'au nombre n. Ainsi, la mémoire dont vous aurez besoin sera proportionnelle au nombre de nombres premiers, ce qui réduira considérablement le coût de la mémoire.

Par exemple, supposons que vous trouviez un nombre premier à dire p1 puis le suivant à p2, Insérer un intervalle (p1, p2), etc., et lorsque vous effectuez une recherche sur un nombre compris dans cette plage, cet intervalle sera renvoyé et vous pourrez renvoyer p2, ce qui serait la réponse dans votre cas.

Si vous pouvez déterminer lesquels sont Mersenne ou d'autres nombres premiers facilement représentés, vous pourrait peut-être économiser quelques bits en utilisant cette représentation avec un drapeau pour les nombres applicables.

Aussi, pourquoi ne pas stocker les nombres comme différence par rapport au nombre précédent? Ensuite, la taille ne devrait pas augmenter aussi rapidement (mais la recherche serait lente). En combinant l’approche ci-dessus, vous pouvez stocker les nombres premiers de Mersenne et la différence par rapport au dernier nombre de Mersenne précédent.

Licencié sous: CC-BY-SA avec attribution
Non affilié à StackOverflow
scroll top