Сегодня я выступил с докладом на offline-части конференции C++ Russia 2023. Тема доклада — «Что-то у меня тормозит: заглядываем внутрь стандартных контейнеров». Это доклад из рубрики «Назад к основам», поэтому он нацелен на то, чтобы осветить вещи, которые разработчикам и так должны быть известны.
Изначально я хотел собрать материалы «Алгоритмического фундамента программиста» и «Поясов по C++» и осветить особенности внутреннего устройства
std::vector, std::deque и ̀std::unordered_map, которые влияют на скорость и корректность работы программы. Однако в процессе подготовки мне пришло осознание ряда вещей, и именно им я уделил внимание в своём докладе.
Во-первых, я детально разобрал в докладе, что такое асимптотика O(1), амортизированное O(1) и O(1) в среднем. Моя центральная идея состоит в том, что «асимптотика O(1) означает, что время работы операции не зависит от размера входных данных». Такая операция может длиться сколько угодно долго. Важно только то, зависит это время от размера входных данных или нет.
Например, добавление элемента в связный список имеет асимптотику O(1), потому что оно выполняется за одно и то же время, независимо от того, сколько элементов есть в списке: ноль, десять или миллион. А вот
std::vector::push_back работает за O(1), когда в нём есть свободное место, и за O(N) — когда приходится выделять буфер большего размера. То есть в общем случае это не O(1), потому что время работы зависит от количества элементов в векторе (std::vector::push_back работает за амортизированное O(1), но это уже совсем другая история).Второй вопрос, который я разбирал в докладе, был про то, как получается, что хеш-таблица, основанная на цепочках, выполняет поиск за O(1) в среднем и O(N) в худшем случае? Что значит "в среднем" и какой случай является худшим?
Поиск в хеш-таблице работает за длину цепочки. Чем больше элементов в таблице, тем длиннее её цепочки и тем дольше будет работать поиск. А значит, время работы поиска зависит от количества элементов в хеш-таблице, а следовательно, — это не O(1). Но ведь в документации сказано, что всё-таки O(1)! Как же так получается? Всё дело в параметре
load factor, который задаёт отношение количества элементов в таблице к количеству бакетов. По сути load factor определяет среднюю длину цепочек в хеш-таблице. Когда load factor становится слишком большим, в хеш-таблице выполняется рехеширование — количество бакетов увеличивается минимум вдвое, и элементы перераспределяются по ним, уменьшая load factor и среднюю длину цепочек. Таким образом, неважно, сколько элементов в нашей хеш-таблице, средняя длина цепочек в ней (а следовательно, и среднее время поиска в хеш-таблице) всегда находится в одном и том же диапазоне. То есть среднее время поиска в хеш-таблице не зависит от количества данных в ней, а значит имеет асимптотику O(1) в среднем.Мораль этой истории в том, что я с 2000-го года связан с программированием, я был на двух финалах ACM ICPC и сделал алгоритмический курс — казалось бы, я уже ничего нового не могу открыть для себя в стандартных структурах данных. Но подготовка этого, на первый взгляд, простого доклада позволила мне достичь гораздо более глубокого понимания того, как работает структура данных, которой мы пользуемся ежедневно. Так что я и правда сам понял, пока объяснял 😉
P.S. Теперь у меня есть повод перенести эти мысли в мой «Алгоритмический фундамент программиста», сделав его ещё полезнее и проще для понимания.
