0/7. Целая прорва связных списков, чтобы выучить Rust: Введение

Возникли какие-то сложности или хотите сразу получить весь финальный код? Всё на Github!

ПРИМЕЧАНИЕ: Текущая редакция этой книги написана для Rust 2018, выпущенного совместно с rustc 1.31 (8 декабря 2018). Если у вас достаточно новый инструментарий Rust, файл Carto.toml, созданный при запуске cargo new, будет содержать строку edition = "2018" (или, если вы из далёкого будущего, большее число!). Можно использовать старый инструментарий, но тогда вы разблокируете секретный режим повышенной сложности: больше ошибок от компилятора, совершенно не упомянутых в этой книге. Как по мне, звучит весело!

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

В этом цикле я научу вас и базовому, и продвинутому программированию на Rust, с помощью реализации 6 связных списков. За время изучения вы освоите:

• Следующие типы указателей: &, &mut, Box, Rc, Arc, *const, *mut, NonNull(?)

• Владение, заимствование, наследуемую изменчивость, внутреннюю изменчивость, типаж Copy

• Все ключевые слова: struct, enum, fn, pub, impl, use, …

• Сопоставление с образцом, обобщения, деструкторы

• Тестирование, установку новых инструментов, использование miri

• Небезопасный Rust: сырые указатели, псевдонимы, многоуровневые заимствования, вариантность

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

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

1. Неправильный односвязный стек

2. Правильный односвязный стек

3. Устойчивый односвязный стек

4. Неправильный, но безопасный двусвязный дек

5. Правильная небезопасная односвязная очередь

6. Небезопасный двусвязный дек для прода

7. Куча странных списков

Чтобы мы понимали друг друга, я буду писать здесь все команды, которые ввожу в терминал. Также, для разработки проекта, я использую стандартный растовский пакетный менеджер Cargo. Писать программы на Rust можно и без Cargo, но с ним намного удобнее, чем с rustc. Если вам захочется поэкспериментировать, простые программы можно запускать в браузере через play.rust-lang.org.

В следующих разделах мы будем использовать rustup для установки дополнительных инструментов Rust. Я настоятельно рекомендую устанавливать весь инструментарий Rust, используя rustup.

Давайте начнём и создадим наш проект:

cargo new --lib listscd lists

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

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

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

Мы будем двигаться достаточно медленно, и я на 100% не собираюсь всё это время быть серьёзной. Я, блин, думаю, что программирование должно быть весёлым! Если вы — читатель, которому нужен максимально информативный, серьёзный и формальный текст, эта книга не для вас. Вообще всё, что я когда-либо напишу — не для вас. Читайте другие книги.

Обязательное Общественное Обращение

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

• Вам надо много раз сливать и разделять большие списки. Много раз.

• Вы пишите какую-то удивительную неблокирующую конкурентную штуку.

• Вы пишите системную/низкоуровневую штуку и вам нужны интрузивные списки.

• Вы пишите на чистом функциональном языке, где ограниченная семантика вкупе с неизменяемостью делают связные списки простейшим решением.

• …ну и так далее!

Но у всех, кто пишет на Rust, эти задачи встречаются супер редко. В 99% случаев вы должны просто использовать Vec (массив-стек), а в 99% из оставшегося 1% — VecDeque (массив-дек). Это безусловно лучшие структуры данных для большинства рабочих задач из-за нечастых выделений, небольшой служебной памяти, честного произвольного доступа и локальности кэша.

Связные списки — такая же нишевая и расплывчатая структура данных, как и префиксное дерево. Мало кто станет возражать против моего утверждения, что префиксное дерево — нишевая структура, с которой средний программист, к счастью, никогда в своей жизни не столкнётся. В то же время, у связных списков какая-то необъяснимая популярность. Каждого студента мы учим, как писать связные списки. Это единственная нишевая коллекция, которую я не смогла удалить из std::collections. И в стандартной библиотеке C++ связный список тоже есть!

Мы, как сообщество, должны сказать нет связным спискам как «стандартной» структуре данных. Это — прекрасная структура данных, для которой есть несколько прекрасных сценариев использования, но эти сценарии — исключения, а не правила.

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

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

Производительность не всегда имеет значение

Да! Скажем, ваше приложение занимается в основном вводом и выводом. Или его запускают пару раз в год и время его работы действительно не имеет значения. Но это не аргумент в пользу связного списка. Это аргумент в пользу чего угодно. Зачем ограничиваться связным списком? Используйте связный ассоциативный массив!

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

У списков разделение-добавление-вставка-удаление выполняются за O(1), если есть указатель на нужный узел

Точняк! Хотя, как заметил Бьёрн Страуструп, на самом деле это неважно, поскольку получение указателя на нужный узел занимает гигантское время по сравнению с простым копированием элементов массива (что на практике довольно быстро).

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

Но — да, если профилирование показало, что приложение тратит всё время на слияние и разделение, вы получите выгоду от связных списков.

Я не могу позволить себе амортизированную сложность

Вы — уже в достаточно узкой нише, поскольку большинство программистов могут позволить себе амортизированную сложность. Даже для массивов амортизированная сложность — это худший случай, а не основной. Если вы знаете максимальное количество элементов (верхнюю границу), можно зарезервировать столько памяти, сколько вам надо. По моему опыту, количество элементов известно достаточно часто. Скажем, итераторы Rust как раз для этого предоставляют метод size_hint.

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

Как вам такая скорость?

Но — да, если вы не можете предсказать количество элементов, связные списки работают быстро даже в худшем случае!

Связные списки занимают меньше места

Ну, это сложно. «Стандартная» стратегия при изменении размера массива — следить, чтобы при увеличении или уменьшении, по меньшей мере половина массива оставалась пустой. При этом действительно уходит много места. Особенно в Rust, где мы не уплотняем коллекции автоматически (что оправданно, если вы собираетесь заполнять их снова), так что потери могут стремиться к бесконечности!

Но это худший случай. В лучшем случае массив-стек имеет всего три дополнительных указателя. Считайте, никаких накладных расходов.

С другой стороны, связные списки гарантированно требуют места для каждого элемент. Служебные данные в односвязном списке — это один указатель, а в двусвязном — два. В отличие от массивов, относительные расходы у списков обратно пропорциональны размеру элементов. Если элементы огромные, накладные расходы близки к 0. Если элементы крошечные (скажем, байты), служебные данные в 16 раз превышают размер самих элементов (в 8 — на 32-хбитных машинах)!

А, если учесть выравнивание по размеру указателя  — в 23 раза (в 11 за 32-хбитные машинах).

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

Но — да, если у вас огромные элементы, вы не можете предсказать их количество и фрагментация не очень высокая — можно добиться экономии памяти!

Я всё время использую связные списки в «функциональных языках»

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

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

В Rust подобные вещи делаются с помощью итераторов. Они могут быть бесконечными. Над ними можно выполнять операции map, filter, reverse и concatenate, как и над обычными функциональными списками. Помимо прочего, они ещё и ленивые!

Наконец, Rust облегчает работу с под-массивами с помощью срезов. В функциональных языках списки обычно делят на голову и хвост, точно также, как это делает slice.split_at_mut(1). На протяжении долгого времени в Rust существовала крутая экспериментальная система сопоставления с образцом для срезов. Во время стабилизации её всё-таки упростили, но даже сейчас образцы для срезов весьма изящны! Кстати, срезы легко превратить в итераторы!

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

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

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

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

Да! Хотя создание потокобезопасных структур данных совершенно из другой оперы, и к нему нельзя относиться легкомысленно. Однозначно, в теме разбираются не так много людей. И как только они разработают для вас готовую структуру, вы больше не будете выбирать связный список. Вы будете выбирать MPSC-очередь или что-то такое. А для этого очереди стратегия реализации очень сильно отличается!

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

Тык-пык ядро, встраиваемые системы, туда-сюда интрузивные

Это — ниши. Вы говорите о ситуациях, в которых нельзя использовать даже стандартную библиотеку. Разве это не красный флаг, что вы делаете что-то очень необычное?

Плюс ко всему, всё это крайне небезопасно.

Но — ладно. Пишите свои потрясающие списки без выделения памяти в куче.

Итераторы могут работать после вставки/удаления элементов

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

Но — да, с помощью курсоров можно делать действительно крутые и безумные штуки.

Они простые и хорошо подходят для обучения!

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

Сделайте вдох

Что ж. С этим разобрались. Давайте теперь напишем хреналлиард связных списков.

Вперёд, к первой главе!