Более быстрая структура данных, чем unordered_map?

Question

Я ищу структуру данных, которая быстрее, чем Corder's unordered_map в моем сценарии.

Я хранил на карте несортированный уникальный C-String char * (map.first) и целые числа (map.second). Я могу использовать около 10 МБ памяти для этой структуры данных. Прежде чем добавить новый элемент, мне нужно сначала проверить, существует ли он. Итак, я делаю тонну поисков и много вставок. Структура данных будет содержать несколько элементов (< 500), а затем она будет удалена. Поэтому мне не нужно удалять отдельные элементы.

Я реализовал свое собственное самобалансирующееся дерево AVL (кажется, действительно хорошо для моего случая), но оно было на самом деле медленнее по сравнению с std::unordered_map.

Вы знаете какую-либо структуру данных лучше, чем unordered_map в моем случае?

Answer 1

Если память действительно не имеет значения, вы можете создать огромный vector<bool> и сохранить, если данное значение было вставлено в ваше дерево AVL.

например. взгляните на Counting sort. Вы могли бы реализовать его так.

Answer 2

Хорошим ответом на это будет сочетание линейного поиска и двоичного поиска.

В основном есть отсортированный вектор элементов, которые вы можете использовать в двоичном формате. Это будет иметь фантастическую локальность кэша и, вероятно, будет быстрее для тех размеров, на которые вы смотрите. Если вам нужно вставить, просто надавите на отдельный несортированный вектор. Когда вам нужно выполнить поиск, выполните линейный поиск несортированного вектора и двоичный поиск отсортированного вектора. Когда ваш несортированный вектор становится достаточно большим (скажем, 10, но профилирование поможет здесь), вставьте их обратно в отсортированный вектор и приложите его, затем очистите «несортированный» вектор.

Это не гарантия лучшей сложности, но, скорее всего, будет быстрее на современном оборудовании для размеров, которые вы ищете (доступ к линейной памяти - это FAST и, вероятно, бить деревья/списки, пока вы не получите достаточно большой) ,

Сортировка несортированного вектора, а затем объединение его в отсортированный, даст немного увеличения скорости за счет сложности кода.

Answer 3

Похоже, что ваш случай использования требует набора, а не карты. Вам действительно нужна карта, почему-то непонятная в вопросе? Если нет, то unordered_set будет лучшим выбором, и если вы имеете дело с достаточно маленьким диапазоном vector<bool>, как предложил Томас Спарбер.