Эффективность хеш-карты в C ++ stdext - реорганизация (?)

Question

Я столкнулся с довольно странной вещью, связанной с хэш-картой stdext. Мне приходится работать со многими объектами, и приоритет - быстрый доступ к элементам. Моя программа считывает значения объекта из файла и, если это новый элемент, затем вставляет это значение в hashmap, если это уже обработанный объект, то изменяет сохраненное значение в hashmap.

Моя проблема связана с hashmap(stdext). Я не нашел никакой опции инициализации для этого контейнера.

Ключевым элементом является целое число без знака (uint64), и этот объект сохраняется в хэш-карте с этим ключом, размером 160 КБ.
Программа работает, но мне приходится слишком долго ждать, когда количество объектов в hashmap достигает предела.

После этого hashmap снова работает хорошо, как я и ожидал. Я подумал, может быть, это реорганизация шаг.

Но эти шаги очень важны, потому что после определенного количества объектов этот шаг занимает 5 часов, в то время как обычный шаг обработки составляет около 2-3 минут. После этого обработка становится «нормальной».

Кто-нибудь сталкивался с такими проблемами? Кто-нибудь знает что-то более глубокое об этой хэш-карте? Я не нашел ничего релевантного по этой теме.

---

Я пытаюсь использовать параметры hashmap со значениями не по умолчанию: bucket_size и min_buckets. Значения по умолчанию для этого bucket_size=4 и min_buckets=8. Я изменил их в файле xhash на большие значения, потому что мне не удалось изменить эти значения из кода. Я думаю, что min_buckets имеет решающее значение в моем приложении, я пытаюсь "настроить", чтобы получить лучшую производительность, избегая шага реорганизации.

Но у меня возникает другая проблема, все работает нормально, пока я не попытаюсь очистить hashmap. Это занимает много времени. Когда я использую его со значениями по умолчанию, работает очень быстро.

Был ли это плохой шаг для изменения файла xhash? Кто-нибудь использовал значения не по умолчанию раньше? Каковы причины этого медленного прояснения?

Мой второй вопрос связан с хранением указателей в hashmap. Идея ясна, но как мне удалось освободить остроконечную память. Я должен создать указатели на мои объекты; эти указатели хранятся в hashmap, и когда мне нужно значение, оно может разыменовать этот указатель. Но как я мог очистить память после того, как я сохранил карту? Может быть, это тривиальный вопрос, но сейчас я не вижу решения.

Спасибо за ваши уже опубликованные ответы.

Answer 1

Копирование вашего объекта, вероятно, очень дорого (учитывая его размер). Попробуйте сохранить указатель на объект вместо всего объекта или boost :: shared_ptr, если вы хотите сделать удаление простым.

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

Answer 2

Использовать Java. Вы будете шокированы порядком, в котором он превосходит C ++, когда дело доходит до эффективных вставок хэш-карт (более качественные распределители, без копирования) и сопоставляет их при поиске.

Answer 3

Ваша проблема в перераспределении (и копировании) или коллизии хешей.

Векторы страдают от этого слишком сильно (и имеют экспоненциально увеличивающийся размер выделения). Тем не менее, карты, наборы и хэш-карты, как правило, менее подвержены влиянию. Эти последние классы не имеют члена resize () в большинстве случаев. Таким образом,

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

При желании вы можете проверить в своей реализации hashmap, следят ли они за ходом-идиомы. Если они не сделают это.

Answer 4

Звучит так, как будто вы пострадали от стоимости копирования ваших объектов, когда контейнер решает выделить место для большего количества объектов. Два самых простых варианта:

1. Если вы знаете количество объектов, которые вы будете вставлять с помощью функции void resize(size_type n).

2. Вы можете хранить указатели в контейнере, а не на самих объектах.