Основные структуры данных

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

В настоящей главе сначала рассматривается устройство оперативной памяти и стоимость хранения простых значений, затем — собираемые из них структуры: массивы постоянного и переменного размера, связные списки, стек, очередь и дек. Для каждой структуры выясняется, какие операции она выполняет быстро, какие медленно и почему.

Выбор между списком и деком, сделанный при обработке данных эксперимента, меняет время расчёта на порядок, и никакой код, написанный поверх неудачной структуры, этого не компенсирует.

Оперативная память и представление данных

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

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

Устройство оперативной памяти

Оперативная память, или ОЗУ, служит программе черновиком для вычислений: в неё можно записывать и перезаписывать информацию, а записанное — считывать обратно.

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

Оперативная память разбита на ячейки размером в 1 байт, и у каждой ячейки есть свой порядковый номер, называемый «адресом» (отдельные биты внутри ячейки адресов не имеют). Процессор, работающий с оперативной памятью напрямую, обращается к данным по адресам почти так же, как программа обращается к переменным по имени.

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

Представление базовых типов данных в ОП

Наименьшая ячейка имеет размер в 1 байт, состоящий из 8 бит. Каждый бит принимает одно из двух значений: 0 или 1. Восемь бит позволяют закодировать \(2^8 = 256\) вариантов, поэтому в такую ячейку можно записать, например, целое число, лежащее в промежутке от 0 до 255.

Если считать записанные числа номерами символов, то в 1 байт умещается один символ ASCII (тип char): латиница, цифры и основные знаки препинания занимают меньше 128 кодов. Для кириллицы места уже не хватает: в однобайтовых кодировках наподобие CP1251 она размещена в верхней половине таблицы, а в UTF-8, принятом сегодня по умолчанию, каждая русская буква занимает два байта — отсюда расхождение между len(text) и len(text.encode()), о котором шла речь в главе «Объекты и память».

Самый распространённый тип целых чисел int занимает 4 байта и позволяет закодировать числа от –2 147 483 648 до 2 147 483 647.

Границы легко вычислить. В 4 байтах содержится 32 бита, один из которых кодирует знак. Оставшийся 31 бит позволяет закодировать \(2^{31} = 2;147;483;648\) чисел. Число «ноль» также занимает один из кодов, поэтому положительных чисел остаётся на одно меньше, чем отрицательных.

Если числа не превышают по модулю два миллиарда, этого типа достаточно. Всего значений около четырёх миллиардов, но половина из них отрицательные. Если точно известно, что переменная не может быть отрицательной, подходит тип беззнаковых целых unsigned int, хранящий числа от 0 до 4 294 967 295.

Вещественные (то есть дробные) числа чаще всего кодируются типом double, «числами с плавающей точкой», занимающими 8 байт. Восьми байт хватает и на очень большие числа, такие как \(\pm10^{308}\), и на близкие к нулю, например \(\pm10^{-308}\).

Диапазон, однако, не то же самое, что точность. Под мантиссу, цифровую часть числа, из восьми байт отведено 53 бита, что соответствует примерно шестнадцати значащим десятичным цифрам; всё, что за них не поместилось, отбрасывается округлением. Наименьшая добавка, которую единица ещё различает, называется машинным эпсилон и равна примерно \(2.2\cdot10^{-16}\), причём шаг между соседними представимыми числами не постоянен, а растёт вместе с самим числом, оставаясь относительным. Отсюда 0.1 + 0.2 != 0.3: ни одна из этих дробей в двоичной записи не конечна, и сумма отклоняется от ответа на последние биты. Отсюда же следует и потеря точности при вычитании близких величин: старшие цифры, которыми они совпадали, взаимно уничтожаются, и от разности остаётся столько верных цифр, сколько их было в различающейся младшей части.

Составные типы данных

Подсчитаем, сколько памяти потребуется для хранения массива, составленного из 10 строк по 20 символов каждая.

Во-первых, потребуется хранить сам текст. Это займёт $$10; строк \cdot (20; \frac{символов}{строка}) \cdot (1;\frac{байт}{символ}) = 200; байт$$ Этого было бы достаточно, если бы строки располагались в памяти друг за другом, но выполнять с ними операции в таком случае было бы сложно.

Поэтому в массивы (и в другие составные структуры) зачастую помещаются не сами объекты, а только указатели на них, то есть адреса ячеек, отведённых под эти объекты в оперативной памяти.

Во многих других языках каждый объект в программе записан в специальную «обёртку», содержащую, помимо данных, вспомогательную информацию. Из-за такой обвязки в Python даже короткие целые числа занимают не 4 байта, а почти 30. Для хранения строки требуется около 40 байт служебных данных, а для хранения массива и того больше. Объекты в таких языках ведут себя как строки из примера выше: они могут находиться в произвольном месте памяти, и любое обращение к ним осуществляется по сохранённому адресу.

Подсчитаем, сколько памяти расходует массив, собранный из 10 чисел в Python, и на что она уходит:

import sys
print(sys.getsizeof(42))  # => 28 байт занимает короткое целое число
print(sys.getsizeof([]))  # => 56 байт занимает пустой массив
print(sys.getsizeof([42]))  # => 64 = (56 + 8) байт занимает массив с одним элементом.
print(sys.getsizeof([1,2,3,4,5,6,7,8,9,10]))  # => 136 = (56 + 8*10) байт занимает массив
                               # с десятью элементами.
                               # сами данные хранятся отдельно
                               # и добавляют 280 = (28 * 10) байт

56 байт уходит на сам массив, далее по 8 байт на адрес каждого элемента и ещё по 28 байт на каждое записанное число. Итого массив из десяти чисел в Python занимает 56 + (8 + 28) * 10 байт = 416 байт против 40 байт в C++.

Освобождение памяти

Если программа перестала пользоваться объектом, это ещё не означает, что занимаемая им память освобождена. В языке C++ необходимо следить за тем, чтобы выделенная память освобождалась. Встроенные контейнеры наподобие std::vector сами выделяют память при создании и отдают её обратно, когда переменная, хранящая контейнер, выходит из области видимости.

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

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

Массивы постоянного размера

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

Самый простой тип массивов имеет фиксированный размер и хранит элементы одного и того же типа. Например, в созданный массив из десяти целых чисел нельзя добавить ещё один элемент или записать объект неподходящего типа. Такие массивы встречаются в языке C как int numbers[10], а в C++ как std::array<int, 10> numbers.

С массивами фиксированного размера можно выполнить только две операции:

  • получить значение элемента по заданному индексу,
  • перезаписать значение по указанному индексу.

Обе операции выполняются за \(O(1)\).

Устройство массива

Массив представляет собой набор однотипных данных, расположенных в памяти друг за другом, поэтому он всегда занимает один непрерывный участок. Точное местоположение выделенного участка операционная система сообщает программе в момент создания массива.

В начале выделенного участка памяти находится нулевой элемент, сразу за ним первый и далее по порядку, друг за другом, без пропусков. Зная адрес элемента, его можно прочитать или записать.

Пусть имеется массив numbers из 10 беззнаковых целых чисел, адрес нулевого элемента которого равен 1000. Адрес следующего элемента равен адресу начала плюс размер элемента в байтах. Каждое число занимает по 4 байта, и нулевой элемент займёт байты 1000, 1001, 1002, 1003. Следовательно, элемент с индексом 1 будет записан по адресу 1004.

Сложность вставки и удаления в динамических массивах

Динамические массивы иногда называют «векторами», потому что в C++ они реализуются классом std::vector. В Python динамический массив скрыт за классом list, и, несмотря на название, это не список, а массив.

Сложность вставки в динамический массив

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

Элемент можно вставить в любое место массива; вставка в начало и в конец являются частными случаями. Худший случай — вставка в начало, поскольку все лежащие правее элементы приходится сдвинуть на одну позицию, а это \(O(n)\). Добавление в конец — лучший случай: сдвигать ничего не нужно, и стоимость операции составляет \(O(1)\).

Сложность удаления из динамического массива

При удалении, как и при вставке, приходится сдвигать все элементы, стоящие правее затронутой ячейки: при добавлении — на один вправо, при удалении — на один влево. Стоимость та же: \(O(n)\) при работе с началом массива и \(O(1)\) при работе с концом.

Реаллокация в динамических массивах

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

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

Выделение памяти является долгой операцией, а копирование обходится ещё дороже: пройти придётся по всем записанным элементам, а это \(O(n)\). Возникает вопрос, почему добавление в конец массива при этом стоит \(O(1)\).

Рассмотрим программу, добавляющую в массив тысячу элементов по одному за раз:

values = []
for i in range(1000):
    values.append(i)

Операцию append() можно представить как две: реаллокацию и присваивание значения элементу массива. Операции присваивания учитывать не будем: их число равно количеству добавляемых элементов и оптимизации не поддаётся. Время же реаллокаций зависит от выбранного подхода.

Если бы реаллокация происходила при каждом добавлении элемента, сложность оказалась бы квадратичной.

Во-первых, чтобы не приходилось на каждом шаге выделять дополнительную память, необходимо держать запас свободного места в массиве. Например, если увеличивать размер сразу на 100 элементов, программа будет запрашивать память в 100 раз реже. Однако такая программа всё ещё работает за \(O(n^2)\), хотя и с небольшой константой при квадратичном члене.

Таким образом, у массива появляются два разных размера: size (количество занятых ячеек) и capacity (ёмкость выделенного участка), причём size ≤ capacity.

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

Пусть изначальная ёмкость массива равна 1, а при каждой реаллокации она удваивается. Тогда на первой реаллокации копируется 1 элемент, на второй — 2, на третьей — 4, затем 8, 16, 32, 64, 128, 256 и 512, после чего накопленная ёмкость равна 1024.

Общее число копирований к моменту добавления 1000-го элемента: \(S = 1 + 2 + 4 + \cdots + 512 = 1024 - 1\).

В общем случае, если необходимо добавить \(n\) элементов, где \(2^k \lt n \le 2^{k+1}\), последнее копирование затронет \(2^k\) элементов. Запишем сумму получившейся геометрической прогрессии: \(S = \sum_{i=0}^k 2^i = 2^{k+1} - 1 = 2 \cdot 2^k - 1 \le 2\cdot n\).

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

Связные списки

Элементы массива в памяти компьютера расположены последовательно. Чтобы вставить или удалить элемент из начала массива, требуется \(O(n)\) операций, потому что передвинуть придётся каждый элемент, стоящий следом.

Структурой, не требующей при вставке или удалении сдвигать остальные элементы, является связный список (англ. linked list); он присутствует в стандартных библиотеках многих языков: std::list в C++, LinkedList в Java.

В языке Python list остаётся динамическим массивом, хотя и обозначен словом «список».

Устройство связного списка

В связном списке у каждого элемента, помимо его значения, есть ссылка на следующий элемент списка, за исключением последнего, ссылающегося в никуда. В зависимости от языка программирования ссылка в никуда может представлять собой объект None, нулевой указатель или аналогичную сущность. У связного списка определяют точку старта, называемую «головой списка».

Достоинства и недостатки связного списка

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

Платой за это является доступ по индексу: элементы лежат вразброс, и до нужного приходится идти от головы списка, перебирая все звенья по дороге, а это \(O(n)\) операций.

Двигаться по односвязному списку можно только в одном направлении. Отсюда ещё один недостаток: быстро удалить элемент не удастся, потому что неизвестно, какой элемент на него ссылается. В худшем случае поиск предыдущего звена, хранящего эту ссылку, потребует \(O(n)\) операций, тогда как вставка элемента после текущего выполняется быстро.

Структура данных стек

Стек работает по принципу LIFO (англ. last in, first out, «последним пришёл, первым ушёл»). Извлечь можно только элемент, положенный последним.

На стеке реализована кнопка «назад» в браузере: одно нажатие возвращает на предыдущую страницу, следующее — на открытую перед ней.

Отмена последних операций в текстовых редакторах также реализована на стеке.

Наглядной моделью служит стопка книг в коробке: взять можно только верхнюю, а отложив её — следующую сверху. Из стека также извлекается только верхний, положенный последним, элемент.

Интерфейс стека

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

  • push(item) добавляет элемент на вершину стека;
  • pop() возвращает элемент с вершины стека и удаляет его;
  • size() возвращает размер стека (количество лежащих в нём элементов).

Иногда присутствуют дополнительные операции:

  • peek() или top() возвращает элемент с вершины стека, не удаляя его;
  • isEmpty() определяет, пуст ли стек.

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

Реализация стека

Стек на основе массива: в конструкторе создаётся пустой массив, а методы push() и pop() его изменяют:

class Stack:
     def __init__(self):
         self.items = []

     def push(self, item):
         self.items.append(item)

     def pop(self):
         return self.items.pop()

     def peek(self):
         return self.items[-1]

     def size(self):
         return len(self.items)

stack = Stack()
stack.push('apple')
stack.push('banana')
stack.push('orange')

stack.pop()

Структуры данных: очередь и дек

Очередь, в отличие от стека с его LIFO, работает по принципу FIFO (англ. first in, first out): первым извлекается элемент, добавленный раньше всех.

Бытовые очереди подчиняются тому же правилу:

  • Кассир в магазине обслуживает покупателей по одному, и покупатель будет обслужен не раньше, чем все вставшие в очередь до него.
  • На горячей линии, когда все операторы заняты, автомат также ставит звонящих в очередь.

Такие сценарии моделируются структурой данных очередь.

Интерфейс очереди

Как и стек, очередь задаёт интерфейс взаимодействия с данными, гарантирующий набор методов, но не способ их хранения. Очередь принято реализовывать так, чтобы и вставка, и удаление элемента стоили \(O(1)\).

Методы очереди:

  • push(item) добавляет элемент в конец очереди;
  • pop() берёт элемент из начала очереди и удаляет его;
  • peek() берёт элемент из начала очереди без удаления;
  • size() возвращает количество элементов в очереди.

Дек: очередь с двумя концами

Очередь пропускает элементы только в одну сторону: вход через хвост, выход через голову. Дек (deque, от double-ended queue, двусторонняя очередь) позволяет добавлять и удалять элементы с любого конца, и обе операции выполняются за \(O(1)\).

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

Интерфейс дека объединяет стек и очередь:

  • append(item) добавляет элемент в конец;
  • appendleft(item) добавляет в начало;
  • pop() берёт элемент с конца и удаляет;
  • popleft() берёт с начала и удаляет.

Дек обобщает обе структуры: работа с одним концом даёт стек, вход с одного конца и выход с другого — очередь. Поэтому в Python нет отдельной простой очереди, её роль выполняет дек. Класс queue.Queue из стандартной библиотеки решает другую задачу, синхронизацию между потоками, и внутри содержит тот же дек.

В стандартной библиотеке дек находится в модуле collections:

from collections import deque

buf = deque()
buf.append(1)          # [1]
buf.append(2)          # [1, 2]
buf.appendleft(0)      # [0, 1, 2]

print(buf.popleft())   # 0, забрали из начала
print(buf.pop())       # 2, забрали с конца
print(buf)             # deque([1])

Преимущества дека перед списком

Список в Python поддерживает и insert(0, x), и pop(0); разница заключается в стоимости. Список устроен как динамический массив, его элементы лежат в памяти подряд; чтобы вставить элемент в начало, необходимо сдвинуть все остальные на одну позицию вправо, а это \(O(n)\) на каждую вставку. Дек устроен как связанные между собой блоки, и добавление к любому его концу не затрагивает уже уложенные элементы.

Замер на Apple M4, заполнение структуры с начала:

      N |      list |     deque | отношение
   1000 |    0.19 мс |  0.015 мс |     13x
  10000 |   13.09 мс |  0.122 мс |    107x
 100000 | 1358.53 мс |  1.364 мс |    996x

Важны не сами числа, а последний столбец. Отношение растёт вместе с \(N\), и это является признаком разной алгоритмической сложности. Если бы дек был просто реализован эффективнее, выигрыш оставался бы постоянным. Здесь же на тысяче элементов разница тринадцатикратная, на ста тысячах — тысячекратная, потому что время списка растёт как \(O(n^2)\), а время дека как \(O(n)\).

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

buf = []
for x in data:
    buf.append(x)
    if len(buf) > 1000:
        buf.pop(0)         # удаление из начала — O(n)

У дека ограничение длины встроено в конструктор, и при переполнении он сам удаляет элемент, лежащий на противоположном конце.

buf = deque(maxlen=1000)
for x in data:
    buf.append(x)          # старое значение уходит само, O(1)

На потоке из 200 000 отсчётов первый вариант отработал за 21 мс, а второй за 2 мс: порядок, выигранный одной строкой в выборе структуры данных.

Дек платит за это доступом по индексу. У списка элементы лежат подряд, поэтому lst[50000] вычисляется арифметикой по адресу за \(O(1)\). У дека до середины приходится добираться по блокам, перебирая сцепленные звенья, и это \(O(n)\). В том же замере обращение к середине заняло 0.005 мкс у списка против 0.525 мкс у дека, то есть почти в сто раз дольше.

Правило выбора, работающее почти всегда: если нужен произвольный доступ по индексу — список; если нужны быстрые операции с обоими концами, а середина лишь пробегается целиком — дек. insert(0, x) или pop(0) внутри цикла почти наверняка означают, что требуется дек.

Стек вызовов

Код программы разделён на функции: базовые объединяются в сложные, а те в ещё более сложные, и вся программа представима как одна функция, вызывающая множество других.

Устройство стека вызовов

Допустим, написана программа на C++. Первой вызывается функция main(), в которой вызывается функция A. Она вызывает функцию B, которая, в свою очередь, вызывает C.

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

        вершина стека
   ┌──────────────┐
   │      C       │  ← выполняется сейчас
   ├──────────────┤
   │      B       │  вызвала C
   ├──────────────┤
   │      A       │  вызвала B
   ├──────────────┤
   │    main()    │  вызвала A
   └──────────────┘
         дно

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

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

def say_hello(name):
    print(f"Привет, {name}")
    print_horoscope(name.upper())
    print(f"Пока, {name}, хорошего дня!")

def print_horoscope(name):
    print(f"{name}! Сегодня подходящий день для прогулок в парке и изучения рекурсии")

say_hello('Гоша')

В разных частях программы переменная name хранит разные значения: при входе в say_hello() в ней записано 'Гоша', в print_horoscope() — 'ГОША', а после возврата в say_hello() снова 'Гоша'.

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

Работа стека: шаг за шагом

Первая команда программы — вызов say_hello(), под который на стеке выделяется блок памяти.

   ┌────────────────────┐
   │  say_hello()       │  ← выделен блок под вызов
   └────────────────────┘

В блок записывается адрес возврата — адрес инструкции, следующей сразу за местом вызова функции.

Туда же помещаются аргументы, с которых начинается набор локальных переменных. Здесь один аргумент name = 'Гоша', других локальных переменных нет.

   ┌────────────────────┐
   │  say_hello()       │
   │    адрес возврата  │
   │    name = 'Гоша'   │
   └────────────────────┘

Первая инструкция say_hello() выводит «Привет, Гоша». Затем метод upper() возвращает строку 'ГОША', и она становится параметром print_horoscope().

Вызовы print() и upper() на схеме не показаны, хотя они также помещаются на стек при вызове и снимаются с него после завершения.

При вызове print_horoscope() с параметром 'ГОША' выделяется новый блок памяти с параметрами, адресом возврата и местом под локальные переменные. Он ложится поверх блока say_hello() — та же стопка книг в коробке, только из блоков памяти.

   ┌────────────────────┐
   │  print_horoscope() │  ← новый блок лёг сверху
   │    адрес возврата  │
   │    name = 'ГОША'   │
   ├────────────────────┤
   │  say_hello()       │
   │    адрес возврата  │
   │    name = 'Гоша'   │
   └────────────────────┘

Первая инструкция print_horoscope() выводит «ГОША! Сегодня подходящий день для прогулок в парке и изучения рекурсии».

Инструкций в print_horoscope() больше нет, и управление возвращается по адресу, записанному в её блоке. Блок снимается со стека, а значение переменной name восстанавливается.

   ┌────────────────────┐
   │  say_hello()       │  ← верхний блок снят,
   │    адрес возврата  │    name снова 'Гоша'
   │    name = 'Гоша'   │
   └────────────────────┘

Затем исполняется инструкция say_hello(), следующая за вызовом print_horoscope(), и выводит «Пока, Гоша, хорошего дня!»

Это последняя инструкция say_hello(), поэтому происходит возврат из функции, и её блок освобождается.

   ┌────────────────────┐
   │                    │  ← стек пуст
   └────────────────────┘

Рекурсия. Переполнение стека вызовов

Функции, вызывающие сами себя с изменёнными аргументами, называются рекурсивными, и они также используют стек вызовов.

Здесь речь идёт о цене, которую рекурсия платит стеком; как рекурсия записывается, из чего складываются рекурсивный и базовый случаи и какие ошибки при этом типичны, рассматривается далее, в главе «Рекурсия и сортировки».

Факториал

Факториал натурального числа можно вычислить как произведение всех натуральных чисел от 1 до n: \(n! = 1 \cdot 2 \cdot ... \cdot (n-1) \cdot n\)

Рекурсия и стек вызовов

Рекурсивная функция вычисления факториала:

def factorial(n):
    if n == 1 or n == 0:
        return 1
    return n * factorial(n - 1)

Вызов factorial(3):

   Погружение:                    Возврат:
   ┌──────────────┐               ┌──────────────┐
   │ factorial(1) │ вернёт 1      │ 1            │
   ├──────────────┤               ├──────────────┤
   │ factorial(2) │ ждёт          │ 2 * 1 = 2    │
   ├──────────────┤               ├──────────────┤
   │ factorial(3) │ ждёт          │ 3 * 2 = 6    │
   └──────────────┘               └──────────────┘

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

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

Чтобы хранить локальные переменные и адрес возврата на каждом уровне рекурсии, потребуется \(O(d)\) памяти на стеке, где d — глубина рекурсии. При вычислении факториала \(n!\) глубина равна n, поэтому приведённая выше функция расходует \(O(n)\) памяти на стеке.

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

Ограничений два. Первое устанавливает сам Python: по умолчанию около тысячи вложенных вызовов, далее RecursionError, а поднять порог можно через sys.setrecursionlimit. Второе — стек операционной системы, обычно 8 МБ; достичь его можно, только сняв первое. Здесь важна версия. До Python 3.10 кадр каждого вызова помещался на стек C, и глубже нескольких десятков тысяч вызовов рекурсию довести было нельзя. С 3.11 кадры питоновских функций переехали в кучу, поэтому чистая рекурсия с поднятым порогом доходит и до миллиона уровней. Однако когда цепочка вызовов уходит через C (например, через __repr__), стек C работает по-прежнему, и переполнение никуда не исчезает (англ. stack overflow). В одних языках при этом возникает исключение «Stack Overflow», в других ошибка «Segmentation Fault».

factorial(10_000)

Предотвращение переполнения стека

Приёмы против переполнения стека:

  • Иногда рекурсию можно заменить циклом. Например, факториал переписывается следующим образом:
def factorial(n):
    accumulator = 1
    i = n
    while i > 1:
        accumulator *= i
        i -= 1
    return accumulator
  • Другой способ — собственный стек, эмулирующий стек вызовов, но без ограничений встроенного.

Объёмом памяти под стек вызовов можно управлять. В некоторых языках — непосредственно во время работы программы: в Python метод setrecursionlimit() модуля sys параметром limit задаёт максимальную глубину рекурсии; наибольшее значение зависит от платформы и всё равно существенно ограничено. Текущее значение возвращает getrecursionlimit(). В Java и JavaScript размер стека вызовов задаётся настройками виртуальной машины при запуске и во время работы не меняется. Иногда размер стека вызовов можно изменить на уровне операционной системы.

sys.getrecursionlimit()

Как выбор структуры сказывается на работающем сервисе, показано в главе «Базы данных»: там одна задача переложена в четыре хранилища, от текстового файла до кеша.

Резюме

Сводная таблица для выбора структуры под задачу:

СтруктураДоступ по индексуВставка в конецВставка в началоПоиск
Массив постоянного размера\(O(1)\)нетнет\(O(n)\)
Динамический массив (list)\(O(1)\)\(O(1)^*\)\(O(n)\)\(O(n)\)
Связный список\(O(n)\)\(O(n)^{**}\)\(O(1)\)\(O(n)\)
Дек (deque)\(O(n)\)\(O(1)\)\(O(1)\)\(O(n)\)

\(^*\) Амортизированно: изредка происходит реаллокация, но в среднем на каждый добавленный элемент приходится константа.

\(^{**}\) В том виде, в каком список описан выше, с одной только головой: чтобы добавить элемент в конец, приходится пройти весь список. Если хранить ещё и ссылку на хвост, вставка в конец становится \(O(1)\), и так устроены реализации, принятые в стандартных библиотеках.

Универсальной структуры не существует, существует подходящая под задачу. Если элементы постоянно добавляются и снимаются с обоих концов, а в коде используется список, программа платит \(O(n)\) там, где могла бы платить \(O(1)\).

Ни одна из рассмотренных структур не позволяет быстро искать по значению, все дают \(O(n)\). Как обойти это ограничение, рассматривается в следующих главах, посвящённых хеш-таблицам и деревьям поиска.