Структура данных для эффективного поиска

Question

Я ищу предложение для соответствующей структуры данных для использования в следующем сценарии. У меня есть минимальное и максимальное значения, определенные для ключей, например.

Key          Min Value                Max Value

key1          0 .5                    4.5
key2          1                       9
key3          0.75                    1.5

Я должен разбить каждое значение для дальнейшегоподпакеты, так что разница между минимальным значением и максимальным значением не может превышать 1, и минимальное значение каждого сегмента будет увеличиваться на 0,5.

, например, ключ1 будет ломаться дальше

Key               Bucket   Min Value                Max Value
key1             B1       0.5                      1.5
key1             B2       1                        2
key1             B3       1.5                      2.5
key1             B4       2                        3
key1             B5       2.5                      3.5
key1             B6       3                        4
key1             B7       3.5                      4.5

После того, как я создал эти сегменты (и это только один раз), мне нужно найти подходящие сегменты для заданного ключа и значения.

Например, допустимыми сегментами для ключей 1 и 2.2 являются B3 и B4.

В настоящее время я храню все сегменты в std::map<Key, std::vector<Buckets> >

, где Buckets - это структура, в которой в качестве переменной указаны имя сегмента, min и max.

Какую альтернативу я могу использовать, кроме std::map<Key, std::vector<Buckets> > чтобы ускорить процесс поиска?

Answer 1

Вы можете поместить все записи в std::vector, затем использовать std::map<key, vector-index>.Это называется созданием индексной таблицы.

Для небольших объемов данных линейный поиск не отличается от использования таблиц индекса (на самом деле может быть быстрее).

Поиск в Интернете «первой нормальной формы», чтобы найти способы оптимизации вашегоданные.

Answer 2

Линейный поиск std::vector сам по себе (или std::binary_search, если он отсортирован) хорошо выполняет на современном оборудовании.Непрерывная структура памяти очень удобна для иерархии кеша и предварительной выборки.std::vector обычно побеждает контейнеры, основанные на узлах, которые должны преследовать указатели по всей памяти (даже если что-то вроде BigO скажет вам, что оно потеряет большой объем).Но вы всегда должны оценивать различные решения для вашего конкретного случая использования, чтобы знать наверняка.