Как я сортирую файл, который имеет очень длинный список объектов?
У меня есть текстовый файл, который имеет очень длинный список объектов. Таким образом, я хочу отсортировать их в алфавитном порядке, но я не хочу загружать весь файл в память (RAM).
Я пытался загрузить все содержание файла к массиву, и отсортируйте их точно так же, как я обычно делаю. Но система жалуется, что нет никакой большой памяти!!
Спасибо, Mohammad
4 ответа
Вам нужно будет прочитать о внешней сортировке . Базовый подход заключается в использовании какой-то процедуры «разделяй и властвуй», например сортировка слиянием , где вы читаете и сортируете часть файла, затем читаете и сортируете другую часть файла и т. Д. И когда дойдете до конца, вы объедините отсортированные порции вместе.
Возможно, поможет STXXL (стандартная библиотека шаблонов для очень больших наборов данных).
STXXL предлагает, среди прочего, внешнюю сортировку .
Если вы используете какую-то unix-подобную ОС, вы можете использовать команду sort. Это позаботится о потреблении памяти. Например, что-то вроде "cat large_file | sort" подойдет.
Или вы можете написать свою собственную / использовать внешнюю сортировку из библиотеки. Сообщите нам, какой язык вы используете, и, возможно, кто-нибудь подскажет вам, какую библиотеку использовать.
Вам не нужно держать весь файл в памяти. Если это задача, которую вам не придется выполнять очень часто, вы можете написать приложение, которое сортирует его очень медленно. Что-то вроде этого (псевдо):
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;