Какой контейнер выбрать для поиска по ключу для разных размеров?

Question

[Dyikot]

Недавно наткнулся на видео C++Now 2018 You Can Do Better than std unordered_map. Хотя его целью было создание более быстрой версии стандартного unordered_map, но меня заинтересовали его графики приведенные в начале. В них автор сравнивание различные контейнеры при различном числе элементов.



И исходя из них я могу сделать примерный вывод лучше поиск по целочисленному ключу:
1) Линейный поиск в vector (до 20 элементов)
2) Бинарный поиск в map/flat_map ( с 20 до 300 элементов)
3) Поиск использую hash функцию в unordered_map (с 300 элементов)
Могу предположить что если тип ключа более сложный то unordered_map начнет доминировать раньше. Сейчас я использую unordered_map, но для контейнеров которые будут изменятся редко, небольшого размера и использующие простой ключ - size_t хотелось бы оптимизировать скорость и память.
Насколько эти графики выглядят правдимыми? Просто после этого я решил протестировать контейнеры для небольших размеров - vector + линеный поиск и unordered_map для 10, 25 и 50 элементов. И у меня получается unordered_map во всех случаех лучше. Думаю может я что-то не правильно протестировал?

Release
size   vector	unordered_map
10	10ns	6ns
25	13ns	6ns
50	19ns	6ns

Что по вашему опыту лучше для небольших контейнеров и простым типом ключа?

Comments

[rPman]

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

p.s. самая простая рабочая лошадка unordered map

Тупой пример не использовать эти решения - если ваш ключ принимает значения по порядку (типа 0,1,2,... или 100,101,102,... пусть и с незначительными пропусками) и нет поиска по значению, то самое эффективное решение - статичный массив самих значений, где ключом является индекс. Если есть пропуски (или требуется удаление элементов, т.е. нужно понятие not exists) то либо вводить техническое значение для элемента либо заводить еще массив битовый/булевый.

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

[Алексей 〒.]

глянь Swiss Tables
https://abseil.io/blog/20180927-swisstables

[Евгений Шатунов]

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

По одному предложению, расскажи внутреннее устройство и опиши структуру данных у std::vector, std::list, std::deque, std::map и std::unordered_map.

[Dyikot]

Евгений Шатунов, Интересный опрос. Про deque не скажу, т.к не пользовался. vector динамический массив, память непрерывна, произвольный доступ. list по сути представлет собой несколько структур пусть называются они node, в которой указатели на следующий и предыдущий и значение. map вроде схожа на лист(в плане тоже есть node) только они предсталены в виде дерева и в нем производится двоичный поиск. unordered_map особо не вникал как что там. Но вроде представлется вектор листов? по крайнер мере стандратная реализация. Гланое что я передаю ключ он хешируется через std hash и я получаю нужное мне значение.

Из стандартных пользуюсь только vector, unordered_map, queue, редко stack. Ну и сделал отдельно SortedVector.

[Евгений Шатунов]

Dyikot, я не задаю вопросы просто так. Твои ответы позволяют мне понять твою подготовку и видеть где у тебя пробелы.

list по сути представлет собой несколько структур пусть называются они node, в которой указатели на следующий и предыдущий и значение.

Структура данных называется: Двусвязный список. А std::forward_list - это односвязный список.

map вроде схожа на лист(в плане тоже есть node) только они предсталены в виде дерева и в нем производится двоичный поиск

std::map реализует структуру данных: Бинарное дерево. Чаще всего реализуют в виде RB-дерева.
В деревьях нет бинарного поиска. Бинарный поиск выполняется только на отсортированных данных в линейном контейнере (векторе, да). Поиск в бинарном дереве выполняется методом прохода в глубину по критерию. Отсюда и берется аппроксимация трудоемкости поиска.
std::set реализуется тем же способом, но не хранит данные. Это просто дерево ключей.

unordered_map особо не вникал как что там. Но вроде представлется вектор листов? по крайнер мере стандратная реализация. Гланое что я передаю ключ он хешируется через std hash и я получаю нужное мне значение.

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

std::deque реализует т.н. разреженный или постраничный массив. Или - Двусвязную очередь. Структура данных в основе: двусвязный список. Элементами списка являются массивы одинаковой длины. Такая организация позволяет манипулировать блоками элементов вместо цельного куска, как в векторе, и добиваться лучшей производительности на вставке, удалении и добавлении элементов по концам деки.
И смотри внимательно, std::queue и std::stack - это адаптеры, а не контейнеры. А подлежащим по умолчанию в них является именно std::deque.
Т.е. ты пользуешься std::deque как бы не беря это во внимание.

А тут я продолжу. Хэш-таблицы обычно организуются как вот такие списки массивов списков или массивы массивов списков. Аппроксимация трудоемкости поиска O(1) достигается тем, что доступ элемента по индексу-хэшу константен при правильно выбранной хэш-функции, которая редко приводит к коллизиям, из-за чего списки не глубже того самого одного элемента.
Однако, трудоемкость хэш-функции при этом не учитывается, а ведь именно трудоемкость хэш-функции оказывает наибольший эффект на время поиска элемента в хэш-таблице.
Плюсом ложится организация хэш-талицы. Это - дополнительные расходы.

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

[Dyikot]

Евгений Шатунов, По ответу rPman я решил одну задачу перенести с unordered map на vector, где ключ индекс а другие оставить как есть. Но опять же когда какие использывать знаю. Тут был вопрос на сколько правдивы эти графики просто. Просто я всегда считал что хеш таблица должна быть быстрее находить по ключу на любом числе данных, не думая о кеше и после этого видео возникли сомнения. Ведь у меня много небольших unordered_map. Очевидно где мне нужно будет производить не только поиск но и итерировать контейнер, либо мне нужны сортированные данные тогда я просто возьму тот же map или flat_map.