[Перевод] Сверхскоростные связные списки

info@vsetut.pro

Стать автором

Вернуться

05.06.2024 12:35:09 | Хабр

Хабы: Высокая производительность, Программирование, Алгоритмы, Rust

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

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

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

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

От читателя поста ожидается, что он на базовом уровне понимает Rust, обычные структуры данных, а также концептуально представляет, как выделяется память (в стеке и куче).

Дополнение (14.05.2024): Я учёл поступившую обратную связь и подчеркнул, какие идеи объективно плохи, прояснил некоторые отступления и удалил идею о imbl.

Чтобы было проще прослеживать этапы реализации и исследовать код, отсылаю вас к репозиторию, сопровождающему этот пост.

Подробнее