Как правильно подойти к вопросу: какой контейнер выбрать для поиска по ключу для разных размеров?
По вводным: недавно наткнулся на видеоПо вводным: 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Что именно по вашему опыту лучше для небольших контейнеров и простым типом ключа?
Опишите проблему, и специалист поможет с настройкой, исправлением ошибки или доработкой сайта. Подберём понятный план работ без лишней переписки.
Пока нет других ответов. Будьте первым, кто поможет автору.
Ответить на вопрос
Выбор контейнера для поиска по ключу зависит от размера данных, частоты вставок/удалений, требований к порядку и языка. В C# и C++ базовая логика одинаковая: если нужен быстрый поиск по ключу без порядка — hash map; если нужен отсортированный порядок — tree map; если данных мало — иногда простой массив/список быстрее и проще.
Для C#:
Dictionary<TKey,TValue>— быстрый поиск по ключу, среднее O(1);SortedDictionary<TKey,TValue>— отсортированные ключи, O(log n);SortedList<TKey,TValue>— компактно для редко изменяемых данных;List<T>— нормально для маленьких наборов и линейного поиска.Для C++:
std::unordered_map— быстрый hash lookup;std::map— отсортированное дерево;std::vector+ binary search — хорошо для статических отсортированных данных;std::flat_mapв новых/сторонних реализациях — выгодно для cache locality.Если элементов до нескольких десятков, не всегда стоит усложнять: линейный поиск по массиву может быть быстрее из-за кэша и отсутствия накладных расходов. Если элементов тысячи и больше, частый поиск по ключу — берите hash map.
Если данные загружаются один раз и потом только читаются, хороший вариант — отсортированный массив/вектор и binary search. Он компактнее дерева и часто быстрее на практике.
Если ключи пользовательские, обязательно проверьте hash/equality. Плохая реализация
GetHashCodeв C# или hash functor в C++ может убить производительность и привести к странным ошибкам поиска.Итог: по умолчанию берите
Dictionary/unordered_map. Нужен порядок —SortedDictionary/map. Данные маленькие или статические — список/вектор может быть проще и быстрее. Выбор делайте по операциям, а не только по асимптотике.