Чтение большого файла в словарь

Question

У меня есть файл объемом 1 ГБ, содержащий пары строк и long. Каков наилучший способ чтения этого в словаре, и сколько памяти, по вашему мнению, ему требуется?

Файл имеет 62 миллиона строк. Мне удалось прочитать его, используя 5,5 ГБ оперативной памяти.

Скажите 22 байта на каждую словарную запись, это 1,5 ГБ. длина 8 байтов, это 500 МБ. Средняя длина строки составляет 15 символов, каждый символ 2 байта, это 2 ГБ. Всего около 4 ГБ, куда уходят дополнительные 1,5 ГБ?

Первоначальное выделение словаря занимает 256 МБ. Я заметил, что каждые 10 миллионов строк, которые я читаю, занимают около 580 МБ, что очень хорошо согласуется с приведенным выше расчетом, но где-то около 6000-й строки использование памяти увеличивается с 260 МБ до 1,7 ГБ, это мои недостающие 1,5 ГБ, причем идти?

Спасибо.

Answer 1

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

Когда вы создаете новый Hashtable, .NET создает массив, содержащий 11 блоков, которые являются связанными списками словарных статей. Когда вы добавляете запись, ее ключ хэшируется, хэш-код отображается на один из 11 сегментов, а запись (ключ + значение + хэш-код) добавляется в связанный список.

В определенный момент (и это зависит от коэффициента загрузки, используемого при первом создании Hashtable), Hashtable определяет, во время операции Add, что он сталкивается с слишком большим количеством коллизий и что начальных 11 сегментов недостаточно , Таким образом, он создает новый массив сегментов, который в два раза больше старого (не совсем; количество сегментов всегда простое), а затем заполняет новую таблицу из старого.

Итак, есть две вещи, которые вступают в игру с точки зрения использования памяти.

Во-первых, Hashtable время от времени требует вдвое больше памяти, чем он использует в настоящее время, чтобы он мог копировать таблицу во время изменения размера. Так что, если у вас есть Hashtable, который использует 1,8 ГБ памяти и требует изменения размера, вкратце потребуется 3,6 ГБ, и, ну, теперь у вас проблема.

Во-вторых, каждая запись хеш-таблицы имеет около 12 байтов служебной информации: указатели на ключ, значение и следующую запись в списке, а также хеш-код. Для большинства применений эти издержки незначительны, но если вы создаете Hashtable со 100 миллионами записей, то это примерно 1,2 ГБ.

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

Answer 2

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

Существует простой способ решить, какие части лучше хранить в памяти:

Поместить данные в базу данных.

Реальный, такой как MSSQL Express, MySql или Oracle XE (все бесплатны).

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

Answer 3

Может быть, вы можете преобразовать этот 1 ГБ файл в базу данных SQLite с двумя столбцами ключ и значение. Затем создайте индекс по ключевому столбцу. После этого вы можете запросить эту базу данных, чтобы получить значения предоставленных вами ключей.

Answer 4

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

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

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

Это приведет к тому, что наиболее часто используемые материалы будут доступны в памяти, но потребует дополнительной работы при пропадании кеша.

В любом случае, не зная немного больше о проблеме, это всего лишь «общее решение».

Может быть, достаточно хранить его в локальном экземпляре базы данных sql:)

Answer 5

Вам нужно будет указать формат файла, но если это просто что-то вроде name = value, я бы сделал:

Dictionary<string,long> dictionary = new Dictionary<string,long>();
using (TextReader reader = File.OpenText(filename))
{
    string line;
    while ((line = reader.ReadLine()) != null)
    {
        string[] bits = line.Split('=');
        // Error checking would go here
        long value = long.Parse(bits[1]);
        dictionary[bits[0]] = value;
    }
}

Теперь, если это не сработает, нам нужно больше узнать о файле - сколько там строк и т. Д.?

Вы используете 64-битную Windows? (Если нет, вы не сможете использовать более 3 ГБ на процесс, IIRC.)

Объем требуемой памяти будет зависеть от длины строк, количества записей и т. Д.

Answer 6

Можете ли вы преобразовать файл 1G в более эффективный индексированный формат, но оставить его как файл на диске? Затем вы можете получить к нему доступ по мере необходимости и сделать эффективный поиск.

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

Answer 7

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

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

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

Выделите буфер размером с файл. Прочитайте файл в этот буфер.

Затем создайте словарь с длинными значениями (32-битные значения, я полагаю?) В качестве ключей, а их значения также будут 32-битными.

Теперь просмотрите данные в буфере следующим образом: Найдите следующую пару ключ-значение. Вычислить смещение его значения в буфере. Теперь добавьте эту информацию в словарь, указав длину ключа и смещение в качестве значения.

Таким образом, вы получите словарь, который может занимать 10-20 байт на запись, и один больший буфер, содержащий все ваши текстовые данные.

По крайней мере, с C ++, я думаю, это был бы довольно эффективный способ памяти.

Answer 8

Если вы решите использовать базу данных, вам лучше использовать инструмент в стиле dbm, например, Berkeley DB для .NET . Они специально разработаны для представления дисковых хеш-таблиц.

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

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

[key2][value2...][key1][value1..][key3][value3....]

Разделить его на индексный файл и файл значений.

Файл значений:

[value1..][value2...][value3....]

Индексный файл:

[key1][value1-offset]
[key2][value2-offset]
[key3][value3-offset]

Записи в индексном файле представляют собой пары key->value-offset фиксированного размера и упорядочены по ключу. Строки в файле значений также упорядочены по ключу.

Чтобы получить значение для key(N), необходимо выполнить двоичный поиск для key(N) записи в индексе, а затем прочитать строку из файла значений, начиная с value(N)-offset и заканчивая value(N+1)-offset.

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

Answer 9

Не считывайте 1 ГБ файла в память, даже если у вас есть 8 ГБ физической памяти, у вас все еще может быть очень много проблем. на основе личного опыта -

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

Answer 10

Загрузка 1 ГБ файла в память за один раз не кажется мне хорошей идеей. Я бы виртуализировал доступ к файлу, загружая его небольшими блоками, только когда нужен конкретный блок. Конечно, это будет медленнее, чем весь файл в памяти, но 1 ГБ - настоящий мастодонт ...