第 16 集 · B1 · 8 分钟
科技数码 · 第16集 · Динамическое программирование сверху и с
适合听读练习的俄语真实语料。片段原文开头：Давайте обсудим скорость вычисления чисел Фибоначчи. Посмотрим на программу, которую мы написали.
中俄字幕
Давайте обсудим скорость вычисления чисел Фибоначчи.
让我们讨论一下斐波那契数的计算速度。
Посмотрим на программу, которую мы написали.
我们来看一下之前编写的程序。
Вот она. Функция Фибоначчи, в которой отдельно крайний случай, отдельно рекуррентный
就是它：斐波那契函数，其中基础情况和递归情况分别处理。
случай. Всё понятно, кристально чисто.
一切都很清晰，一目了然。
Я запускаю вычисление с первого по сорок девятое число Фибоначчи и надеюсь сейчас
我将从第1个到第49个斐波那契数依次进行计算，并希望马上
увидеть их на экране.
在屏幕上显示出来。
Итак, посмотрим на результат.
那么，我们来看一下结果。
вот мы видим числа по сороковое, но почему- то он тормозит, очень медленно
我们已看到前40个数，但不知为何运行变慢了，计算速度非常慢，
вычисляются числа, осталось- то не так много.
其实剩下的数量并不多。
но я не могу дождаться, когда же это произойдет.
但我实在等不及它完成的那一刻了。
Может, когда Ханойские башни переложатся?
也许要等到汉诺伊塔被重新排列完成？
Что такое? Давайте попробуем замерить это время.
这是什么？我们来尝试测量一下这个时间。
На помощь нам придет библиотека time, в которой есть функция clock.
我们将借助 time 库，其中包含 clock 函数。
Я заранее заготовил блок кода.
我事先准备好了代码块。
я заменяю этот вызов функции на этот.
我将这个函数调用替换为这个。
вызов функции с замером времени, вот time1, time2, я
带时间测量的函数调用，这里是 time1、time2，我
первычисляю разность между ними в миллисекунды, и вот я ее.
将它们的差值换算成毫秒，这就是结果。
распечатаю на экран.
将其打印到屏幕上。
Давайте с вами посмотрим на то, какие времена там получатся.
让我们一起看看得到的时间结果。
Ну вот, видим миллисекунды, миллисекунды, уже полторы секунды,
看，这里显示的是毫秒、毫秒，已经是一点五秒了。
вот уже две секунды 290.
已经两秒了，290。
В общем, он реалистично, да, то есть он time нас не обманывает, да, часики
总之，它很真实，是的，也就是说，它没有欺骗我们的时间，是的，钟表。
показывают все правильно.
显示完全正确。
что то можно начать подозревать.
这时，人们可能会开始怀疑。
Вот, например, 1 плюс 2 равно 3.
例如，1加2等于3。
да ну два и два плюс три и семь это примерно видите да шесть
啊，2加2再加3等于7，大致如此，你看，是6。
3, 7 плюс 6 это как раз примерно 9, 7.
3.7加6刚好大约是9.7。
Времена как- то тоже ведут себя как числа Фибоначчи.
时间也似乎表现出斐波那契数列的特征。
В чем же дело?
问题究竟出在哪里？
Давайте с вами.
让我们一起来看看。
посмотрим, что происходит при рекуррентном вызове, например, функции Фибоначчи от
我们来看看递归调用时会发生什么，例如计算斐波那契函数在
пяти. Она, ничто жесумнявшаяся, вызывает функцию Фибоначчи от четырех, а затем,
5。它毫不犹豫地先调用斐波那契函数在4，然后
соответственно, функцию Фибоначчи от трех.
再调用斐波那契函数在3。
Но это произойдет не скоро, а только в тот момент, когда вот это вернет результат.
但这不会很快发生，而要等到此处返回结果之后。
Но я просто для себя отметил, что там она будет, да.
我只是自己记一下，它会在那里，是的。
Это вызывает соответственно функцию Фибоначчи от трех, а потом вызовет функцию
这又会相应地调用斐波那契函数在3，然后调用
Фибоначчи от двух.
斐波那契函数在2。
Это вызовет функцию Фибоначчи от двух и функцию Фибоначчи от одного.
这将调用斐波那契函数在2和斐波那契函数在1。
Функция Фибоначчи от 2 вызовет функцию Фибоначчи от 1 и функцию
斐波那契函数在2会调用斐波那契函数在1和
Фибоначчи от 0.
斐波那契函数在0。
Ну, слава богу, у меня это крайние случаи, то есть они вычисляются быстро, возвращая
嗯，谢天谢地，我的情况属于边界情形，也就是说它们能快速计算并返回结果。
результат. Это возвращает единичку, это возвращает нолик.
这会返回1，这会返回0。
После этого вот эта функция соображает результат 1 плюс 0 равно 1 и возвращает
之后，这个函数计算出结果：1加0等于1，并将其返回。
его функции Фибоначчи от 3.
返回给斐波那契函数（参数为3）的结果。
но самое страшное то, что вот эта функция фибоначчи от 3, она знает результат.
但最糟糕的是，这个斐波那契（参数为3）函数虽然知道结果，
но она не знает вот этого результата.
却不知道这个结果。
Он забыт, он нигде не закэширован.
它被遗忘了， nowhere 被缓存。
Поэтому мне приходится снова вызвать и получить этот результат оттуда, что функция
所以我不得不再次调用函数，从那里重新获取该结果，
Фибоначчи от 1 равна 1.
即斐波那契（参数为1）等于1。
Функция Фибоначчи от 3 соображает и возвращает, что она равна 2.
斐波那契（参数为3）函数计算后返回结果：它等于2。
Функция Фибоначчи от 4 получила двойку, но она забыла, она и не знала на самом деле,
斐波那契函数对输入4的计算结果是2，但它却忘记了——实际上它根本不知道，
что уже функция Фибоначчи от 2 была вычислена.
斐波那契函数对输入2的值此前已被计算过。
Поэтому она ее вызывает, прошу прощения, сразу возврата не произойдет, потому что
因此它会再次调用该函数；抱歉，此处不会立即返回，因为
фибо от 2 он вызовет фибо от 1 и фибо от 0.
fib(2) 将进一步调用 fib(1) 和 fib(0)。
которые, конечно, вычисляются просто, но
这两者当然可直接快速计算，但
тем не менее вот этот результат о том, что она равна единичке, будет получен не
即便如此，得出结果为1这一结论仍不会很快完成。
очень скоро. В результате fib от 4- х таки соображает, что результат равен 3, return
最终，fib(4) 终于意识到结果应为3，并返回3。
3. А дальше функция fibonacci от 5- ти, ничтоже сумняшися, вызывает fib от 3- х.
接着，fibonacci(5) 毫不迟疑地调用 fib(3)。
Зачем она это делает, негодная, но, увы, она вызывает в свою очередь fib от 2- х.
它为何要这么做？真是岂有此理！然而遗憾的是，它又进一步调用了 fib(2)。
она fib от 1 и fib от 0.
它还调用了 fib(1) 和 fib(0)。
Так, но она получит, естественно, результаты.
是的，但她自然会得到结果。
1, 0 вернет 1, а тут еще надо вызвать fib от 1, которая, ну слава богу, быстро
1 和 0 返回 1，而这里还需要调用 fib(1)，谢天谢地，它能快速返回。
вернет, она крайний случай.
它是边界情况，会快速返回 1。
быстро вернет 1, и только тогда, когда вот эта функция досчитается, мы елки палки,
会快速返回 1；只有当这个函数计算完毕后，天啊，
наконец- таки узнаем, что функция Фибоначчи от 5 равна.
我们才终于知道斐波那契函数在 5 处的值是多少。
пяти. Представляете себе, да?
是 5。您能想象吗？
Надо сказать, что то, что вы сейчас видите, вот это дерево вызовов,
需要说明的是，您现在看到的这个调用树，
это дерево Фибоначчи.
就是斐波那契树。
в нем левое и правое поддеревья имеют высоту, различающуюся на 1, и каждое поддерево
它的左子树和右子树高度相差为 1，且每个子树
тоже является деревом Фибоначчи.
本身也是一棵斐波那契树。
вот ну что можно здесь сказать ничего хорошего для того чтобы посчитать число
这里没什么好说的，根本无法准确计算出这个数
фибоначчи от 5 мне пришлось совершить 15 вызовов функций
为了计算斐波那契数列第5项，我需要调用函数15次
а глубина погружения, то есть количество адресов, максимальное количество адресов
而递归深度，即栈中存储的返回地址数量
возврата, хранившееся на стэке вызовов, и локальных переменных, ведь параметры же
存放在调用栈中的返回地址和局部变量的数量，因为参数也
тоже там хранятся, параметр n, да?
存放在那里，也就是参数n，对吧？
Их сколько? Раз, два, три, четыре, пять, то есть оно равно, собственно, этому n.
有多少个？一、二、三、四、五，所以它实际上就等于这个n。
То есть по памяти это тоже неэкономно.
因此，该方法在内存使用上也不经济。
Приехали. Что может нам помочь?
到此为止。那么，什么能帮到我们呢？
Поможет нам, конечно,
当然，能帮到我们的就是
наш заголовок" Динамическое программирование".
我们的标题——“动态规划”。
Основная идея динамического программирования состоит в том, чтобы решить каждую
动态规划的核心思想是每个子问题只求解一次，从而减少计算量。
подзадачу только один раз, сократив тем самым количество вычислений.
子问题仅求解一次，从而减少计算量。
И наибольшую пользу оно приносит именно тогда, когда экспоненциальное количество
当存在指数级数量的重复子问题时，动态规划的效果最为显著。
повторяющихся задач.
重复子问题。
Итак, давайте с вами попробуем кэшировать.
那么，让我们尝试进行缓存。
попробуем кэшировать те числа, которые уже вычислили.
尝试缓存那些已经计算过的数值。
Я создам вот здесь вот вне функции кэш.
我将在函数外部创建一个缓存。
Это будет у меня массив из. . .
它将是一个数组……
мне на самом деле будет достаточно 50 чисел, в крайнем случае хорошо 100.
实际上，我最多只需要50个数，极端情况下100个也足够了。
Числа Фибоначчи растут очень быстро, поэтому я. . .
斐波那契数增长得非常快，因此我……
знаю, что они просто не поместятся в стандартную переменную int.
我知道它们根本无法放入标准的 int 变量中。
Оверфлоу наступит слишком рано.
溢出会过早发生。
Ну и я инициализирую этот массив нулями.
那么，我将用零初始化这个数组。
Фактически эти переменные, эта переменная, да, этот массив, он у меня хранится в
实际上，这些变量——是的，这个数组——存储在我的
сегменте данных, является статическим.
数据段中，并且是静态的。
Он живет между вызовами функций независимо от них.
它独立于函数调用而存在，在函数调用之间一直存在。
Я подчеркну это словом static.
我将用 static 这个词来强调这一点。
вот хотя в данном случае это и так не обязательно.
尽管在此情况下其实并非必须。
что я буду делать?
我该怎么做？
ну, крайний случай крайним случаем, пускай он себе всегда реагирует однозначно, а
嗯，极端情况就按极端情况处理，让它始终做出明确响应，
вот иначе. я буду в первую очередь смотреть, не закэшировано ли уже это число n.
情况不同。我首先会检查数字n是否已经缓存。
То есть, если у меня кэш от n.
也就是说，如果我有n的缓存。
не равен нулю не равен нулю то просто нужно вернуть этот самый кэш от н
如果不为零，就直接返回这个n的缓存值。
И всё. А вот иначе, мне нужно будет развернуть некоторую деятельность, давайте её
就这样。否则，我就需要展开一些操作，我们来展开它。
развернём. Мне нужно не сразу возвращать этот результат, а закэшировать его.
我需要的不是立即返回该结果，而是先将其缓存。
cache от n равно соответственно вот этому вот ну и вернуть этот самый return cache
n的缓存值等于该值，然后返回cache[n]。
от n. я могу вот здесь вот заметить один важный момент, что, во- первых, вот этот
我在这里可以注意到一个关键点：首先，这个else是多余的。
else ненужен.
这个else是多余的。
来源：Тимофей Хирьянов · CC BY 3.0