Stockage efficace des nombres premiers

Une alternative aux bitmaps et aux roues emballés - mais tout aussi efficace dans certains contextes-stocke les différences entre les nombres premiers consécutifs. Si vous omettez le numéro 2 comme d'habitude, toutes les différences sont égales. Stocker la différence / 2 Vous pouvez obtenir jusqu'à 2 ^ 40ish régions (juste avant 1999066711391) en utilisant des variables de taille octet.

Les nombres premiers jusqu'à 2^32 ne nécessitent que 194 MByte, par rapport à 256 MByte pour un bitmap emballé uniquement avec des cotes. Itérer sur des nombres premiers stockés en delta est beaucoup plus rapide que pour le stockage à roues, qui comprend la roue modulo-2 connu sous le nom odds-seulement bitmap.

Pour les plages à partir de 1999066711391, une taille de cellule plus grande 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 à ajouter jusqu'à ce qu'un octet LZ4), en raison de la fréquence extrêmement faible des intervalles de plus de 510/2.

Pour des raisons d'efficacité, il est préférable de diviser la plage en sections (pages) et les gérer B-Tree style.

Entropie-codage les différences (Huffmann ou codage arithmétique) réduisent les besoins de stockage permanent à un peu moins de la moitié, ce qui est proche de l'optimum théorique et mieux que les listes ou les roues compressées en utilisant les meilleurs emballeurs disponibles.

Si les données sont stockées non compressées, elles sont encore 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 en mémoire au besoin et de les parcourir à une vitesse fulgurante.

Pour le moment, vous traitez 2 comme un cas particulier et avez ensuite un tableau où chaque nombre impair est mappé à un élément du tableau (certains nombres impairs étant premiers). Vous pouvez améliorer cela 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 > 3, P mod 6 = 1 ou 5). Cela peut être encore généralisé-voir Wikipedia . Pour tous les nombres premiers p > 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 au détriment du temps de traitement (bien que ce soit toujours O (1), juste un O(1) plus lent).

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

Bien qu'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 des nombres) et assez rapides à rechercher avec un O(m) (M=longueur de clé) au maximum.

Si vous recherchez un premier dans le arbre pré-généré, vous pouvez marcher l'arbre jusqu'à ce que vous le trouviez ou vous êtes déjà au nœud qui est à côté du premier précédent et suivant.

Étant donné que la mémoire est si bon marché, Je ne pense pas que vous puissiez faire beaucoup mieux du point de vue de la vitesse que votre schéma existant.

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

Π(L) / (L / ln(L)) approches 1.

Peut-être qu'une meilleure solution aurait une solution d'emballage adaptative dans une structure de données un peu comme une liste de saut.

Que diriez-vous d'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 nombres premiers q les plus bas - choisissez q suffisamment élevé pour minimiser le nombre de collisions).

Que diriez-vous d'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. de cette façon, vous aurez la mémoire dont vous aurez besoin sera proportionnelle au nombre de nombres premiers seulement, réduisant considérablement le coût de la mémoire.

Par exemple supposons que vous trouviez un premier à P1, puis le suivant à p2, Insérer intervalle (P1, p2) et ainsi de suite et lorsque vous exécutez une recherche de n'importe quel nombre dans cette plage il retournera cet intervalle et vous pouvez retourner p2 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 pourriez être en mesure d'enregistrer quelques bits en utilisant cette représentation avec un indicateur pour les nombres applicables.

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

Consultez le tutoriel topcoder sur les nombres premiers: http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=math_for_topcoders