У меня есть 200 папок с 20 файлами в каждой папке. Общий набор данных - 2gb. Я попытался разобрать все сразу и поместить каждую строку в список и отсортировать их, но я уйду из памяти.Сортировка нескольких файлов в один файл
Какой подход можно использовать для сортировки нескольких файлов в одном файле?
файл на основе merge-sort:
Если вы не хотите выполнять сортировку по 200 путям, вы можете разделить # 3 на несколько типов слияния, а затем объединить сортировку результатов на столько уровней, сколько необходимо.
Обратите внимание, что шаги 2 и 3 не являются слияниями, а просто слияния. В частности, [k-way merge] (https://en.wikipedia.org/wiki/K-Way_Merge_Algorithms). И, действительно, если ваш код может выполнить слияние с 20 путями, он может выполнить 200-way merge. В какой-то момент у вас будет нехватка памяти для буферов, но не в 200. –
@JimMischel Я не верю, что существует требование о том, чтобы слияние было ограничено слияниями двух сторон, хотя это, как правило, имеет место , Концепция слияния двух (или более) отсортированных подмножеств для обработки большего сортированного подмножества и повторения этого процесса до тех пор, пока все данные не будут отсортированы, это именно то, что делает Merge-Sort. Я никогда не говорил, что шаг 2 - это сортировка слияния. Я говорил, что вся последовательность (1-3) является многоуровневой сортировкой с использованием дисков. Конечно, шаг 1 может выполняться в памяти и использовать любой алгоритм сортировки, но общая концепция - это сортировка слияния. – Andreas
Вы неправильно поняли мой комментарий. Я просто говорил, что шаги 2 и 3 не являются технически подобными, а скорее просто сливаются. Поэтому вместо того, чтобы «Объединить сортировку 20 файлов ...», правильнее сказать «Слить 20 файлов ...» Что касается слияний, я никогда не упоминал о двухсторонних слияниях. Это было бы ужасно неэффективно. Наиболее эффективным в этом случае будет выполнение 4000-way merge после сортировки отдельных файлов. Это минимизирует время ввода-вывода. Но разделение его, как вы рекомендовали, имеет практический смысл, если скорость не является наивысшим приоритетом. –
Какой алгоритм сортировки вы используете? Потому что я думаю, что проблема кроется в алгоритме; вам нужно взглянуть на более эффективный алгоритм для сортировки. Я считаю, что для больших входов Merge-Sort является лучшим (хотя и с несколькими модификациями для этого размера).
Here - очень похожий вопрос, посмотрите на два первых ответа. Они должны помочь вам решить проблему.
Простейшее решение; добавьте больше памяти в размер вашей кучи. 8 ГБ не так много. У моего 9-летнего есть старая машина, которая имеет 24 ГБ. –
XML? Джейсон? Простой текст? – efekctive
его текст ссылки – sweep