Файл, загруженный в память, имеет гораздо больший размер, чем размер его диска? !! Любой способ сжать?

Question

У меня сейчас тяжелая проблема. У меня большой файл словаря для загрузки в моей программе, его формат в основном:

word1 val1
word2 val2
word3 val3
...
...

Этот файл имеет 170 тыс. Строк, а его размер составляет 3,9 МБ на диске (в виде простого текста). В моей реализации я использовал boost :: unordered_map (hashtable), чтобы хранить эти данные для поддержки операций поиска только для чтения в моей программе.

Тем не менее, после загрузки в память во время выполнения, использование памяти увеличилось на 20 МБ из-за операции загрузки (я проверил это с помощью Размер частного рабочего набора в диспетчере задач Windows, может быть, это не правильный способ определения использования памяти?). Я знаю, что в хеш-таблице должны быть некоторые вспомогательные структуры данных для хранения этих данных, которые увеличат использование памяти, но я не ожидал, что объем памяти будет в 5 раз больше, чем размер диска !

Это нормально? Поскольку я попробовал другую версию hashmap в библиотеке расширений std и структуру Trie в какой-то другой памяти, ни одна из них не принесла существенного улучшения в этом вопросе.

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

Answer 1

Структура данных карты хеш-памяти выделяет намного больше памяти, чем она использует за один раз.Это должно облегчить быстрые вставки и удаления.Когда хэш-таблица достигает определенной емкости (реализация определена, но ее число, например, заполнено на 50%, заполнено на 70%, заполнено на 90% и т. Д.), Она перераспределяет больше памяти и копирует все.Дело в том, что он выделяет больше памяти, чем используется.

Кроме того, 20 МБ, которые вы видите в программе, - это размер всей памяти, которую использует ваша программа, а не только одна хэш-карта.

Кроме того, если вы используете std::string или эквивалентную структуру для хранения значения, вы уже создали копию половины данных, которые вы получаете из файла.У вас будет одна копия в буфере, в который вы читаете файл, а затем еще одна копия в string s в хэш-таблице.

Answer 2

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