J'essayais d'obtenir tous les nombres premiers avant 600851475143. J'utilisais un tamis d'eratosthènes pour cela. Cela nécessite que je crée une matrice booléenne de cette taille énorme. Mauvaise idée, vous pouvez manquer de mémoire. Toute autre manière. J'ai essayé d'utiliser une chaîne en utilisant chaque index avec des valeurs 0 et 1 pour représenter True ou False. Mais l'index de la méthode renvoie trop int.
Suivant J'utilise une matrice 2D pour mon problème. Toute autre meilleure façon de stocker un tableau aussi énorme?
5 Réponses :
Utilisez Bitset . Vous pouvez ensuite définir un bit n'importe quel élément d'index. 600851475143 est Vous pouvez infuser déplacer up to 2 ^ 39 ne prenant ainsi que 39 bits en interne (en réalité, il occupera 64 bits car il utilise Long).
2 ^ 63 qui est énorme à la plupart des objectifs
Il aurait besoin de 2 ^ 39 bits, pas 39.
L'OP nécessite des drapeaux de bits 600851475143 (ou la moitié de ceux-ci si elles sautent même des nombres, un troisième si vous ignorez également des multiples de 3, quelques-uns de moins si des multiples de petits nombres premiers sont ignorés). Ce serait toujours plus d'entrées que d'indexer dans un Bitset .
@assylias ouais ton droit
J'ai eu un problème similaire et j'ai utilisé un bit réglé (ensemble fondamentalement 1 ou 0 pour le décalage souhaité dans l'ordre) et je recommande en utilisant ewahcompressedbitmap compressera également votre jeu de bits
Comme Alan dit que le bitset occupera 70 Go de mémoire, mais vous pouvez faire une autre chose: avoir plusieurs bits de bits (consécutifs afin que vous puissiez calculer la position absolue) et chargez-vous en mémoire que vous avez besoin à ce moment-là quelque chose Comme une charge paresseuse, dans ce cas, vous aurez le contrôle de la mémoire utilisée.
L'exigence de mémoire pour 600851475143 booléens est au meilleur de 70 Go. Ce n'est pas réalisable. Vous devez soit utiliser la compression comme suggéré par Stephan ou trouver un algorithme différent pour calculer les nombres premiers.
C'est faisable, mais probablement pas réaliste!
Eh bien, j'aurais probablement dû clarifier que possible, ce n'est pas possible (alias pratiques) avec quelque chose de moins qu'un ordinateur sérieux (ou éventuellement superordinateur).
Je ne veux pas utiliser une bibliothèque, alors même si EwahCompressedbitmap est très prometteur, j'utiliserai des bits de taille de 32 Mo chacun. Et ajoutez un chargement paresseux à celui-ci. À la recherche d'une meilleure option. La manière traditionnelle de ce problème est trop lente, mais le travail.
Ce n'est pas vraiment pratique à retenir pour chaque numéro s'il s'agissait d'une quantité importante ou non pour une telle quantité (le tamis est une approche très lente pour les grands nombres en général).
de ce lien Vous avez une idée du nombre de nombres premiers à attendre plus petit que x . Pour votre fourchette de 600 milliards, vous pouvez vous attendre à environ 20 milliards de nombres premiers dans cette gamme. Les stocker aussi longtemps [] nécessiterait environ 160 Go de mémoire ... qui notamment plus que le 70 Go suggéré pour stocker un seul bit pour chaque numéro, la moitié si vous excluez même des chiffres (2 est le seul import).
pour un ordinateur de bureau 35 Go en mémoire peut être un peu important, mais un bon poste de travail peut avoir beaucoup de RAM. J'essaierais un tableau en deux dimensions avec un bit changeant / masquage.
Je m'attendrais toujours à ce que votre code de tamis puisse exécuter un beaucoup de temps (quelque chose de jours à des années). Je vous suggère d'enquêter sur des méthodes de détection de qualité supérieure plus avancées que le tamis.
Vous pouvez utiliser l'API interne Sun.Misc.unsafe d'Hotspot pour allouer un plus grand tableau. J'ai écrit un blogpost Comment simuler un tableau avec celui-ci cependant, ce n'est pas une API officielle Java, donc elle qualifie comme un hack.
"J'essayais d'obtenir tous les nombres premiers avant 600851475143." C'est totalement la mauvaise approche pour le problème d'Euler du projet.
Je suggérerais que si votre solution vous oblige à effectuer 600 milliards d'entrées de réseau, vous devez prendre une nouvelle approche.
@Ashok vectoriel est soutenu par un tableau, je ne vois pas comment cela fera une différence.
@Ashok Les vecteurs sont soutenus par des tableaux et sont synchronisés. Ne va pas aider.
+1: Les vecteurs ne peuvent pas être utilisés.
S'il s'agit de résoudre le problème d'Euler, il peut être plus facile de trouver simplement les facteurs d'abord, puis de déterminer les nombres premiers plutôt que inversement. Il vous suffit de trouver les facteurs entre 2 et SQRT (600851475143), ce qui rend cela beaucoup plus faisable