Связный список

Поставьте курсор в самое начало первой части «Войны и мира» и напечатайте букву. Если текст хранится массивом, все 244 500 знаков после курсора сдвинутся на одну ячейку вправо. Если связным списком, новая буква встанет между двумя соседями, и поменяются четыре ссылки. Ниже первая часть первого тома сразу в трёх видах: массив, двусвязный список и буфер с разрывом, на котором держится Emacs. Печатайте, переставляйте курсор, поставьте курсоры после каждого «Пьер» — и смотрите, кто сколько работает.

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

Идея

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

Вся статья — про оговорку «который уже в руках». Если узел нужно сначала найти по номеру или по значению, список проходит O(n) узлов, и его быстрая вставка уже ничего не меняет. Как собрать список из объектов Python, почему его придумали для первой программы искусственного интеллекта и чем он отличается от list и deque, рассказано в главе курса о списках. Здесь — что нужно, чтобы пользоваться им всерьёз: стражи и кольца, честный счёт с массивом и петли.

Четыре ссылки и страж

Вставка буквы перед узлом at, на котором стоит курсор, в двусвязном списке — четыре присваивания. Новый узел получает ссылку назад, на левого соседа, и вперёд, на at; левый сосед теперь смотрит вперёд на новый узел, а at — назад на него. Удаление буквы слева от курсора — два присваивания: соседи стёртого узла начинают смотреть друг на друга, а сам он выпадает из цепочки, хотя ссылки внутри него всё ещё куда-то ведут.

Неприятности начинаются на краях. У первого узла нет левого соседа, у последнего — правого, в пустом списке нет никого, и в каждой операции появляются проверки «а вдруг это начало». Их убирает один пустой узел, который не хранит данных, — страж. Список замыкается через него в кольцо: сосед стража справа — первый узел, слева — последний, в пустом списке страж смотрит сам на себя. Теперь у любого узла всегда есть оба соседа, и вставка в начало ничем не отличается от вставки в середину. Так устроены container/list в Go (в исходнике прямо сказано: внутри список реализован как кольцо, а корневой узел — страж), OrderedDict в той версии, что написана на самом Python (в комментарии сказано, что страж никогда не удаляется и это упрощает алгоритм), и списки ядра Linux.

В редакторе из сцены курсор — ссылка на узел, перед которым он стоит, а курсор перед стражем означает конец текста. Поэтому клавиши «в начало» и «в конец» бесплатны: сосед стража справа и сам страж известны всегда. А вот переход в середину стоит столько шагов, сколько до неё идти.

Где список выигрывает

Условие одно: узел уже в руках, и с ним нужно сделать что-то константное — вставить соседа, вынуть, переставить в другое место.

Много курсоров. Нажмите в сцене «Курсор после каждого „Пьер“» и напечатайте пару букв. Каждая буква вставляется у каждого курсора, и массив на каждой вставке сдвигает весь хвост. В последней правке листинга novel курсоры стоят после всех 36 «князь Василий», и печатается « Курагин»: массив сдвигает 33 864 016 знаков, буфер с разрывом переносит 1 456 970, потому что разрыв на каждой букве объезжает все курсоры, а список переписывает 1152 ссылки — по четыре на каждую из 288 вставленных букв.

Кэш LRU. Кэш ограниченного размера, переполнившись, выбрасывает запись, к которой дольше всех не обращались. Словарь находит запись по ключу за O(1), а двусвязный список держит записи в порядке обращений. При попадании узел вынимают с его места и ставят в конец — четыре ссылки, без всякого поиска, потому что словарь отдаёт сам узел. Так устроен functools.lru_cache в CPython: в его исходнике у каждой записи есть поля prev и next, а попадание вырезает запись и дописывает её перед стражем. Подробно — в статье о кэше LRU.

Кольцо. Когда у последовательности нет ни начала, ни конца, её естественная форма — кольцевой список: очередь задач, которым процессор раздаёт время по кругу, игроки за столом, свободные блоки памяти. Распределитель памяти из книги Кернигана и Ричи «Язык программирования Си» держит свободные блоки именно так — кольцевым списком. В Go для этого есть отдельный пакет container/ring.

Узел внутри объекта. В ядре Linux ссылки prev и next — поле struct list_head внутри самой структуры, например процесса, а не отдельный узел, который на неё указывает. Такой интрузивный список не тратит память на лишние узлы, объект с несколькими такими полями стоит в нескольких списках сразу, а вынуть его из любого можно за O(1), держа в руках только сам объект. Макрос list_entry по адресу поля восстанавливает адрес структуры, в которую оно встроено.

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

Где проигрывает: память и кэш

Каждая ссылка — восемь байт на 64-битной машине. Узел двусвязного списка букв в Go — буква и две ссылки, 24 байта вместо четырёх у элемента []rune и меньше двух в среднем у русского текста в UTF-8. В Python узел со __slots__ занимает 56 байт, к ним добавляется объект самой буквы, и на первой части романа выходит около ста байт на знак.

Хуже памяти — порядок обхода. Процессор читает память строками кэша по 64 байта и умеет заранее подтягивать следующие, если адреса идут подряд. Массив он так и читает. По списку так нельзя: адрес следующего узла становится известен, только когда прочитан текущий. Ниже — сложение n чисел: из среза, из списка, узлы которого выделены подряд, и из того же списка, где связи перемешаны, как после долгой жизни со вставками и удалениями в разных местах.

На Go срез тратит около половины наносекунды на число при любом n. Список с узлами подряд — около полутора: каждый шаг ждёт, пока прочитается предыдущий, но узлы лежат рядом и уже в кэше. Перемешанный список на тысяче узлов почти не отличается от неперемешанного, на десяти тысячах уже вчетверо медленнее, а когда перестаёт помещаться в кэш, каждый шаг становится походом в оперативную память: на двух миллионах узлов 146 наносекунд на число, в двести с лишним раз дольше среза. У Python все три линии выше из-за интерпретатора, но на 300 тысячах перемешанных узлов картина та же: 385 наносекунд против 71 у списка Python.

А теперь честная проверка на любимой операции списка — вставке в середину. Эту задачу Бьярне Страуструп показывал в 2012 году на конференции GoingNative и рассказывает, что придумал её Джон Бентли: вставлять случайные числа так, чтобы последовательность оставалась упорядоченной. Место для числа ищут просмотром с начала и там, и там; дальше массив сдвигает хвост, а список меняет одну ссылку.

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

Код

Редактор из сцены в миниатюре: двусвязный список букв со стражем и курсором и рядом такой же редактор на массиве. Клавиши — как в первой задаче статьи: < и > двигают курсор, [ и ] отправляют его в начало и в конец, # стирает букву слева. Оба редактора получают одни и те же нажатия, а программа печатает текст с курсором, сколько ссылок переписал список и сколько знаков сдвинул массив.

Тире в начале строки массиву обошлось в 62 сдвига: два знака, и каждый сдвинул весь 31 знак текста. Списку — восемь ссылок, по четыре на знак, как и любая другая вставка. В Go для настоящей работы есть готовый container/list с тем же устройством; здесь список написан вручную, чтобы было видно все четыре ссылки.

Теперь первая часть романа целиком, в трёх видах сразу. Программа читает «Войну и мир» с сервера, где исполняется код, вырезает первую часть первого тома и делает четыре правки — те же, что кнопка в сцене.

edit                          array shifts  list hops   links   gap moves
start: Война и мир. Том...       6,112,500          0     100     244,500
end: Конец первой части.                 0          0      76     244,500
first Наташа: + Ростова          1,303,816     81,567      32     162,977
36 x князь Василий: + Курагин   33,864,016          0   1,152   1,456,970
total                           41,280,332     81,567   1,360   2,108,947

Третья строка — слабое место списка: чтобы дописать фамилию Наташе, ему пришлось пройти 81 567 узлов от начала текста. Массив зато сдвинул по 162 977 знаков на каждую из восьми букв. Все эти сдвиги в абсолютных числах недороги: сдвинуть 244 500 знаков []rune в Go — копия мегабайта памяти, около 15 микросекунд на Mac, где проверялись примеры, и человек за клавиатурой этого не заметит. Счёт меняется с файлами в сотни мегабайт и с десятками курсоров: тогда каждое нажатие сдвигает гигабайты.

Петля в цепочке: черепаха и заяц

Список может замкнуться в петлю — по ошибке, когда ссылка указала назад, или потому что так устроены данные. Возьмём генератор «случайных» чисел, который Джон фон Нейман предложил в 1949 году: возвести четырёхзначное число в квадрат, дописать слева нули до восьми цифр и взять средние четыре. 0540 даёт 2916, потом 5030, потом 3009 — и снова 0540. Каждое число однозначно задаёт следующее, то есть последовательность — связный список, где ссылка на следующий узел не хранится, а вычисляется. Чисел конечное число, поэтому цепочка обязательно зациклится. Сначала идёт хвост из μ чисел, которые больше не встретятся, потом бесконечно крутится цикл длины λ, и вся картина похожа на греческую букву ρ.

Найти μ и λ можно, запоминая все числа в словаре, пока какое-нибудь не повторится. Но памяти на это уходит μ + λ ячеек, а если узел — состояние программы в мегабайт, это непозволительно. Алгоритм, который приписывают Роберту Флойду, обходится двумя указателями. Черепаха делает шаг на одно число, заяц — на два.

В сцене рисунок знает форму заранее, а указатели — нет: у них только два числа. Начните с 0156: хвост из восьми чисел, цикл из четырёх, 6100 → 2100 → 4100 → 8100. Число 1234 за 56 шагов скатывается в ноль и остаётся там навсегда: цикл длины один. У восьмизначного 80770865 хвост тянется 16 279 шагов и тоже кончается нулём. Сам фон Нейман знал, что его метод быстро вырождается, и считал это достоинством: вырождение легко заметить. Ему же принадлежит фраза о том, что всякий, кто получает случайные цифры арифметикой, пребывает в состоянии греха.

В 1980 году Ричард Брент предложил вариант быстрее: черепаха стоит на месте и перепрыгивает к зайцу, когда число шагов зайца доходит до очередной степени двойки. По оценке самого Брента, в среднем это примерно на 36 % быстрее метода Флойда. Программа ниже находит μ и λ тремя способами — Флойдом, Брентом и словарём — и считает, сколько раз каждый вычислил формулу.

digits      seed     mu  lam  cycle entry  floyd calls  brent calls  remembered
     4       540      0    4          540           16           11           4
     4      6100      0    4         6100           16           11           4
     4      5546    101    4         4100          518          337         105
     6    857729    689  210       119585         4108         2821         899
     8  80770865  16279    1            0        81396        48943       16280

Словарь вычисляет формулу меньше всех — ровно μ + λ раз, — но держит в памяти все 16 280 чисел. Флойд и Брент считают больше, зато помнят два-три числа при любой длине цепочки. Тот же приём лежит в основе ро-метода Полларда, который раскладывает числа на множители: там петлю ищут в последовательности остатков по модулю делителя, который ещё неизвестен, и запомнить её нельзя в принципе. А с генераторами случайных чисел цикл — первое, что проверяют: длина периода — мера качества, о ней — в статье о генераторах.

Сколько это стоит

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

История

Связный список придумали в 1955–1956 годах Аллен Ньюэлл, Клифф Шоу и Герберт Саймон: на нём держался их язык IPL и написанная на нём программа «Логик-теоретик». Привычная картинка — прямоугольники, соединённые стрелками, — впервые появилась в статье Ньюэлла и Шоу 1957 года «Programming the Logic Theory Machine». Ещё в 1953 году Ханс Петер Лун из IBM предлагал связывать в цепочки записи, которым выпал один номер в хеш-таблице. В 1958 году Джон Маккарти начал Лисп, где список стал главной структурой, а в 1975 году Ньюэлл и Саймон получили премию Тьюринга, и обработка списков названа в её формулировке. Подробно эта история рассказана в главе курса.

Алгоритм черепахи и зайца Дональд Кнут в 1969 году во втором томе «Искусства программирования» приписал Флойду. В опубликованных работах Флойда его нет, так что авторство под вопросом; имя тем не менее прижилось.

Задачи

В первой задаче нужно восстановить документ по журналу нажатий, и известное решение на двух стеках там не успевает: клавиши «в начало» и «в конец» заставляют его перекладывать весь текст. Во второй — найти хвост и цикл генератора фон Неймана для многих начальных чисел.