Как сочинять алгоритмы

Тема сегодняшнего занятия могла бы занимать год на серьёзном программистском факультете (но на ВМиК не занимает, размазывается тонким слоем по нескольким отдельным репликам в нескольких отдельных курсах и вообще сваливается на совесть отдельных личностей). На самом деле, тема тут даже не одна, а как минимум две: составление алгоритмов и оценка их сложности.

Я попробую впихнуть первое представление об этой теме в одно занятие, дабы дать первый вкус и, может, несколько простейших приёмов, и хотя бы установить какую-то терминологию.

The first rule of optimization

Но прежде, чем переходить к теме, я обязан познакомить вас с самым главным правилом: the first rule of optimization is: DON'T DO IT!.

Перевожу на русский: короткая и понятная функция лучше длинной и быстрой. Потому, узкое горлышко всё равно на практике окажется совсем не там, где вы оптимизировали.

Задача

Как водится, рассказы об алгоритмах я буду делать на примере подсчёта n-го элемента списка всех чисел Фибоначчи. (Сложилась в программировании такая традиция. Это и понятно: задача выглядит одновременно и достаточно просто, и имеет достаточно сложности, чтобы демонстрировать на ней много разных подходов).

Для начала вспомним (а кто не знает, узнаем) определение чисел Фибоначчи. Оно простое: первое и второе числа Фибоначчи – единицы; каждое следующее число Фибоначчи есть сумма двух предыдущих.

Можно записать это определение формулой:

• f₁ = 1
  f₂ = 1
  f_n = f_n-1 + f_n-2

Пример 1: рекурсия (обратный проход, a.k.a. всплытие)

Если приглядеться, это определение уже очень похоже на обычную питоновскую рекурсию. Чуть-чуть подправим синтаксис так, чтобы получился питон, и получим:

   1 def fib1(n):
   2     if n == 1 or n == 2:
   3         return 1
   4     else:
   5         return fib1(n - 1) + fib1(n - 2)

Эта функция вызывает сама себя. Такой приём программирования называется рекурсия.

=== Как сочинять рекурсию ==

При сочинении рекурсивной реализации, если сама задача не сформулирована сразу в виде рекурретных соотношений (как в нашем случае), рассуждения должны быть примерно такими:

• предположим, у нас есть решения (точнее, ответы) этой задачи для более простого случая (в нашем примере мы предполагаем, что мы уже посчитали числа Фибоначчи для n - 1 и n - 2)

• в этом предположении опишем, как из этих ответов получить ответ для заданного нам вопроса (т.е. fib1(n)).
• выберем необходимый минимум тривиальных случаев (в нашем случае это n = 1 и 2) и напишем для них ответы
• проверим, что для случаев, близких к тривиальным функция ведёт себя так, как нужно

В общем случае рекурсивная функция будет выглядеть примерно так:

   1 def функция(аргументы):
   2     # условия завершения рекурсии:
   3     if простой случай:
   4         return простой ответ
   5     elif другой простой случай:
   6         return другой простой ответ
   7     elif ещё один простой случай:
   8         return ещё один простой ответ
   9     # собственно рекурсивный вызов:
  10     else:
  11         return функция(аргументы попроще) и чуть-чуть вычислений

Стек вызовов

Посмотрим, как будет вычисляться эта функция. Для этого нам понадобится немного представления о том, как устроен интерпретатор питона.

Когда питон вызывает функцию, он создаёт у себя специальное место в памяти, где он запоминает: какую строчку функции он сейчас исполняет, и все значения локальных переменных функции. Соответственно, когда из этой функции мы вызываем ещё одну функцию, питон снова создаёт такое же место в памяти. Список всех таких мест в памяти называется стеком вызовов (стек от англ. stack – стопка; полное название: call stack или stack trace).

Стек вызовов легко наблюдать через дебаггер – там от стека отображается только имя функции и строка в ней, но если по нему щёлкнуть, то дебаггер показывает, какие локальные переменные хранятся на этом уровне стека.

Стек вызвов печатает питон при ошибке, чтобы объяснить, где же именно случилась ошибка. Эту картину вы уже наблюдали не один раз.

Обычно стэк изображают растущим сверху вниз или слева-направо (у нас он будет расти слева-направо, так удобнее).

Итак. Вызвали мы, например,

   1 >>> fib1(4)

На внешнем уровне стэка у питона нет никаких переменных, он только знает, что он сейчас вычисляет fib1(4):

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

Питон проверяет if, условие не выполняется, переходит в else:

Идём считать fib1(3):

Далее:

При очередном вызове fib1 мы попали внутрь условия if, и наконец-то дошли до первого return, который мы можем выполнить:

Произойдёт следующее:

Мы подставили значение из return вместо вызова, который к нему привёл, и свернули последний уровень стека. Но на вызове с n = 3 в return значение ещё не получено, снова нужно вызывать fib1:

Вот такое непростое дело – быть интерпретатором питона.

Если вы не понимаете, в чём у вас в программе ошибка, зачастую очень помогает представить себя интерпретатором питона и вот точно так же, как это сейчас изобразил я, повторить его работу.

Сложность алгоритма

Данная реализация функции хорошая и понятная, но у неё есть один недостаток: она _ОЧЕНЬ_ медленная.

Нетрудно посчитать, что функции fib(1) и fib(2) суммарно будут вызываться при такой реализации примерно fib(n) раз при вычислении значения fib(n). Ну а fib(n) ведёт себя асимптотически так же, как и e ** n. Историю про шахматную доску и экспоненту с n = 64 мы с вами помним.

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

Так что попробуем изобрести что-нибудь другое.

Пример 2: кэширование

Получить вторую реализацию мы можем рассуждая двумя способами.

Способ размышления первый. Мы хотим всё-таки иметь соотношение, похожее на исходную постановку задачи. Мы выяснили уже, что если мы на каждом шагу делаем рекурсивный вызов, это плохо. И мы знаем из постановки задачи, что нам нужно использовать для n-го шага результаты с предыдущих шагов. Давайте тогда результаты с предыдущих шагов хранить в массиве, а основное отношение у нас приобретёт вид вычисления очередной ячейки массива по значениям двух других ячеек: fib[n] = fib[n - 1] + fib[n - 2]

Способ размышления второй. Попробуем сделать предыдущую реализацию всё-таки работающей не за экспоненту(n) шагов, а побыстрее. Мы видим, что у нас очень часто случаются вызовы с одним и тем же значением аргументов, и именно из-за этого вылезает плохая сложность функции. Давайте тогда складывать результаты вычисления функции для каждого аргумента в массив! Такой подход называется кэшированием.

Каким бы образом мы ни рассуждали, у нас получается вот такая реализация:

   1 def fib2(n):
   2     fibs = [1, 1] + range(n - 2)
   3     for i in range(2, n):
   4         fibs[i] = fibs[i - 1] + fibs[i - 2]
   5     return fibs[n - 1]

Ещё один приём программирования, на который я хочу обратить ваше внимание: мы сразу создали список нужной длины. В питоне нельзя присваивать за границы существующего списка (хотя есть конструкция append, и +=). В питоне нету никаких деклараций маиссивов или прочих конструкций, которые бы нас обязывали это делать. Но ведь всё, что нам нужно – это список длины n, заполненный каким-нибудь мусором. А это мы умеем, как раз это у нас делает range! (Можно было бы написать и более красиво: fibs = [1, 1] + [None] * (n - 2)}}. Заодно тут был бы элемент защиты от нашей собственной ошибки: если мы куда-то почему-то не записали значение, там будет {{{None).

Ход вычисления

Ход вычисления тут очень простой. Посмотрим снова на примере

   1 >>> fib(4)

Демонстрирую это для того, чтобы показать, что почти всегда ход исполнения питонской программы – даже ход исполнения цикла for – можно свести к последовательности присваиваний в переменные. Это намекает нам на то, что можно придумать удобный формат записи хода исполнения нерекурсивных функций: просто писать последовательность присваиваний. Покуда у нас нет сложной рекурсии, всё, что нас интересует, происходит на одном уровне стека.

Пример 3: рекурсия (прямой проход, a.k.a. погружение)

Посмотрим снова на пример 1. Основное действие у него происходит тут: return fib(n - 1) + fib(n - 2). Т.е. мы до рекурсивного вызова считаем новые значения n, делаем два рекурсивных вызова, и только на возврате из рекурсии считаем, наконец, результат вычисления функции.

Иногда это бывает плохой идеей и хочется результат очередного шага рекурсии считать до рекурсивного вызова. Такой подход называется работой на прямом проходе рекурсии. (В данном случае этот пример носит определённо извращенческий характер, и разве что показывает разнообразие возможных подходов к одной и той же простой задаче).

Итак, мы решили работать на прямом проходе. Следовательно, нам придётся ввести вспомогательную функцию, которая будет делать собственно саму рекурсию: у этой функции будет больше аргументов, чтобы для шага рекурсии было достаточно данных.

Тут у нас возникает сложная задача: на какой вопрос будет отвечать наша вспомогательная функция? Для самой нашей функции вопрос известен: она получает n и отвечает на вопрос, каким будет n-е число Фибоначчи. Для вспомогательной функции я предлагаю такую постановку вопроса: она получает n, первое число Фибоначчи, второе число Фибоначчи, и отвечает на вопрос, каким будет n-е число Фибоначчи за ними.

   1 def fib3(n):
   2     return _fib3(n, 1, 1)
   3 
   4 def _fib3(n, a, b):
   5     if n == 1:
   6         return a
   7     else:
   8         return _fib3(n - 1, b, a + b)

Логика довольно проста. Нам даны первое и второе числа. Соответственно, для n == 1 и n == 2 мы ответ сразу знаем: для 1 это a, для 2 это b. (Красоты и понятности ради, я убрал условие для n == 2: оно нам и не потребуется).

Если же мы ответа не знаем сразу, то из двух текущих чисел Фибоначчи мы можем посчитать два следующих.

Дословно это в примере и написано. Оставляю читателю в качестве задачи убедиться, что эта функция работает правильно.

Пример 4: цикл с запоминанием

Очередной подход кажется очень похожим на пример 2, но демонстрирует совсем другую идею.

В питоне есть большое количество объектов, которые ведут себя примерно как список – их содержимое можно перебирать циклом for, – но списком они не являются – у них нельзя попросить i-й элемент. Пока что мы на такие объекты не натыкались, но скоро наткнёмся. Когда мы работаем с такого рода объектом, и нам нужно описать алгоритм, который учитывает не только очередной элемент, но и его соседей, всё, что мы можем сделать – это запоминать значения с предыдущих итераций.

Вот как это будет выглядеть на примере чисел Фибоначчи:

   1 def fib4(n):
   2     prev = None
   3     pprev = None
   4     fib = 1
   5     for i in range(n):
   6         if prev is not None and pprev is not None:
   7             fib = prev + pprev
   8         pprev = prev
   9         prev = fib
  10     return fib

Здесь в основной части тела цикла (т.е. внутри if) prev – значение fib с предыдущей итерации, а pprev – с пред-предыдущей.

if можно переписать покрасивее: if None not in [prev, pprev].

Ещё можно сменить точку зрения на то, что же именно мы считаем предыдущим и пред-предыдущим значениями: мы знаем первые два значения, поэтому мы можем вместо того, чтобы заполнять переменные изначально None, заполнить их сразу содрежательными значениями, избавиться от условия в теле цикла, и делать на две итерации меньше, лишь бы не ошибиться с тем, что мы возвращаем:

   1 def fib5(n):
   2     fib = 1
   3     prev = 1
   4     pprev = 1
   5     for i in range(n - 2):
   6         fib = prev + pprev
   7         pprev = prev
   8         prev = fib
   9     return fib

Как я уже объяснил, иногда использование такого подхода в питоне оказывается неизбежным.

Кроме этого, основное его достоинство в оптимальности: мы не заводим лишних больших массивов (оптимизация по объёму памяти), мы не делаем большого количества дорогостоящих операций и работаем в линейное время (оптимизация по времени). Но это тот самый случай, против которого я предупреждал: optimization: DON'T DO IT. Хранение предыдущего шага итерации зачастую оказывается довольно неочевидным для читателя, провоцирует к ошибкам (если мы не в тот момент сохраняем предыдущее значение, полезут ошибки, которые бывает трудно выловить), а если нам приходится хранить больше одного значения с предыдущей итерации, то почвы для ошибок становится ещё больше и требуется крайняя внимательность при программировании.

Мудрый программист знает, что он невнимателен, и использует те подходы, которые требуют от него меньше умственных усилий и защищают его от собственных ошибок.

Основы алгоритмизации – про рекурсию