Превышен лимит памяти в питоне - PullRequest
Новая
       30

Превышен лимит памяти в питоне

0 голосов
/ 25 июня 2019

Я решаю задачу, для которой нужен либо список целых чисел, либо словарь размером 10 ^ 18. После запуска кода компилятор выдает сообщение об ошибке «Превышен лимит памяти».

Вот мой код: 

def fun(l,r,p):
    #f=[None,1,1]
    f={0:0,1:1,2:1}
    su=0
    for i in range(1,r):
        if i%2==0:
            f[i+2]=2*f[i+1]-f[i]+2
            #f.append(2*f[i+1]-f[i]+2)
        else:
            f[i+2]=3*f[i]
            #f.append(3*f[i])

    for k in range(l,r):
        su=su+f[k]

    su=(su+f[r])%p
    print(su)

t,p=input().split()
p=int(p)
t=int(t)
#t=3
#p=100000007
for i in range(t):
    l,r=input().split()
    l=int(l)
    r=int(r)
    fun(l,r,p)

Показывает превышение лимита памяти при максимальном использовании памяти 306612 КБ

1 Ответ

0 голосов
/ 25 июня 2019

Два наблюдения здесь:

  • Вам не нужно хранить все числа одновременно, вы можете использовать функцию deque и generator для генерации чисел, отслеживая только последние три сгенерированных цифры вместо всей последовательности. 

    import itertools
from collections import deque

def infinite_fun_generator():
    seed = [0, 1, 1]
    dq = deque(maxlen=2)
    dq.extend(seed)
    yield from seed
    for i in itertools.count(1):
        if i % 2 == 0:
            dq.append(2 * dq[-1] - dq[-2] + 2)
        else:
            dq.append(3 * dq[-2])
        yield dq[-1]

def fun(l, r, p):
    funs = itertools.islice(infinite_fun_generator(), l, r + 1)
    summed_funs = itertools.accumulate(funs, lambda a, b: (a + b) % p)
    return deque(summed_funs, maxlen=1)[-1]

  • Возможно, у вас больше шансов спросить об этом в Math.SE, так как я не хочу сейчас выполнять математику, но, как и в случае последовательности Фибоначчи, вероятно, есть аналитическое решение, которое вы можете использовать для вычисления n-го член последовательности аналитически без необходимости итеративного вычисления промежуточных чисел, и может даже оказаться возможным аналитически вывести формулу для вычисления сумм за постоянное время.

...