Сортировка файла с огромным объемом данных с учетом ограничения памяти

Ответ 1

Похоже, что вы ищете внешняя сортировка.

В основном вы сначала сортируете мелкие куски данных, записываете их обратно на диск и затем перебираете их для сортировки.

Ответ 2

Вы можете читать файлы в меньших частях, сортировать их и записывать во временные файлы. Затем вы снова читаете два из них и объединяете их с большим временным файлом и так далее. Если осталось только один, вы можете отсортировать свой файл. В основном, алгоритм Megresort выполняется для внешних файлов. Он хорошо масштабируется с большими большими файлами, но вызывает некоторые дополнительные операции ввода/вывода.

Изменить: если у вас есть некоторые сведения о вероятной дисперсии строк в ваших файлах, вы можете использовать более эффективный алгоритм (сортировка распределения). Упрощенный, вы должны прочитать исходный файл один раз и записать каждую строку во временный файл, который берет только строки с тем же самым первым char (или определенным диапазоном первых символов). Затем вы перебираете все (теперь маленькие) временные файлы в порядке возрастания, сортируете их в памяти и добавляете их непосредственно в выходной файл. Если временный файл оказывается слишком большим для сортировки в памяти, вы можете повторно использовать тот же процесс для этого на основе 2-го char в строках и так далее. Поэтому, если ваше первое разбиение было достаточно хорошим для создания достаточно небольших файлов, у вас будет только 100% -ная нагрузка ввода-вывода, независимо от того, насколько велик файл, но в худшем случае он может стать намного больше, чем с устойчивой стабильной сортировкой слияния.

Ответ 3

Несмотря на ваши ограничения, я бы использовал встроенную базу данных SQLITE3. Как и я, я работаю еженедельно с 10-15 миллионами плоских файловых строк, и очень быстро импортировать и генерировать отсортированные данные, и вам нужно всего лишь немного бесплатного исполняемого файла (sqlite3.exe). Например: после загрузки файла .exe в командной строке вы можете сделать это:

C:> sqlite3.exe dbLines.db
sqlite> create table tabLines(line varchar(5000));
sqlite> create index idx1 on tabLines(line);
sqlite> .separator '\r\n'
sqlite> .import 'FileToImport' TabLines

то

sqlite> select * from tabLines order by line;

or save to a file:
sqlite> .output out.txt
sqlite> select * from tabLines order by line;
sqlite> .output stdout

Ответ 4

Я бы развернул кластер EC2 и запустил Hadoop MergeSort.

Изменить: не уверен, сколько деталей вам нужно, или о чем. EC2 - это Amazon Elastic Compute Cloud - он позволяет арендовать виртуальные серверы по часам по низкой цене. Вот их сайт.

Hadoop - это платформа MapReduce с открытым исходным кодом, предназначенная для параллельной обработки больших наборов данных. Работа является хорошим кандидатом для MapReduce, когда его можно разделить на подмножества, которые могут обрабатываться индивидуально, а затем объединяться вместе, обычно путем сортировки по ключам (т.е. Стратегии разделения и покоя). Вот его веб-сайт.

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

Ответ 5

Как уже упоминалось, вы можете обрабатывать пошагово. Я хотел бы объяснить это своими словами (отличается в пункте 3):

• Прочитайте файл последовательно, обрабатывайте N записей за раз в памяти (N произвольно, в зависимости от вашего ограничения памяти и количества T временных файлов, которые вы хотите).

• Сортируйте N записей в памяти, запишите их в файл temp. Петля на T, пока вы не закончите.

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

Преимущества:

• Потребление памяти как можно меньше.
• Вы используете только двойной доступ к диску по сравнению с политикой "все в памяти". Неплохо!: -)

Пример с цифрами:

• Оригинальный файл с 1 миллионом записей.
• Выберите, чтобы иметь 100 файлов temp, поэтому читайте и сортируйте 10 000 записей за раз, и отбрасывайте их в своем собственном временном файле.
• Откройте 100 временных файлов за раз, прочитайте первую запись в памяти.
• Сравните первые записи, напишите меньше и продвиньте этот временный файл.
• Петля на шаге 5, миллион раз.

EDITED

Вы упомянули многопоточное приложение, поэтому я задаюсь вопросом...

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

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

Прочитав этот ответ: Сортировка файла с огромным объемом данных с учетом ограничений памяти Я предлагаю вам рассмотреть этот дистрибутив. Это может быть огромным выигрышем в вашем контексте.

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

Ответ 6

Если ваше ограничение состоит только в том, чтобы не использовать внешнюю систему баз данных, вы можете попробовать встроенную базу данных (например, Apache Derby). Таким образом, вы получаете все преимущества базы данных без каких-либо внешних зависимостей инфраструктуры.

Ответ 7

Вы можете использовать следующую стратегию деления и покорения:

Создайте функцию H(), которая может назначить каждой записи во входном файле число. Для записи r2, которая будет сортироваться за записью r1, она должна вернуть большее число для r2, чем для r1. Используйте эту функцию, чтобы разбить все записи на отдельные файлы, которые будут вписываться в память, чтобы вы могли сортировать их. Как только вы это сделаете, вы можете просто конкатенировать отсортированные файлы, чтобы получить один большой отсортированный файл.

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

Alan Smith
Jon Doe
Bill Murray
Johnny Cash

Давайте просто построим H(), чтобы он использовал первую букву в записи, чтобы вы могли получить до 26 файлов, но в этом примере вы просто получите 3:

<file1>
Alan Smith

<file2>
Bill Murray

<file10>
Jon Doe
Johnny Cash

Теперь вы можете сортировать каждый отдельный файл. Что бы заменить "Джон Доу" и "Джонни Кэш" в <file10 > . Теперь, если вы просто соедините 3 файла, у вас будет отсортированная версия ввода.

Обратите внимание, что вы делите сначала и только побеждаете (сортируете) позже. Тем не менее, вы обязательно выполняете разделение таким образом, чтобы результирующие части, которые вам нужно сортировать, не перекрывались, что упростит объединение результата.

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

Ответ 8

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

Ответ 9

Вы можете использовать файл SQL Lite db, загружать данные в db, а затем разрешать сортировку и возвращать результаты для вас. Преимущества: Не нужно беспокоиться о написании лучшего алгоритма сортировки. Недостаток: вам потребуется дисковое пространство, медленная обработка. https://sites.google.com/site/arjunwebworld/Home/programming/sorting-large-data-files

Ответ 10

Вот способ сделать это без особого использования сортировки в стороне Java и без использования БД. Предположения. У вас есть пространство 1TB, и файлы содержат или начинаются с уникального номера, но не сортируются.

Разделите файлы N раз.

Прочитайте эти N файлов один за другим и создайте один файл для каждой строки/номера

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

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

Теперь у вас есть папка с файлами, отсортированными по их имени, используя счетчик, начинающийся с каждого файла один за другим, поместите числа в ваш файл OUTPUT, закройте его.

Когда вы закончите, у вас будет большой файл со отсортированными числами.

Ответ 11

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

На каждой итерации:

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

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

Максимальное количество итераций: (размер файла)/(размер буфера) * 2

Ответ 12

Если вы можете перемещаться вперед/назад в файле (искать) и переписывать части файла, тогда вы должны использовать тип пузыря.

Вам нужно будет сканировать строки в файле и иметь только 2 строки в памяти на данный момент, а затем поменять их, если они не в правильном порядке. Повторяйте процесс, пока файлы не будут заменены.