Превышение размера списков в Python

Question

Я пытаюсь реализовать сито с эратосфенами в python, однако при попытке найти все простые числа вплоть до корня из sqare, например 779695003923747564589111193840021 Я получаю сообщение об ошибке Range () имеет слишком много элементов. Мой вопрос: как мне избежать этой проблемы, если я создаю экземпляр списка с помощью цикла while, я получу сообщение об ошибке, говорящее о том, что я использую слишком много памяти (до того, как он даже начнет использовать файл подкачки), они перечислены ниже:

Использование диапазона ()

maxnum = 39312312323123123

primes = []
seq = []
i = 0
seq = range(2,maxnum)

for i in seq:
    mul = i * seq
    for j in mul:
        try:
            seq.remove(j)
        except:
            pass
        primes.append(i)

print primes

Использование while:

maxnum = 39312312323123123

primes = []
seq = []
i = 0
while i < maxnum:
    seq.append(i)
    i+=1

for i in seq:
    mul = i * seq
    for j in mul:
        try:
            seq.remove(j)
        except:
            pass
        primes.append(i)

print primes

Answer 1

Я бы сказал, "используйте xrange() вместо", но вы фактически используете список целых чисел в качестве результата сита ..... Так что целочисленный генератор не является правильным решением.

Я думаю, что будет трудно материализовать список с 39312312323123123 элементами в нем, независимо от того, какую функцию вы используете для этого .... Это, в конце концов, 279 петабайт 64-битных целых.

Попробуйте это.

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

Answer 2

Это более сложный алгоритм, возможно, технически не считающийся ситом, но один из подходов состоит в том, чтобы не удалять все кратные с заданного простого числа одновременно, а ставить в очередь следующий кратный (вместе с простым). Это может быть использовано в реализации генератора. Очередь по-прежнему будет содержать много (кратных) простых чисел, но не столько, сколько путем построения и фильтрации списка.

Первые несколько шагов сделаны вручную, чтобы показать принцип ...

• 2 простое число - выход и очередь (4, 2)
• 3 простое число - выход и очередь (6, 3)
• 4 является составным - заменить (4, 2) на (6, 2) в очереди
• 5 простое число - выход и очередь (10, 5)
• 6 является составным - заменить (6, 2) на (8, 2) и (6, 3) на (9, 3)

Примечание - очередь не FIFO. Вы всегда будете извлекать кортежи с самым низким первым элементом, но новые / заменяющие кортежи не имеют (обычно) самого высокого первого элемента, и (как в случае с 6 выше) будут дубликаты.

Чтобы эффективно обрабатывать очередь в Python, я предлагаю словарь (т. Е. Хеш-таблицу) с ключом от первого элемента кортежа. Данные представляют собой набор значений второго элемента (исходные простые числа).

Как предложено в другом месте, протестируйте с маленькими целями, прежде чем пытаться на большую. И не удивляйся, если потерпишь неудачу. Возможно, вам еще понадобится слишком много больших целых чисел, выделенных кучей, за один раз (в очереди), чтобы завершить решение.

Answer 3

Ваш алгоритм не работает. Сначала включите его для maxnum = 100.

Как только вы запустите его, вы обнаружите, что maxnum = 100000000 займет много времени.

График времени, необходимого для запуска maxnum, в (10 100 100 000 100 000 100 000 100 000 ...). Вы можете экстраполировать, сколько времени займет 39312312323123123:

Answer 4

Существует сторонний модуль для Python, который называется gmpy

.

У него есть пара функций, которые могут быть вам полезны, поскольку они очень быстрые. Вероятностные штучки достигают отметки в 4 млрд.

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.

Answer 5

Попробуйте это:

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

Вы не должны исчерпывать память, пока не получите очень большое количество простых чисел. Таким образом, вам не нужно беспокоиться о создании списка кратных. Не уверен, что это все равно считается ситом.

На самом деле, это не будет работать для maxnum = 39312312323123123. Используя теорему простого числа , мы можем оценить, что в этом диапазоне будет приблизительно 1,028,840,332,567,181 простых чисел.

Как указано в этого вопроса , максимальный размер списка python в 32-битной системе равен 536,870,912. Поэтому, даже если у вас не хватает памяти, вы все равно не сможете завершить вычисления.

У вас не должно быть такой проблемы с 64-битной системой.

2 ** 64 => 18446744073709551616

При использовании математики из вышеупомянутого вопроса (2 ** 64) / 8 максимальное количество элементов в списке будет 2,305,843,009,213,693,951, что превышает предполагаемое число простых чисел, с которыми вы столкнетесь.

Edit:

Чтобы избежать проблем с памятью, вы можете сохранить список простых чисел в файле на жестком диске. Сохраняйте одно простое число в строке и читайте файл каждый раз, когда проверяете новый номер.

Может быть, что-то вроде этого:

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

В конце у вас на жестком диске будет файл, содержащий все ваши простые числа.

Хорошо, так что это будет довольно медленно, но вам не хватит памяти. Вы можете сделать это быстрее, увеличив скорость чтения / записи файлов (например, RAID ).

Answer 6

Об ограничении памяти, как насчет создания настраиваемого списка (класса), который внутренне является связанным списком списков или массивов. Волшебный переход от одного к другому внутри, и добавляйте больше по мере необходимости, так как вызывающий использует ваш пользовательский список с предоставленным вами внешним интерфейсом, который будет аналогичен тем членам, которые необходимы для удовлетворения потребностей .append .remove и т.д. массивы, используемые в вашей задаче.

Примечание : я не программист на Python. Не знаю, как реализовать то, что я сказал в Python. Возможно, я не знаю контекста здесь, поэтому я пойму, если за меня проголосуют.

Может быть, использовать " generators ", как они вызываются в python, для получения результатов ваших внутренних списков, как если бы это был один огромный список. Возможно с связанным списком .

Answer 7

range() возвращает список, содержащий все числа в запрошенном диапазоне, тогда как xrange является генератором и выдает числа один за другим с потреблением памяти, близким к нулю.