Un stockage efficace de nombres premiers
Pour une bibliothèque, j'ai besoin de stocker les premiers nombres premiers les nombres jusqu'à une limite L. Cette collection doit avoir un O(1) temps de recherche (afin de vérifier si un nombre est premier ou pas) et il doit être facile, étant donné un nombre, trouver le prochain nombre premier (en supposant qu'il est plus petit que L).
Étant donné que L est fixe, un Eratostene tamis pour générer la liste est très bien. Maintenant, j'utilise un panier booléen tableau pour stocker la liste, qui ne contient que des entrées pour les nombres impairs entre 3 et L (inclus). Cela prend (L-2)/2 bits de mémoire. Je voudrais être en mesure d'augmenter de manière statique L sans utiliser plus de mémoire.
Est-il une structure de données en utilisant moins de mémoire avec des propriétés similaires? Ou au moins la constante recherche du temps? (nombres impairs peuvent ensuite être énumérés jusqu'à ce que nous obtenir une prime)
(la langue que j'ai écrit ceci en est Facteur de mais cette question serait la même dans n'importe quelle langue qui a intégré ou facilement programmable paniers bits tableaux)
- Ce qui est un cas typique de "L'? Est-ce pour un dispositif intégré où la mémoire est serré? Elle pourrait affecter les recommandations. Étant donné qu'il y a 50,847,534 nombres premiers en vertu d'un milliard de dollars, vous pourriez passer plus de temps à l'emballage/déballage puis d'un simple tableau de 4 octets entiers.
- L est aujourd'hui de 5 000 000.
- Et je ne voudrais pas besoin de plus que le ~320kB de mémoire, j'ai aujourd'hui.
- Si vous voulez stocker des informations dans l'ordre de 5 000 000 de nombres entiers dans de 320 000 octets...
- DanielDaranas: c'est ce qui est fait aujourd'hui. Étant donné que seul un nombre impair de primalité est stocké (et prend un bit d'information, vraie ou fausse), je stocker des informations à propos de 2 500 000 nombre impair dans moins de 313 000 octets. Pourquoi cela vous surprend-il?
- Je pense que c'est assez cool que nous pouvons compact tellement en si peu d'espace.
- Cela me surprend parce que la contrainte de mémoire est si exigeant qu'il exclut pratiquement n'importe quelle efforts pour optimiser l'ordre des algorithmes impliqués. Il n'est pas impossible de travailler avec cette limite de mémoire, étant donné les propriétés des nombres premiers; mais il est loin, loin d'être optimale.
Vous devez vous connecter pour publier un commentaire.
Vous pouvez explicitement vérifier plus de nombres premiers à supprimer les redondances.
Au moment où vous effectuez cette opération uniquement pour deux, par la vérification de divisibilité par deux explicitement et puis les stocker uniquement pour les nombres impairs, qu'ils sont de qualité.
Pour 2 et 3, vous obtenez des restes de 0 à 5, dont seulement 1 et 5 ne sont pas divisibles par deux ou trois et peut conduire à un nombre premier, alors vous êtes à 1/3.
Pour 2, 3, et 5, vous obtenez 8 nombre de 30, ce qui est agréable pour les stocker dans un octet.
Ceci est expliqué plus en détail ici.
Une alternative aux paniers des bitmaps et des roues mais tout aussi efficace dans certains contextes - est de stocker les différences entre les nombres premiers consécutifs. Si vous laissez de côté le nombre 2 comme d'habitude, puis toutes les différences sont encore. Le stockage de la différence/2 vous pouvez obtenir jusqu'à 2^40ish régions (juste avant 1999066711391) à l'aide d'octets de taille variables.
Les nombres premiers jusqu'à 2^32 nécessitent seulement 194 Mo, comparativement à 256 Mo pour un odds-seulement emballés bitmap. Itération sur delta-stockées sur les nombres premiers est beaucoup plus rapide que pour les roues de stockage, qui comprend le modulo-2 roues connu comme la cote-seulement bitmap.
Pour des plages de 1999066711391 à partir de, plus gros, plus la taille des cellules ou de longueur variable de stockage sont nécessaires. Ce dernier peut être extrêmement efficace, même si très simple, des dispositifs sont utilisés (par exemple, continuer à ajouter jusqu'à ce qu'un octet < 255 a été ajouté, comme dans LZ4style de compression), en raison de la très faible fréquence des écarts de plus de 510/2.
Pour des raisons d'efficacité, il est préférable de diviser la plage en sections (pages) et de les gérer de B-Tree style.
Entropie-codage des différences (Huffmann ou le codage arithmétique) des coupes de stockage permanent des exigences pour un peu moins de la moitié, ce qui est proche de l'optimum théorique et mieux que les listes ou les roues compressé à l'aide de la meilleure disponible packers.
Si les données sont stockées décompressée, alors qu'il est encore beaucoup plus compact que les fichiers binaires ou textuelles de nombres, par un ordre de grandeur ou plus. Avec un B-Arbre style index en place, il est facile de simplement sections de la carte dans la mémoire nécessaire et itérer sur eux à la vitesse de l'éclair.
Au moment où vous êtes le traitement 2 en tant que cas particulier et puis d'avoir un tableau où chaque nombre impair est associé à un élément du tableau (avec des nombres impairs étant le premier). Pourriez-vous améliorer cela en traitant 2 et 3 comme des cas particuliers en reconnaissant que le reste de l'nombres premiers de la forme 6n+1 ou 6n-1 (qui est pour tous les nombres premiers p où p > 3, p mod 6 = 1 ou 5). Celui-ci peut être généralisé à voir Wikipédia. Pour tous les nombres premiers p > 5, p mod 30 = 1, 7, 11, 13, 17, 19, 23 ou 29. Vous pourriez aller de l'avant avec cette et de réduire la mémoire nécessaire au détriment du temps de traitement (bien qu'il sera toujours en O(1), juste un ralentissement de O(1)).
Peut-être un trie structure de données qui ne contient que des nombres premiers est ce que vous cherchez. Au lieu d'utiliser des caractères d'index, vous pouvez utiliser les chiffres entiers. Une mise en œuvre de ce sont Judy-Tableaus.
Bien, ils ne répondent pas à vos O(1) exigence, ils sont extrêmement efficace de la mémoire pour les mêmes clés (comme la plupart des pièces de numéros) et assez rapide à regarder avec un O(m) (m=longueur de la clé) au maximum.
Si vous regardez pour un premier dans la pré-généré à l'arbre, vous pouvez parcourir l'arborescence jusqu'à ce que vous trouver ou vous êtes déjà au niveau du noeud qui est à côté de la précédant et suivant le premier.
Donné que la mémoire est si bas, je ne pense pas que vous pouvez faire beaucoup mieux à partir d'un point de vue de la vitesse de votre système actuel.
Si il y a une meilleure solution, puis je suppose qu'il faudrait profiter de la Théorème Des Nombres Premiers qui montre que L devient plus grand, à la limite de
π(L) /(L /ln(L)) les approches 1.
Peut-être une meilleure solution serait une adaptation de l'emballage de la solution dans une structure de données comme une sorte de ignorer la liste.
Comment sur une sorte de table de hachage?
Vous avez besoin d'une très bonne fonction de hachage (quelque chose comme
n mod p
, oùp
n'est pas un multiple de l'un quelconque desq
plus bas nombres premiers - choisirq
suffisamment élevé afin de réduire le nombre de collisions).Comment sur un Intervalle Arbre? http://www.geeksforgeeks.org/interval-tree/
Il peut ne pas être en O(1) mais elle est très rapide. Comme peut-être O(log(p(n))) où p(n) est le nombre de nombres premiers jusqu'à le nombre n de. De cette façon vous aurez la mémoire dont vous aurez besoin sera en proportion du nombre de nombres premiers seulement, considérablement la coupe de la mémoire des coûts.
Par exemple, supposons que vous trouverez un premier à-dire p1 et puis la prochaine à p2,
Insérer un intervalle (p1,p2) et ainsi de suite et lorsque vous effectuez une recherche pour n'importe quel nombre dans cette gamme, il sera de retour cet intervalle et vous pouvez retourner p2 qui serait la réponse dans votre cas.
Si vous pouvez savoir quels sont ceux qui sont Mersenne ou d'autres facilement représentés les nombres premiers, vous pourriez être en mesure d'enregistrer quelques morceaux à l'aide de cette représentation avec un drapeau pour les nombres.
Aussi, comment à propos de stocker les numéros de la différence de la précédente nombre? Alors que la taille ne devrait pas augmenter de façon assez rapide (mais recherche serait lente). La combinaison avec l'approche ci-dessus, vous pouvez stocker des nombres de Mersenne et de la différence de la dernière nombre de Mersenne premier.
Vérifier la topcoder tutoriel sur les nombres premiers:
http://community.topcoder.com/tc?module=Static&d1=tutoriels&d2=math_for_topcoders