Как отсортировать файл с очень длинным списком элементов?

Question

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

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

Спасибо, Мохаммад

Answer 1

Вам нужно будет прочитать о внешней сортировке . Основной подход заключается в использовании некоторой подпрограммы «разделяй и властвуй», такой как сортировка слиянием , где вы читаете и сортируете часть файла, затем читаете и сортируете другую часть файла и т. Д., И когда Вы получаете до конца, вы объединяете отсортированные части вместе.

Answer 2

Может быть, поможет STXXL (Стандартная библиотека шаблонов для очень больших наборов данных).

STXXL предлагает внешнюю сортировку среди прочих.

Answer 3

Если вы используете некую Unix-подобную ОС, вы можете использовать команду sort.Он позаботится о потреблении памяти.Например, что-то вроде «cat large_file | sort» сделает эту работу.

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

Answer 4

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

vector<int> linesProcessed;
for (int i = 0; i < lineCount; i++)
{
   if (linesProcessed contains i) continue;
   string alphabeticalFirstLine;
   int lineIndex;
   foreach line in oldFile
   {
       if (line is before alphabeticalFirstLine)
       {
            alphabeticalFirstLine = line;
            lineIndex = i;
       }
   }
   write alphabeticalFirstLine to newFile;
   vector.add(lineIndex);
}
clear vector;
delete oldFile;
rename newFile to oldFile;