C++ эффективная и компактная карта с целыми ключами

Question

У меня есть 200 наборов из примерно 50000 уникальных целых чисел в диапазоне от 0 до 500 000. Мне нужно сопоставить другое небольшое значение (пара значений ints, значения не связаны, поэтому нет вычисления по требованию).

Я попытался использовать std :: unordered_maps, и это использовалось около 50 МБ (измерено в инструменте диагностики кучи VS2015), и, хотя производительность была прекрасной, Id хотел бы использовать это использование памяти (намереваясь быть фоновым сервисом на некоторых небольших 500MB облачных серверов).

Фактически моя первоначальная версия была 200 отдельно std::unordered_map<int, std::pair<int, int>>.

Один из вариантов, похоже, является отсортированным массивом и использует двоичный поиск, но есть ли что-нибудь еще?

Answer 1

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

Если вам нужна еще лучшая производительность и не против какой-либо сторонней библиотеки. Вы можете попробовать sparse_hash_map, которые реализуют хэш-карту с очень небольшим объемом служебных данных.

Answer 2

Я думаю, что наиболее эффективным с точки зрения памяти будет std::vector<std::pair<int, std::set<Something>>>, как вы уже сказали.

В этом случае, вы будете иметь только накладные расходы памяти в результате:

• Фиксированный погона станд :: вектор (очень ограниченный)
• иногда выше использования памяти во время «растут» как старые данные и новый должен быть живым в тот момент
• неиспользуемое пространство в станд :: вектор

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

Если у вас было бы более плотное использование, вы можете рассмотреть возможность изменения хранилища до std::vector<std::set<Something>> или std::vector<std::unique_ptr<std::set<Something>>>. В этой структуре индекс неявный, хотя прирост памяти будет отображаться только в том случае, если бы у вас было значение для каждого индекса.

Недостаток использования вектора заключается в том, что вам нужно написать какой-то пользовательский код. В этом случае std::unordered_map и std::map не так уж плох, если вы не возражаете против пропусков кеша в кэшах процессора (L1 ...) для менее стандартных реализаций, можно проверить Googles sparsehash, Googles cpp-btree или Facebooks AtomicHashMap from Folly, хотя я не знаю, У меня есть опыт.

Наконец, можно задаться вопросом, почему у вас есть эти данные в памяти, хотя я не вижу способа предотвратить это, если вам нужна оптимальная производительность.

Answer 3

Для эффективного хранения в зависимости от точного диапазона значений вы можете использовать битовые операции для хранения пар ключ/значение в одном значении: например, если значения действительно малы, вы можете использовать 24bit для ключи и 8 бит для значений, в результате чего одна 32-битная запись. Я считаю, что большинство компиляторов в настоящее время используют 32 или 64-битные выравнивания, поэтому для хранения, например, 32-битных ключей и 16-битных значений, может потребоваться 64-битная запись. Использование простого сжатия также может быть полезно для производительности, если узким местом является шина памяти и пропуски кеша, а не сам процессор.

Тогда это зависит от вида операций, которые вы хотели бы выполнить. Самый простой способ сохранить ключи - это отсортированный массив структур или объединенная запись ley/value, предложенная выше. Это быстро и очень эффективно, но требует поиска O (log n).

Если вы хотите быть немного более причудливым, вы можете использовать perfect hashing, идея состоит в том, чтобы найти хэш-функцию, которая генерирует уникальные значения хэша для каждой клавиши. Это позволяет хэш-карте быть простым массивом, который должен быть только немного больше, чем отсортированный массив, который я предложил выше. Поиск хорошей хэш-функции должен быть относительно быстрым, вы можете сделать это еще проще, сделав массив немного большим и позволяя использовать некоторые неиспользуемые поля в массиве. Here - это реализация идеального хэширования, но я не использовал его сам.

В обоих случаях потребление памяти будет: (количество пар) * (бит на запись) бит, а также сохранение хеш-функции при использовании второго подхода.

** EDIT **

Обновленный после комментария от @FireLancer. Кроме того, добавлено несколько слов о производительности сжатых массивов.