Блог

Я должен хранить данные, где ключ, целое число, следует шаблону, подобному этому:

1, 2, 4, 5, 60, 61, 63

То есть ключи иногда объединяются в блоки из сотен ключей с небольшим количеством пробелов в них, но между блоками могут быть большие промежутки. Иногда встречаются одиночные ключи или небольшие блоки в середине нигде.

На данный момент std::map используется для хранения ключей, но при профилировании обнаруживается, что требуется время для поиска ключей. Это потому, что нам нужен произвольный доступ к ключам, а ключей тысячи.

Пока максимальный ключ 16-разрядный, поэтому я попытался заменить на std::vector , и он ускорился примерно на 10% в режиме отладки (производительность всей программы). Режим выпуска претерпел незначительные изменения, но мы выполняем много долгой работы в режиме отладки.

Но теперь ключи могут иметь длину до 32 бит, поэтому это невозможно.

Я пытался std::unordered_map , но это дало худшую производительность, чем std::map ! У меня нет большого опыта работы с хэш-картами, поэтому, возможно, я мог бы настроить политику хэширования, но я не знаю как.

Есть предложения по эффективной структуре данных для этой задачи?

Спасибо.

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

Например, ваши ключи варьируются от 0 до 1 000 000, тогда вы будете иметь в первом слое:

 1) all keys from 0 to 99,000
2) from 100,000 to 199,999
3) ...
10) from 900,00 to 1,000,000
 

И поэтому вы переходите к более низким уровням, где вы снова разделяете подгруппы. На самом нижнем уровне у вас есть вектор, содержащий фактически доступные ключи в этой группе. Имея 3 таких слоя, вы можете уменьшить количество проходимых ключей в ~ 1/1000 раз по сравнению с исходным числом. Это значительно сократит время поиска определенного ключа.

Я отвечу вам не со стороны программирования, а со стороны математики.

Может быть, это будет хорошим решением (все зависит от реальных данных, с которыми вам приходится работать) для создания анализатора кучи, который разделит ваши тысячи чисел на сотни куч.

Имейте в виду наименьшее число кучи как «базу кучи». Для каждой кучи вы можете создать вектор указателей на ваши данные, где N элемент будет иметь номер «база кучи» N (таким образом, некоторые указатели будут nullptr , но такие векторы не будут длинными).

И затем вы можете создать карту чисел «базы кучи» (каждое из которых связано со своим вектором кучи). Доступ к N элементу из vector занимает O (1), это должно быть очень быстро. Поиск в map your heap — также будет быстрее, потому что вы будете искать в сотнях куч, а не в тысячах чисел.

Используя «lower_bound», вы сможете найти ближайшую кучу к номеру, который вы ищете, а затем выполнить поиск в этой куче.

Если ваша средняя куча состоит из K чисел, вы увеличите свою скорость как Log (2) K. Для K = 8 — тройное время. Вы потеряете время на поиск и некоторые другие действия, но можете серьезно выиграть в скорости.

Если вам нужно создать это хранилище данных только один раз, а затем работать с ним, это может быть решением.

С числами из вашего примера вы должны получить: (где T — ваши объекты, которые вы ищете)

 vector<T*> a = {obj1, obj2, nullptr, obj4, obj5}
vector<T*> b = {obj60, obj61, nullptr, obj63}
map<int, vector<T*> > mymap;

mymap.append(pair(1, a));
mymap.append(pair(60, b));
 

(где objN равно T *)
, а затем выполните поиск числа, например 63, используя методы bounds . Возьмите вектор и возьмите из него элемент с номером 63 -«базовый» (т.Е. с номером 3)