Обработка использования памяти для больших расчетов в python

Question

Я пытаюсь сделать некоторые вычисления с python, где у меня закончилась память. Поэтому я хочу прочитать / записать файл, чтобы освободить память. Мне нужно что-то вроде очень большого объекта списка, поэтому я подумал написать строку для каждого объекта в файле и читать / записывать эти строки вместо памяти. Порядок строк важен для меня, так как я буду использовать номера строк в качестве индекса. Поэтому мне было интересно, как я могу заменить строки в Python, не перемещаясь вокруг других строк (На самом деле, хорошо перемещать строки, если они возвращаются туда, где я их ожидаю).

Редактировать

Я пытаюсь помочь другу, который хуже или равен мне в питоне. Этот код должен найти наибольшее простое число, которое делит данное не простое число. Этот код работает для чисел, пока числа не станут похожими на 1 миллион, но после смерти моя память исчерпывается при попытке составить список чисел.

# a comes from a user input
primes_upper_limit = (a+1) / 2
counter = 3L
numbers = list()
while counter <= primes_upper_limit:
    numbers.append(counter)
    counter += 2L

counter=3
i=0
half = (primes_upper_limit + 1) / 2 - 1
root = primes_upper_limit ** 0.5
while counter < root:
    if numbers[i]:
        j = int((counter*counter - 3) / 2)
        numbers[j] = 0
        while j < half:
            numbers[j] = 0
            j += counter
    i += 1
    counter = 2*i + 3
primes = [2] + [num for num in numbers if num]
for numb in reversed(primes):
    if a % numb == 0:
        print numb
        break

Другое Править

Как насчет записи разных файлов для каждого индекса? например, миллиард файлов с длинными целочисленными именами файлов и просто числом внутри файла?

Answer 1

Вы хотите найти самый большой простой делитель a.( Project Euler Question 3 ) Ваш текущий выбор алгоритма и реализации делает это следующим образом:

1. Создание списка numbers всех простых чисел-кандидатов в диапазоне (3 <= n <= sqrt (a) или (a + 1) / 2, как вы в настоящее время) </li>
2. Просейте список numbers, чтобы получить список простых чисел {p} <= sqrt (a) </li>
3. Пробное деление: проверить делимость а на каждое р.Сохраните все простые делители {q} из a.
4. Выведите все делители {q};нам нужен только самый большой.

Мои комментарии по этому алгоритму приведены ниже.Разделение и пробное разделение - это не масштабируемые алгоритмы, как мы с Оуэном.Для больших (миллиардов или триллионов) вы действительно должны использовать NumPy.В любом случае, некоторые комментарии по реализации этого алгоритма:

1. Знаете ли вы, что вам нужно проверять только до √a , int(math.sqrt(a)), а не (+ 1) / 2, как выделать?
2. Нет необходимости составлять огромный список кандидатов numbers, а затем просеивать его для простоты - список чисел не масштабируется.Просто создайте список primes напрямую .Вы можете использовать while / for-loop и xrange(3,sqrt(a)+2,2) (что дает вам итератор).Как вы упоминаете, переполнение xrange () в 2**31L, но в сочетании с наблюдением sqrt, вы все равно можете успешно увеличить до 2**62
3. В общем, это хуже, чем получение простого разложения a, т.е.раз вы найдете простой делитель р |а, вам нужно только перейти к , чтобы просеять оставшийся коэффициент a / p или a / p² или a / p³ или любой другой) .За исключением редкого случая очень больших простых чисел (или псевдослучайных чисел), это значительно уменьшит величину чисел, с которыми вы работаете.
4. Кроме того, вам только когда-либо потребуется создать список простых чисел {p} один раз ;после этого храните его и выполняйте поиск, а не восстанавливайте его.Поэтому я бы выделил generate_primes(a) из find_largest_prime_divisor(a).Разложение очень помогает.

Вот мое переписывание вашего кода, но производительность все еще падает в миллиардах (a> 10 ** 11 +1) из-за сохранения просеянного списка.Мы можем использовать collection.deque вместо list для простых чисел, чтобы ускорить операцию O (1) append (), но это небольшая оптимизация.

# Prime Factorization by trial division

from math import ceil,sqrt
from collections import deque

# Global list of primes (strictly we should use a class variable not a global)
#primes = deque()
primes = []

def is_prime(n):
    """Test whether n is divisible by any prime known so far"""
    global primes
    for p in primes:
         if n%p == 0:
             return False #  n was divisible by p
    return True # either n is prime, or divisible by some p larger than our list    
def generate_primes(a):
    """Generate sieved list of primes (up to sqrt(a)) as we go"""
    global primes
    primes_upper_limit = int(sqrt(a))
    # We get huge speedup by using xrange() instead of range(), so we have to seed the list with 2
    primes.append(2)
    print "Generating sieved list of primes up to", primes_upper_limit, "...",
    # Consider prime candidates 2,3,5,7... in increasing increments of 2
    #for number in [2] + range(3,primes_upper_limit+2,2):
    for number in xrange(3,primes_upper_limit+2,2):
        if is_prime(number): # use global 'primes'
            #print "Found new prime", number
            primes.append(number) # Found a new prime larger than our list
    print "done"    
def find_largest_prime_factor(x, debug=False):
    """Find all prime factors of x, and return the largest."""
    global primes
    # First we need the list of all primes <= sqrt(x)    
    generate_primes(x)
    to_factor = x # running value of the remaining quantity we need to factor
    largest_prime_factor = None
    for p in primes:
        if debug: print "Testing divisibility by", p
        if to_factor%p != 0:
            continue
        if debug: print "...yes it is"
        largest_prime_factor = p
        # Divide out all factors of p in x (may have multiplicity)
        while to_factor%p == 0:
            to_factor /= p
        # Stop when all factors have been found
        if to_factor==1:
            break
    else:
        print "Tested all primes up to sqrt(a), remaining factor must be a single prime > sqrt(a) :", to_factor
    print "\nLargest prime factor of x is", largest_prime_factor
    return largest_prime_factor

Answer 2

Для числа, состоящего только из двенадцати цифр, как в Project Euler # 3, не требуется никакого сложного метода факторизации целых чисел, и нет необходимости хранить промежуточные результаты на диске.Используйте этот алгоритм, чтобы найти коэффициенты n:

1. Установите f = 2.
2. Если n = 1, остановитесь.
3. Если f * f> n,выведите n и остановитесь.
4. Разделите n на f, сохранив как частное q, так и остаток r.
5. Если r = 0, выведите q, разделите n на q и перейдите к шагу 2.
6. В противном случае увеличьте f на 1 и перейдите к шагу 3.

Это просто пробное деление на каждое целое число, пока оно не достигнет квадратного корня, что означает, что оставшийся кофакторпремьер.Каждый фактор печатается так, как он найден.

Answer 3

pytables отлично подходит для работы и хранения огромных объемов данных.Но сначала начните с реализации комментариев в ответе smci, чтобы минимизировать количество цифр, которое вам нужно хранить.

Answer 4

Если я вас правильно понимаю, это не простая задача.Как я понял, вы хотите оставить дескриптор файла открытым и использовать файл как место для хранения символьных данных.

Скажем, у вас есть файл типа

a
b
c

иВы хотели заменить «b» на «bb».Это будет боль, потому что файл на самом деле выглядит как a\nb\nc - вы не можете просто перезаписать b, вам нужен еще один байт.

Мой совет - попытаться найти способчтобы ваш алгоритм работал без использования файла для дополнительного хранилища.Если у вас переполнение стека, скорее всего, у вас не хватило памяти, вы переполнили стек вызовов, который на намного меньше.

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

edit

Ах, я понимаю, что вы имеете в виду ... когда список

while counter <= primes_upper_limit:
    numbers.append(counter)
    counter += 2L

становится действительно большим, вам может не хватить памяти.Итак, я думаю, вы в основном делаете сито, и поэтому у вас большой список numbers?Это имеет смысл.Если вы хотите продолжать делать это таким образом, вы можете попробовать массив numpy bool, потому что он будет использовать существенно меньше памяти на ячейку:

import numpy as np

numbers = np.repeat(True, a/2)

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

Что-то вроде:

factors = [ ]
tail = a

while tail > 1:
    j = 2
    while 1:
        if tail % j == 0:
            factors.append(j)
            tail = tail / j
            print('%s %s' % (factors, tail))
            break
        else:
            j += 1

т.е.Если бы факторинг 20: tail начинался как 20, то вы обнаружили, что 2 tail становится 10, затем он становится 5.

Это не очень эффективно и будетстановиться слишком длинным для большого (миллиардов) простых чисел, но это нормально для чисел с небольшими коэффициентами.

Я имею в виду, что ваше сито тоже хорошо, пока у вас не закончится память;).Вы можете дать numpy выстрел.