Сортировка гигантских двоичных файлов с помощью C # - PullRequest
Новая
       46

Сортировка гигантских двоичных файлов с помощью C #

6 голосов
/ 30 сентября 2011

У меня большой файл размером примерно 400 ГБ. Генерируется ежедневно внешней замкнутой системой. Это двоичный файл в следующем формате: 

byte[8]byte[4]byte[n]

Где n равно значению int32 байта [4].

Этот файл не имеет разделителей, и чтобы прочитать весь файл, вы просто повторяете до EOF. Каждый элемент представлен в виде байта [8] байта [4] байта [n].

Файл выглядит как 

byte[8]byte[4]byte[n]byte[8]byte[4]byte[n]...EOF

byte [8] - это 64-разрядное число, представляющее период времени, представленный галочками .NET. Мне нужно отсортировать этот файл, но я не могу найти самый быстрый способ сделать это.

В настоящее время я загружаю тики в структуру, а начальные и конечные позиции байта [n] и читаю до конца файла. После этого я сортирую список в памяти по свойству Ticks, а затем открываю BinaryReader и ищу каждую позицию в порядке тиков, считываю значение байта [n] и записываю во внешний файл.

В конце процесса я получаю отсортированный двоичный файл, но это занимает НАВСЕГДА. Я использую C # .NET и довольно крутой сервер, но кажется, что проблема с дисковым вводом-выводом.

Характеристики сервера:

  • 2x 2,6 ГГц Intel Xeon (Hex-Core с HT) (24 потока)
  • 32 ГБ ОЗУ
  • 500 ГБ RAID 1 + 0
  • 2 ТБ RAID 5

Я просмотрел весь интернет и могу найти только примеры, когда огромный файл размером 1 ГБ (заставляет меня смеяться).

У кого-нибудь есть совет?

Ответы [ 4 ]

7 голосов
/ 30 сентября 2011

Отличный способ ускорить такой доступ к файлу - отобразить в памяти весь файл в адресное пространство и позволить ОС позаботиться о считывании любых битов из файла, в котором она нуждается.Поэтому сделайте то же самое, что и сейчас, за исключением чтения из памяти вместо BinaryReader / seek / read.

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

5 голосов
/ 30 сентября 2011

Использовать сортировку слиянием. Он онлайн и хорошо распараллеливается.

http://en.wikipedia.org/wiki/Merge_sort

3 голосов
/ 30 сентября 2011

Если вы можете выучить Erlang или Go, они могут быть очень мощными и отлично масштабироваться, поскольку у вас есть 24 потока. Используйте асинхронный ввод / вывод. Сортировка слиянием. И поскольку у вас есть 32 ГБ оперативной памяти, попробуйте загрузить столько, сколько вы можете , в ОЗУ и отсортировать его там, а затем записать обратно на диск.

1 голос
/ 17 мая 2016

Я бы сделал это в несколько проходов. На первом проходе я бы создал список тиков, а затем распределил их равномерно по многим (сотням?) Сегментам. Если вы заранее знаете, что тики распределены равномерно, вы можете пропустить этот начальный проход. На втором проходе я разделил бы записи на эти несколько сотен отдельных файлов примерно одинакового размера (эти гораздо меньшие файлы представляют группы галочек в нужном вам порядке). Тогда я бы отсортировал каждый файл отдельно в памяти. Затем объедините файлы.

Это похоже на хэш-сортировку (я думаю).

...