2

Пишу функцию по числам Фибоначчи, способ Fast doubling с запоминанием предыдущих результатов, вот код:

def calculate_fib(n, context={}):
    if n < 3:
        return 1
    else:
        if not context.get(n // 2, 0):
            context[n // 2] = calculate_fib(n // 2, context)
        fn = context[n // 2]

        if not context.get(n // 2 + 1, 0):
            context[n // 2 + 1] = calculate_fib(n // 2 + 1, context)
        fn1 = context[n // 2 + 1]

    print(context)
    if n % 2:
        return fn**2 + fn1**2
    else:
        return fn * (2*fn1 - fn)

В словаре context сохраняются уже вычисленные значения. Если мы найдём значение 40-го числа, то напечатает:

>>> calculate_fib(40)
{2: 1, 1: 1}
{2: 1, 1: 1, 3: 2}
{2: 1, 1: 1, 3: 2, 5: 5}
{2: 1, 1: 1, 3: 2, 5: 5, 4: 3}
{2: 1, 1: 1, 3: 2, 5: 5, 4: 3, 6: 8}
{2: 1, 1: 1, 3: 2, 5: 5, 4: 3, 6: 8, 10: 55}
{2: 1, 1: 1, 3: 2, 5: 5, 4: 3, 6: 8, 10: 55, 11: 89}
{2: 1, 1: 1, 3: 2, 5: 5, 4: 3, 6: 8, 10: 55, 11: 89, 20: 6765}
{2: 1, 1: 1, 3: 2, 5: 5, 4: 3, 6: 8, 10: 55, 11: 89, 20: 6765, 21: 10946}
102334155

Всё правильно, как и ожидалось. Но затем найдём, допустим, 13-е число. Так же вызываем calculate_fib(13) без передачи context, но видим:

>>> calculate_fib(13)
{2: 1, 1: 1, 3: 2, 5: 5, 4: 3, 6: 8, 10: 55, 11: 89, 20: 6765, 21: 10946}
{2: 1, 1: 1, 3: 2, 5: 5, 4: 3, 6: 8, 10: 55, 11: 89, 20: 6765, 21: 10946, 7: 13}
233

То есть, локальная переменная context сохранилась, да ещё и при втором вызове инициилизировалась не как пустой словать, а как словарь из прошлого вызова функции. Почему так происходит?

tetelevm
  • 724
  • 2
    context={} вычисляется один раз в момент определения функции а не каждый раз при вызове. – extrn Apr 27 '19 at 00:04
  • то есть, у меня context является чем-то вроде атрибута функции и хранится в памяти постоянно, а не только при работе функции? – tetelevm Apr 27 '19 at 00:09
  • 2
    Верно. print(calculate_fib.__defaults__). Конечно лучше избегать такого изменения, по сути, глобальной переменной. – extrn Apr 27 '19 at 00:17
  • 3
    Марк Лутц - "Изучаем Python", глава 17 «Области видимости и вложенные функции» и раздел «Типичные ошибки при работе с функциями» в конце. – Sergey Gornostaev Apr 27 '19 at 06:38

0 Answers0