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

Question

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

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

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

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

Спасибо.

Answer 1

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

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 2

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

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

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

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

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

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

Answer 3

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

Answer 4

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

Answer 5

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

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

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

Настоящий, как MSSQL Express, или MySql или Oracle XE (все являются бесплатными).

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

Answer 6

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

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

Answer 7

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

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

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

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

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

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

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

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

Answer 8

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

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

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

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

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

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

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

Answer 9

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

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

Answer 10

Если вы решите использовать базу данных, вам может быть лучше подан инструмент типа dbm, например Berkeley DB for .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.

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