C ++ Сортировка огромных двоичных файлов

Question

Мне нужно отсортировать огромные двоичные файлы, которые не помещаются в память. Невозможно использовать алгоритм сортировки и постоянно читать / записывать с устройства ввода-вывода. Есть ли возможность использовать что-то вроде файла с отображенной памятью?

Answer 1

Это решенная проблема, как объяснено на этой вики-странице: http://en.wikipedia.org/wiki/External_sorting

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

ОБНОВЛЕНИЕ :

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

http://www.codeodor.com/index.cfm/2007/5/10/Sorting-really-BIG-files/1194

Answer 2

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

Answer 3

Использование отображенного в память файла должно работать. Он должен уместиться в вашем адресном пространстве (~ 2 ГБ на 32-битной) или LOTS (если 64-битной).

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

Answer 4

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

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