Dont la taille dépasse des listes en python
https://stackoverflow.com/questions/2337700
-
22-09-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianQuestion
Je suis en train de mettre en œuvre le d'Eratosthène en python, mais en essayant de trouver tous les nombres premiers jusqu'à la racine sqare de par exemple
La solution Il est un algorithme plus complexe, peut-être techniquement sans compter que le tamis, mais une approche consiste à éliminer tous les multiples d'une prime à la fois donné, mais la file d'attente multiple suivant (en même temps que le premier). Cela pourrait être utilisé dans une mise en oeuvre du générateur. La file d'attente encore jusqu'à la fin contenant beaucoup de nombres premiers, mais pas autant (multiples de) que par la construction puis à filtrer une liste. premiers pas fait manuellement, pour montrer le principe ... Remarque - la file d'attente n'est pas une FIFO. Vous serez toujours extraire les tuples avec le premier élément le plus bas, mais de nouvelles / tuples de remplacement ne (en général) sont les plus premier élément et (comme 6 ci-dessus) il y aura des doublons. Pour gérer efficacement la file d'attente en Python, je vous propose un dictionnaire (c.-à-Hashtable) calée par le premier élément du tuple. Les données sont un ensemble de valeurs du deuxième élément (les nombres premiers d'origine). Comme suggéré ailleurs, le test avec de petites cibles avant d'essayer pour le grand. Et ne soyez pas trop surpris si vous ne parvenez pas. Il peut encore être que vous avez besoin trop de grands entiers attribués-tas à un moment donné (dans la file d'attente) pour compléter la solution.
Autres conseils
Je dirais, « utilisation xrange() à la place », mais que vous utilisez en fait la liste des ints que le résultat de tamis ..... donc un générateur entier n'est pas une solution correcte.
Je pense qu'il sera difficile de matérialiser une liste avec 39312312323123123 éléments, peu importe quelle fonction que vous utilisez pour le faire .... qui est, après tout, 279 pétaoctets d'entiers 64 bits.
Essayez ceci.
class FoundComposite(Exception): pass
primes = [2]
seq = itertools.takewhile( # Take integers from a list
lambda x: x<MAXNUM, # until we reach MAXNUM
itertools.count(2) # the list of integers starting from 2
)
#seq = xrange(2, MAXNUM) # alternatively
for i in seq:
try:
for divisor in primes:
if not (i % divisor):
# no remainder - thus an even divisor
# continue to next i in seq
raise FoundComposite
# if this is reached, we have tried all divisors.
primes.append(i)
except FoundComposite:
pass
Votre algorithme est cassé. Faites-le travailler pour maxnum = 100 première.
Une fois que vous le faire fonctionner, vous trouverez maxnum = 100000000 volonté prend beaucoup de temps à courir.
Tracer le temps qu'il faut courir pour maxnum dans (10,100,1000,10000,100000,1000000 ...) vous pouvez être en mesure d'extrapoler combien de temps 39312312323123123 prendra:)
Il y a un module tiers pour python appelé gmpy
Il a deux fonctions qui peuvent vous être utiles car ils sont très rapides. Les choses probabiliste entre en jeu autour de la marque de 4 milliards.
next_prime(...)
next_prime(x): returns the smallest prime number > x. Note that
GMP may use a probabilistic definition of 'prime', and also that
if x<0 GMP considers x 'prime' iff -x is prime; gmpy reflects these
GMP design choices. x must be an mpz, or else gets coerced to one.
is_prime(...)
is_prime(x,n=25): returns 2 if x is _certainly_ prime, 1 if x is
_probably_ prime (probability > 1 - 1/2**n), 0 if x is composite.
If x<0, GMP considers x 'prime' iff -x is prime; gmpy reflects this
GMP design choice. x must be an mpz, or else gets coerced to one.
range() retourne une liste contenant tous les numéros dans la gamme requise, tandis que xrange est un générateur et on obtient les numéros un après l'autre avec une consommation de mémoire proche de zéro.
A propos de la limite de mémoire, que diriez-vous de créer une liste personnalisée (classe) qui est en interne une liste chaînée des listes ou des tableaux. Magiquement traverser de l'un à l'autre à l'intérieur, et ajouter plus au besoin, que l'appelant utilise votre liste personnalisée avec l'interface externe que vous avez fourni qui sera similaire aux membres nécessaires pour faciliter la .remove de .append, etc besoins des tableaux utilisés dans votre problème.
Remarque : Je ne suis pas un programmeur Python. Pas la moindre idée comment mettre en œuvre ce que je disais en Python. Peut-être que je ne connais pas le contexte ici, donc je comprendrai si je suis voté vers le bas.
Peut-être utiliser « » comme on les appelle dans python pour obtenir des résultats de vos listes internes comme si elle était une énorme liste unique. Peut-être avec liste chaînée .
Essayez ceci:
def getPrimes(maxnum):
primes = []
for i in xrange(2, maxnum):
is_mul = False
for j in primes: # Try dividing by all previous primes
if i % j == 0:
is_mul = True # Once we find a prime that i is divisible by
break # short circuit so we don't have to try all of them
if not is_mul: # if we try every prime we've seen so far and `i`
primes.append(i) # isn't a multiple, so it must be prime
return primes
Vous ne devriez pas manquer de mémoire jusqu'à ce que vous arrivez à un très grand nombre de nombres premiers. De cette façon, vous n'avez pas à vous soucier de la création d'une liste des multiples. Je ne sais pas si cela compte comme le tamis bien.
En fait, cela ne fonctionnera pas pour maxnum = 39312312323123123. En utilisant les théorème des nombres premiers on peut estimer qu'il y aura environ 1,028,840,332,567,181 nombres premiers dans cette gamme.
Comme indiqué dans cette question la taille maximale d'un liste python sur un système 32 bits est 536,870,912. Donc, même si vous ne courez pas de mémoire, vous serez toujours pas en mesure de terminer le calcul.
Vous ne devriez pas avoir ce problème avec un système 64 bits bien.
2 ** 64 => 18446744073709551616
En utilisant le calcul de la (2 ** 64) / 8 question ci-dessus, le nombre maximum d'éléments dans une liste serait 2,305,843,009,213,693,951 qui est supérieur au nombre estimé de nombres premiers que vous rencontrerez.
Modifier
Pour éviter les problèmes de mémoire, vous pouvez stocker votre liste de nombres premiers dans un fichier sur le disque dur. Stockez une prime par ligne et lire le fichier à chaque fois que vous vérifiez un nouveau numéro.
Peut-être quelque chose comme ceci:
primes_path = r'C:\temp\primes.txt'
def genPrimes():
for line in open(primes_path, 'r'):
yield int(line.strip())
def addPrime(prime):
primes_file = open(primes_path, 'a')
primes_file.write('%s\n' % prime)
primes_file.close()
def findPrimes(maxnum):
for i in xrange(2, maxnum):
is_mul = False
for prime in genPrimes(): # generate the primes from a file on disk
if i % prime == 0:
is_mul = True
break
if not is_mul:
addPrime(i) # append the new prime to the end of your primes file
vous le feriez à la fin, un fichier sur votre disque dur contenant tous vos nombres premiers.
Ok, donc ce serait assez lent, mais vous ne manquerez pas de mémoire. Vous pouvez le rendre plus rapide en augmentant la vitesse à laquelle vous pouvez lire / écrire des fichiers (comme
