§10.6. Подсказки

Если вы забавлялись с рекурсивной функцией поиска чисел Фибоначчи из раздела 5.72, то, наверное, заметили, что чем большие аргументы вы передаете, тем дольше функция выполняется. Более того, время расчетов увеличивается очень быстро. На одной нашей машине, f ibonacci (2 0) завершается мгновенно, fibonacci (30) думает около секунды и f ibonacci (40) будет работать почти бесконечно.

Чтобы понять почему так происходит, рассмотрим диаграмму вызовов для функции

fibonacci() сn = 4:

[TODO: нарисовать в изображение http://www.ibiblio.org/obp/thinkCSpy/illustrations/fibonacci.png]

Диаграмма вызовов функций отображает совокупность прямоугольных блоков, обозначающих функции, с линиями, соединяющими каждый блок с блоками функций которые он вызывает. Вверху диаграммы, fibonacci () с n = 4 вызывает fibonacci () с n = Зип = 2. В свою очередь, f ibonacci () с n = 3 вызывает f ibonacci () с n = 2 и n = 1. Итак далее.

Таким образом, каждая ветка дерева, по сути, отображает изменение стека вызовов, т.е. Поток выполнения в процессе расчетов, должен пройти по каждой ветке этого дерева. Подсчитайте сколько раз были вызваны fibonacci (0) и fibonacci (1). Не самое эффективное решение задачи, с точки зрения производительности (хотя оно, бесспорно, красивое).

Хорошее решение - сохранять значения, которые были недавно вычислены, запоминая их в словаре. Предыдущее вычисленное значение, которое запоминается для последующего использования, называют подсказкой. Ниже приведена реализация fibonacci (), использующая подсказки:

previous = {0:1, 1:1}
def fibonacci(n):
if previous.has key(n):
return previous[n]
else:
newValue = fibonacci(n-	-1)	+	fibonacci	(n-2)
previous[n] = newValue
return newValue

Словарь названный previous хранит числа Фибоначчи, которые мы уже знаем. Мы начинаем только с двух пар: 0 соответствует 1 и 1 соответствует 1.

Всякий раз, когда вызывается функция fibonacci (), она проверяет словарь, чтобы определить содержит ли он результат. Если это так, функция может немедленно возвратить результат, без выполнения дополнительных рекурсивных вызовов. Если нет, он должна рассчитать новое значение. Новое значение добавляется в словарь, перед тем как функция вернёт результат.

Используя эту реализацию, наша машина может вычислить функцию fibonacci() при п = 40 почти мгновенно. Но когда мы пытаемся вычислить fibonacci (50), мы сталкиваемся с другой проблемой:

90

Ревизия: 170

Словари

>» fibonacci (50)

OverflowError: integer addition

Ответ, как вы увидите через минуту 20365011074. Проблема в том, что это число слишком большое чтобы поместиться в тип int. Такую ситуацию называют переполнением. К счастью эта проблема имеет простое решение.