Память эффективная std :: map альтернатива

Question

Я использую std::map для хранения около 20 миллионов записей. Если они были сохранены без каких-либо накладных расходов на контейнер, это займет примерно 650 МБ памяти. Однако, поскольку они хранятся с использованием std::map, он использует примерно 15 ГБ памяти (т. Е. Слишком много).

Причина, по которой я использую std::map, заключается в том, что мне нужно найти ключи, которые равны/больше/меньше, чем x. Вот почему что-то вроде sparsehash не будет работать (поскольку, используя это, я не могу найти ключи по сравнению).

Есть ли альтернатива использованию std::map (или упорядоченных карт в целом), что приведет к меньшему использованию памяти?

EDIT: Производительность записи много более важно, чем чтение. Вероятно, он будет читать только ~ 10 записей, но я не знаю, какие записи он будет читать.

Answer 1

Выбрала номер не былоstd::map.

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

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

Фиксация этой части, теперь она использует < 1 ГБ памяти, как и должно быть! :)

---

TL; ДР:std::map «ы накладные расходы полностью пренебречь для этого. Проблема была моей.

Answer 2

Одним из вариантов было бы использовать flat_map из Boost.Containers: что поддерживает тот же интерфейс, как std::map, но поддерживается отсортированный массив прилежащей (думаю std::vector) вместо дерева. Или вручную создайте собственное решение, основанное на той же идее.

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

Answer 3

Учитывая ваши требования:

1. вставки должна быть быстрой
2. Есть много элементов для чтения
3. обратного чтения может быть медленным
4. Вы только выгружены данные после

Я бы рассмотрел typedef std::pair<uint64, thirty_six_byte_struct> element; и заполнил std::list<element>. Это будет сложно превзойти по производительности.

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

Answer 4

Вы пишете «на лету» или один раз до того, как поиск выполнен? Если это так, вам не нужна карта, вы можете использовать std::vector и одноразовый сорт.

Вы можете просто вставить все несортированное в вектор, отсортировать одноразовое после того, как все там (O (N * log N), а также std::map, но гораздо лучшие характеристики производительности), а затем поиск в отсортированном массиве (O (logN) в качестве std::map).

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