Сортировка очень большого текстового файла в Java

Question

У меня большой текстовый файл, который мне нужно отсортировать на Java. Формат:

слово [табуляция] частота [новая строка]

Алгоритм сортировки:

• Чтение некоторых файлов с фильтрацией по буквам букв алфавита.
• Если у вас есть X буквенных слов, вызовите Collections.sort и запишите результат в файл.
• Повторяйте, пока не закончите чтение файла.
• Начните читать два отсортированных файла, сравнивая строку за строкой для слова с более высокой частотой, и одновременно записывая в новый файл, чтобы не загружать много в вашу память
• Повторяйте, пока все файлы не будут объединены в один большой файл

Прямо сейчас я разделил большой файл на более мелкие (отсортированные по убыванию частоты) по 10000 строк в каждой. Я знаю, что мне нужно как-то объединить эти файлы, но я не знаю, как это сделать.

Я создал LinkedList для отслеживания всех созданных файлов. Алгоритм говорит, что нужно сравнивать каждую строку в двух файлах, за исключением того, что я пробовал случай, когда, скажем, file1 = 8,6,5,3,1 и file2 = 9,8,8,8,8. Тогда, если я сравниваю их построчно, я получаю file3 = 9,8,8,6,8,5,8,3,8,1, который неправильно отсортирован (они должны быть в порядке убывания).

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

изменить: Да, это назначение. К сожалению, нам нельзя увеличивать память: (

Answer 1

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

Итак, все довольно просто:

Для начала прочитайте строку из каждого файла.
Затем повторите это:
.Строка с наибольшим значением записывается в новый файл
.Прочитать еще одну строку из этого файла

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

Answer 2

Если файл слишком велик для размещения в памяти, используйте базу данных. Что-то вроде MySQL может быть слишком тяжелым, но есть встраиваемые базы данных, которые вы можете использовать в Java.

Один из них - berkely DB , который представляет собой систему базы данных ключ / значение.

Apache Derby - это система реляционных баз данных, которая позволяет использовать SQL.

Если вы уже знаете SQL, возможно, дерби - самый простой способ. Я не использовал это сам.