Блог

Ладно, этот вопрос немного странный, но мне было интересно, могу ли я сделать это следующим образом.

Я работаю над простым генератором чисел Фибоначчи для развлечения, так как мне было интересно его программировать. Итак, я написал это:

 def f(n):
    if n == 1: return 1
    if n == 2: return 2
    else:
        return f(n-1)   f(n-2)
  

и это выполнялось очень медленно, на выполнение чего ушло 15 секунд f(30) на моем компьютере.
Итак, затем я написал это:

 def f(n):
    global a
    if n == 1: return 1
    if n == 2: return 1
    else:
        if "fib(%s)" % n in a:
            return a["fib(%s)" % n]
        else:
            z =  f(n-1)   f(n-2)
            a["fib(%s)" % n] = z
            return z
  

который в основном сохраняет предыдущие результаты в словаре следующим образом:

{'f(1)':1,'f(2)':2,'f(3)':3,'f(4)':5} и так далее. В функции это проверило бы, был ли этот результат в этом словаре, затем просто используйте это вместо того, чтобы переделывать все вычисления.

Это сделало его намного быстрее. Я мог бы сделать f(100) , и он мгновенно появится. Пройдя интервалы в 500, я добрался до f(4000) , и это все равно было мгновенно. Единственная проблема заключалась в том, что словарь становился глупо большим.

Итак, я добавил a = {} в конец функции, и это не сработало; он по-прежнему оставался a в виде массивного dict.

Итак, делая это:

 def f(n):
    global a
    if n == 1: return 1
    if n == 2: return 1
    else:
        if "fib(%s)" % n in a:
            return a["fib(%s)" % n]
        else:
            z =  f(n-1)   f(n-2)
            a["fib(%s)" % n] = z
            return z
    a = {}
  

не сработало. но если я сделаю это:

 def f(n):
    global a
    if n == 1: return 1
    if n == 2: return 1
    else:
        if "fib(%s)" % n in a:
            return a["fib(%s)" % n]
        else:
            z =  f(n-1)   f(n-2)
            a["fib(%s)" % n] = z
            return z
# now run the function
f(100)
a = {}
  

a возвращает значение к пустому словарю. Почему это происходит и как я могу это исправить?

Ваш a = {} оператор внутри функции никогда не выполнялся; каждый возможный путь выполнения достигает return до этого. Если бы это было выполнено, вам бы не понравились результаты — оно выполнялось бы при каждом отдельном рекурсивном вызове функции, а это означает, что ваш словарь никогда не содержал бы более одного элемента! Вам каким-то образом пришлось бы обнаруживать самый внешний вызов и очищать dict только там или (что намного проще) очищать его вне рекурсии, как в вашем втором примере.

Обратите внимание, что большая часть размера вашего словаря обусловлена странным решением использовать длинный строковый ключ. Ввод в него самого числа (как в a[n] = z ) сделал бы его намного более компактным.

(Для дальнейшего использования: метод, который вы здесь придумали, для сохранения результатов предыдущих вызовов функций, известен как «запоминание».)

Несмотря на ваш вопрос, то, что вы действительно хотите, это более быстрый способ вычисления последовательности Фибоначчи, верно? Проблема с вашим первоначальным подходом заключается в том, что повторение, несмотря на то, что оно очень элегантное и быстрое в написании кода, происходит довольно медленно. Последовательность Фибоначчи имеет решение близкой формы. Вы должны выполнить эту математику напрямую, чтобы ускорить свой код. В качестве соглашения рассмотрим последовательность Фибоначчи F (i) следующим образом: F(0) = 0, F(1) = 1, F(k) = F(k-1) F (k-2) k = 2, 3, … Решение для этой последовательности (я не буду демонстрировать это здесь, потому что для этого не место) F (k) = (1 / sqrt(5)) *(a ^ k — b ^ k), где a = (1 sqrt(5)) / 2 и b = (1 — sqrt(5)) / 2. Таким образом, ваш код может быть реализован следующим образом:

 def f(n):

    a = (1   5**.5)/2
    b = (1 - 5**.5)/2
    F = (a**n - b**n)/5**.5
    F = int(round(F)) #necessary to get an integer without the decimal part of the approximation. Afterall, you are working with irrational numbers.
    return F
  

Этот код очень хорошо масштабируется для больших значений n.