Как список лежит в памяти

Прошлая глава оставила загадку. Проверка x in set на миллионе элементов занимает столько же, сколько на десятке, а x in list перебирает весь миллион. Откуда такая разница? Множество устроено хитро, до него дойдёт очередь в главе 16. Сначала поймём устройство попроще, которым мы с главы 6 пользуемся в каждой второй строке. Что лежит внутри списка?

Исходный код интерпретатора открыт, и ответ можно было бы в нём прочитать. Мы поступим иначе — как натуралист, которому принесли незнакомого зверя. Сначала понаблюдаем за поведением, потом взвесим, выдвинем гипотезы и проверим их опытом, выведем закон и только в конце возьмём скальпель. Приборов три: секундомер timeit из главы 13, весы sys.getsizeof и, ближе к концу, микроскоп, который заглядывает прямо в память. Все опыты идут на сервере курса, на живом интерпретаторе CPython 3.13; на нём получены и все числа в этой главе.

Полевые наблюдения

Начнём с поведения. Возьмём список из миллиона чисел и попросим достать из него элемент.

В списке миллион чисел. Что быстрее: прочитать a[0] или a[999_999]?

a[0] — до него ближе a[999_999] Одинаково

Одинаково — проверьте ниже. Это первое свойство списка, которое придётся объяснить: к элементу он не идёт от начала, а как-то сразу знает, где тот лежит.

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

Запишем в полевой журнал. Чтение — несколько десятков наносекунд, и ему всё равно, сколько в списке элементов. append тоже стоит десятки наносекунд при любой длине. А insert(0, x) на десяти тысячах занимает около двух микросекунд, на ста тысячах — около двадцати, на миллионе — под двести: элементов в десять раз больше — вставка в десять раз дольше. На языке прошлой главы чтение и append стоят $O(1)$, а вставка в начало — $O(n)$.

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

Взвешивание

Второй прибор — весы. Функция sys.getsizeof говорит, сколько байт занимает объект. Взвесим пустой список и списки из нулей разной длины.

Пустой список весит 56 байт, и каждый элемент добавляет ровно 8: один ноль — 64, два — 72, тысяча — $56 + 8 \cdot 1000 = 8056$. Первая гипотеза напрашивается сама: внутри списка есть заголовок в 56 байт, а дальше подряд лежат элементы по 8 байт каждый.

Но число 0 в Python — объект, и весит он не 8 байт. Положим в список что-нибудь потяжелее: хорошая гипотеза должна выдерживать попытки её опровергнуть.

Одна такая строка весит около тринадцати килобайт, а список из тысячи разных строк — те же 8056 байт, что и список нулей. Весы ясно говорят: элементы не лежат внутри списка. Внутри лежит что-то одинаковое по размеру для нуля и для «Войны и мира», по 8 байт на элемент.

Вы уже знаете, что это. В главе 2 имя было ярлыком на верёвочке, привязанным к объекту. Список устроен так же: это ряд ярлыков, каждый привязан к своему объекту, а сами объекты живут в памяти где угодно. Этим объясняется и ловушка из главы 6, где [[0] * 4] * 3 давало три ярлыка на одну строку таблицы. Осталось выяснить, из чего сделан ярлык, раз он весит 8 байт. Это мы увидим под микроскопом, а пока займёмся третьим вопросом — как список растёт.

Опыт: список растёт

Когда мы пишем append, список становится длиннее. Если элементы-ярлыки лежат подряд, при каждом добавлении где-то надо найти место ещё на 8 байт. Как список его находит?

Список растёт по одному элементу через append. Как, по-вашему, он запасает место?

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

Иначе — опыт ниже покажет как. В учебниках обычно рассказывают про удвоение, и до 16 элементов CPython действительно похож на удваивающего. Дальше закон другой.

Поставим опыт. Будем дописывать в пустой список числа по одному и после каждого append взвешивать список. Печатать будем только тогда, когда вес изменился. Из веса легко узнать, сколько мест по 8 байт сейчас отведено под элементы: отнять заголовок и поделить на восемь.

Вот оно: после очередного append вес то стоит на месте, то прыгает. Первый элемент получил сразу четыре места, пятый — восемь, девятый — шестнадцать. Пока похоже на удвоение. Но дальше идёт 24, 32, 40, 52, 64, 76, 92, 108 — места прибавляются, но далеко не вдвое. У списка есть ёмкость — сколько мест отведено — и длина — сколько из них занято. Ёмкость всегда не меньше длины, а когда длина её догоняет, ёмкость прыгает вверх.

Гипотезу удвоения опыт отверг. Какой закон вместо неё? На маленьких числах его не разглядеть: слишком сильно мешает округление. Натуралист в таком случае увеличивает выборку. Дорастим список до миллиона элементов и посмотрим, во сколько раз и на сколько растёт ёмкость при последних скачках.

На миллион добавлений пришлось всего 86 скачков, и каждый увеличивает ёмкость в 1,125 раза — на восьмую часть. Точнее, на восьмую часть и ещё несколько мест: прибавка 73 260 при восьмой части 73 254. Получается закон:

$$\text{новая ёмкость} \approx n + \frac{n}{8} + \text{немного},$$

где $n$ — длина списка в момент скачка. Из-за этого «немного» маленькие списки и растут почти вдвое: при $n = 8$ восьмая часть — одно место, и основную прибавку даёт добавка. Точную формулу CPython, вплоть до последнего места, вы выведете сами в задаче в конце главы и проверите её на живом интерпретаторе на длинах до миллиона.

Вскрытие

Поведение описано, закон найден, пора браться за скальпель. Но сначала несколько слов о памяти.

Память компьютера — это очень длинная улица из пронумерованных домиков-байтов. На машине, где работает наш сервер, их миллиарды. Номер байта называют адресом. Улица необычная: процессор может прочитать байт по любому адресу за одно обращение, не проходя мимо остальных. Поэтому память и называют RAM — random access memory, память с произвольным доступом. Как она устроена из вентилей и почему так умеет, расскажет глава 31.

В CPython функция id(), которую мы знаем с главы 2, возвращает адрес объекта в памяти: «номер» объекта — это номер его первого байта. А модуль ctypes умеет прочитать память по любому адресу. В обычных программах так не делают: ошибётесь адресом — и интерпретатор упадёт. Нам же нужен микроскоп на один опыт. Прочитаем первые сорок байт объекта-списка — пять полей по 8 байт.

Пять полей заголовка — пять находок. По смещению 0 лежит число ярлыков, которые висят на списке: сейчас один, a. Допишите b = a и запустите снова — станет два; когда число падает до нуля, Python освобождает память объекта. По смещению 8 — адрес объекта list: так список знает, какого он типа. По смещению 16 — длина, её и отдаёт len, ничего не пересчитывая. По смещению 32 — ёмкость, которую мы раньше вычисляли по весу: пять элементов, восемь мест. Ещё 16 байт из 56 — служебная запись для сборщика мусора, она лежит прямо перед адресом объекта.

Самое интересное — по смещению 24. Там лежит адрес другого места в памяти: отдельного блока, где хранятся элементы. Заглянем туда: прочитаем по 8 байт подряд, начиная с этого адреса.

В ячейке номер $i$ лежит id(a[i]) — адрес элемента. Ярлык из главы 2 оказался числом: ссылка на объект — это его адрес, и весит она 8 байт, потому что адреса на 64-битной машине восьмибайтовые. Список хранит не числа 10, 20, 30, а адреса мест, где эти числа живут. Поэтому строке из «Войны и мира» и нулю в списке нужно одинаково места.

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

$$\text{адрес}(i) = \text{начало} + 8 \cdot i.$$

Заодно объясняется и загадка прошлой главы. Массив мгновенно отвечает на вопрос «что лежит в ячейке номер $i$». А на вопрос «есть ли где-нибудь число 30» он не отвечает ничем: тридцать может лежать в любой ячейке, и in открывает их по очереди. Если бы номер ячейки можно было вычислить из самого значения, поиск стал бы таким же мгновенным, как чтение по индексу. Так и устроено множество; как именно, расскажет глава 16.

Переезды

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

Переезжает только блок элементов. Сам объект-список с его заголовком остаётся на месте: меняется одно поле, адрес по смещению 24. Поэтому id(a) не меняется, сколько бы список ни рос, и все ярлыки, привязанные к нему, остаются верными.

Теперь то же самое под микроскопом, на живом CPython. Будем дописывать в список по элементу и после каждого расширения смотреть, изменился ли адрес блока. Опыт поставим дважды: в просторной памяти, где кроме нашего списка почти ничего не появляется, и в тесной, где после каждого десятого append программа создаёт ещё один небольшой список-соседа.

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

Монетки

Переезд стоит дорого: перенести надо все ссылки, а их может быть миллион. И всё же append в наших замерах всегда стоил десятки наносекунд: переезды редки, и чем больше список, тем они реже. Чтобы увидеть это точно, отложим секундомер и посчитаем работу: сколько раз ссылку приходится переносить с места на место, пока список дорастёт до $n$ элементов. И сравним закон CPython с другими способами запасать место.

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

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

Возьмём удвоение. Сразу после переезда в списке $m$ элементов и $2m$ мест, копилка пуста. Следующий переезд случится через $m$ добавлений, и переносить тогда придётся $2m$ элементов. Если каждое из этих $m$ добавлений положит в копилку две монеты, к переезду их наберётся как раз $2m$. Значит, трёх монет на один append хватает навсегда: одна на запись, две в копилку. У CPython запас — восьмая часть, до следующего переезда всего $m/8$ добавлений, а переносить надо $9m/8$ элементов: каждому добавлению приходится откладывать по девять монет, всего десять. Больше, но тоже постоянное число. А при запасе в сто мест до переезда сто добавлений, переносить надо все $m$ элементов, и каждое добавление должно отложить $m/100$ — число, которое растёт вместе со списком. Никакой постоянной платы не хватит.

Такую стоимость называют амортизированной, от слова, которым бухгалтеры называют распределение крупной траты на много лет. Отдельный append иногда стоит $O(n)$ — когда на него выпал переезд. Но в среднем по любой длинной последовательности добавлений он стоит $O(1)$. Это гарантия, на удачу здесь ничего не завязано: копилка доказывает, что так будет при любом $n$. Такие рассуждения, монетки в том числе, свёл в общий метод Роберт Тарьян в статье 1985 года «Амортизированная вычислительная сложность».

И всё же CPython не удваивает: у удвоения своя цена. Сразу после переезда пустует половина мест, а у CPython — лишь девятая часть. Это обмен памяти на время, и разные языки выбирают по-разному: ArrayList в Java растёт в полтора раза, std::vector в библиотеке компилятора GCC — вдвое. При любом постоянном множителе больше единицы append остаётся $O(1)$ амортизированно — меняется только число монет.

Почему вставка в начало дорогая

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

Пять сдвигов ради одной вставки. В списке из миллиона элементов сдвигов миллион, и никакой запас тут не помогает: запас стоит в конце, а место нужно в начале. Так же дорого стоят pop(0) (все сдвигаются влево) и вставка или удаление в середине (сдвигается половина). Сдвиг делает быстрый код на C, а не цикл Python, поэтому на маленьких списках его не видно. Но это всё равно $O(n)$, и на больших списках он проявляется, как в нашем первом опыте.

Итог вскрытия. Список Python — динамический массив ссылок. Чтение и запись по индексу — $O(1)$: адрес вычисляется формулой. append и pop() с конца — $O(1)$ амортизированно: работает запас. Вставка и удаление в начале или середине — $O(n)$: сдвиг. Поиск in — $O(n)$: адрес значения ниоткуда не следует. Хотите быструю вставку в начало — нужен зверь другого вида.

Другой вид: связный список

Картинку, которую вы сейчас увидите, — прямоугольники, соединённые стрелками, — впервые напечатали Ньюэлл и Шоу в феврале 1957 года, в статье о том, как программировали Logic Theorist. С тех пор связный список так и рисуют. А в 1975 году Ньюэлл и Саймон получили премию Тьюринга, и в её формулировке среди их заслуг прямо названа «обработка списков». Через пару лет после IPL идею подхватил Джон Маккарти в языке Лисп — название и значит «обработчик списков», LISt Processor.

В Python связный список собирается из объектов, которые мы научились писать в главе 12. Каждый элемент — узел: объект с двумя атрибутами, значением и ссылкой на следующий узел. У последнего узла следующего нет, и там лежит None. Сам список — это ссылка на первый узел, её называют головой, head.

Нажмите «Шаги»: node перепрыгивает по стрелкам от узла к узлу. Другого способа добраться до элемента нет: узлы не лежат подряд, формулы адреса у них нет. Такую цепочку называют связным списком.

Свойства у нового вида зеркальные. Чтобы добраться до элемента номер $i$, надо пройти $i$ стрелок — $O(n)$ вместо $O(1)$ у массива. Зато вставить узел в начало — три действия: создать узел, дать ему ссылку на старую голову и объявить его новой головой. Никто никуда не сдвигается, сколько бы узлов ни было в цепочке. Так же дёшево вставить или удалить узел сразу после того, на котором вы уже стоите: поменять пару стрелок. Запаса и переездов нет совсем: каждый узел живёт где придётся, а порядок держат стрелки.

Сравните в конструкторе «в начало» и «в конец». Первая операция занимает три шага при любой длине. Вторая проходит всю цепочку, чтобы найти последний узел: чем длиннее список, тем дольше. Если такое нужно часто, к голове добавляют вторую ссылку — на хвост, и тогда дописывание в конец тоже становится $O(1)$. Это пригодится в одной из задач.

Сравнительная анатомия

Сведём наблюдения в таблицу, как это делают зоологи, сравнивая скелеты родственных видов. В последней колонке — collections.deque, гибрид, до которого мы скоро дойдём.

* Амортизированно. ** Если хранить ссылку на хвост.

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

Гонка показывает и то, чего нет в таблице. В «вставке в начало» наш связный список ровный, как и положено $O(1)$, но идёт в несколько раз медленнее deque: каждый узел — объект Python, а создать объект куда дороже, чем записать ссылку в готовую ячейку. Асимптотика говорит, как время растёт, но не говорит, с какого уровня оно начинается. Последнюю строку таблицы тоже проверим.

Модуль tracemalloc считает всю память, которую программа взяла у системы. Узел нашего связного списка обходится в 88 байт, ячейка массива — в 8: одиннадцать раз разницы, и это ещё без самих значений. Есть и третья причина, по которой массивы почти всегда выигрывают у самодельных связных списков: процессор читает память кусками, и соседние ячейки массива достаются ему почти даром. Узлы же разбросаны по памяти, и за каждым приходится ходить отдельно. Как это устроено, расскажет глава 34.

Гибрид: deque

В стандартной библиотеке Python есть структура, которая берёт лучшее у обоих видов. Это deque из модуля collections — название читается «дек» и означает double-ended queue, «очередь с двумя концами». Внутри неё связный список, только каждый узел — блок-массив на 64 ссылки, и стрелок в узле две: на следующий блок и на предыдущий. Такую цепочку со стрелками в обе стороны называют двусвязным списком.

Добавить или забрать элемент с любого края — $O(1)$: в крайнем блоке либо есть свободная ячейка, либо к цепочке пристёгивается новый блок, и никого не надо сдвигать. Памяти на элемент почти столько же, сколько у массива: накладные расходы — пара стрелок на 64 элемента. А вот чтение из середины — $O(n)$: надо пройти блоки от ближнего края, хотя шагать приходится сразу по 64 элемента. Это видно в гонке на вкладке «чтение из середины».

Последние строки показывают удобную мелочь: deque(maxlen=3) помнит только три последних элемента и сам выталкивает старые с другого края. Так хранят «последние 100 строк журнала» или «последние десять действий». Где ещё нужна очередь с двумя концами и чем опасен list.pop(0) в цикле, разберём в следующей главе.

Задачи

Четыре задачи: в двух вы построите свои виды, в одной вас ждёт подвох с глубиной, а ещё в одной найденный закон надо вывести точно, до последнего места.

Список полон: n элементов занимают все n мест. Мы делаем append. Напишите функцию grow(n), которая возвращает новую ёмкость — сколько мест станет. Пользоваться sys.getsizeof нельзя, только арифметикой: вы выводите закон, а не измеряете. Тесты сравнят ваш ответ с CPython 3.13 для каждого n от 0 до 3000 и для сотни случайных n до миллиона. Полный список из n элементов даёт [None] * n; на нём можно ставить опыты в отдельной ячейке.

Сначала соберите данные. В отдельной ячейке для нескольких десятков n сделайте a = [None] * n, a.append(None) и напечатайте (sys.getsizeof(a) - 56) // 8. Сравните с n + n // 8: на сколько ответ отличается?

Все ёмкости делятся на 4. Значит, в конце что-то округляется до кратного четырём — вверх или вниз? Попробуйте округлять вниз выражение вида m + m // 8 + c, где m — новая длина, n + 1, а c — небольшая константа.

Округлить вниз до кратного четырём: x // 4 * 4.

В исходном коде CPython (файл Objects/listobject.c, функция list_resize) эта формула записана так: new_allocated = ((size_t)newsize + (newsize >> 3) + 6) & ~(size_t)3. Сдвиг >> 3 — это деление нацело на 8, а & ~3 обнуляет два младших бита, то есть округляет вниз до кратного четырём; о битах и масках — в главе 28. Рядом в исходнике стоит комментарий с последовательностью, которую мы измерили: 0, 4, 8, 16, 24, 32, 40, 52, 64, 76…

Напишите класс DynArray — динамический массив, как у CPython. Элементы храните в атрибуте data — списке постоянной длины, который играет роль блока памяти: создайте его как [None] * capacity и не меняйте его длину (никаких append, insert, pop на нём). Когда места не хватает — создайте блок побольше и перенесите элементы. Нужны:

• DynArray() — пустой массив; атрибут capacity — сколько мест в блоке (равен len(data));
• append(x) — дописать в конец, амортизированно за $O(1)$;
• pop() — убрать последний и вернуть его; у пустого — IndexError;
• arr[i] и len(arr) — методы __getitem__ и __len__; для i вне 0…len-1 — IndexError.

Тесты дописывают 200 000 элементов и следят, чтобы на каждый элемент пришлось не больше десяти переносов.

Переезд: new = [None] * new_capacity, потом цикл, который копирует self.data[i] в new[i] для всех занятых i, потом self.data = new и self.capacity = new_capacity.

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

В pop не забудьте записать None в освободившуюся ячейку: иначе массив будет держать ярлык на объект, который ему больше не принадлежит, и память не освободится.

Список Python умеет и сжиматься: если после pop занято меньше половины мест, CPython просит у системы блок поменьше. Сжиматься ровно при половине нельзя: тогда чередование append и pop на границе вызывало бы переезд на каждом шаге. Подумайте, почему.

Напишите класс LinkedList на узлах Node (класс узла уже в заготовке). Методы:

• push_front(x) и push_back(x) — добавить в начало и в конец, оба за $O(1)$;
• pop_front() — убрать первый и вернуть его значение; у пустого — IndexError;
• len(lst) — за $O(1)$, то есть без прохода по узлам;
• to_list() — обычный список значений от головы к хвосту.

Тесты добавляют сто тысяч элементов в конец и сто тысяч раз спрашивают длину — с ограничением по времени.

Заготовка правильная, но медленная в двух местах: push_back и __len__ проходят всю цепочку. Что можно хранить в объекте, чтобы не ходить?

Храните self.tail — ссылку на последний узел — и self.size. Каждая операция должна их поддерживать. Особые случаи: добавление в пустой список (голова и хвост — один узел) и удаление последнего узла (хвост снова None).

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

Напишите функцию reverse(head), которая разворачивает связный список на месте и возвращает новую голову: из 1 → 2 → 3 получается 3 → 2 → 1. Новых узлов не создавайте — переставьте стрелки у старых. Пустой список — это None. Тесты проверят и цепочку из двухсот тысяч узлов.

Заготовка верна и коротка, но на длинной цепочке упадёт. Вспомните главу 9: какая у этой рекурсии глубина?

Идите по цепочке циклом, держа две ссылки: prev — голова уже развёрнутой части (сначала None) и cur — первый ещё не развёрнутый узел. На каждом шаге развернуть надо одну стрелку — у cur. Попробуйте кнопку «развернуть» в конструкторе выше.

Прежде чем переставить cur.next, сохраните его: nxt = cur.next. Иначе остаток цепочки потеряется.

Один проход, три ссылки, $O(n)$ времени и $O(1)$ дополнительной памяти. Рекурсивная версия тоже $O(n)$ по времени, но держит в стеке вызовов $n$ кадров и на двухстах тысячах узлов упирается в предел глубины. Эта задача — постоянная гостья собеседований: она проверяет, умеет ли человек не потерять кусок цепочки, переставляя стрелки.

Куда дальше

Дописать в конец списка и забрать с конца стоит $O(1)$, с начала — $O(n)$. Если трогать только конец, список становится готовым хранилищем для вещей, которые нужны в обратном порядке: что положили последним, то и достанем первым. Такой порядок встречается чаще, чем кажется. Кнопка «Назад» в браузере возвращает на последнюю открытую страницу. Ctrl+Z отменяет последнее действие, потом предпоследнее. Функции из главы 9 возвращаются в обратном порядке вызовов. Что это за структура, почему на ней работал первый научный карманный калькулятор, у которого не было кнопки «=», и как с её помощью научить программу понимать скобки — в следующей главе.