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

Question

Баллов:

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

Не могу сделать:

• Мы не можем использовать команды сортировки unix / linux.
• Мы не можем использовать какую-либо систему баз данных, независимо от того, насколько легкими они могут быть.

Теперь мы не можем просто загрузить все в коллекцию и использовать механизм сортировки. Он съест всю память, и программа получит кучу ошибок.

В этой ситуации, как бы вы отсортировали записи / строки в файле?

Answer 1

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

По сути, сначала вы сортируете небольшие порции данных, записываете их обратно на диск, а затем перебираете их, чтобы отсортировать все.

Answer 2

Несмотря на ваши ограничения, я бы использовал встроенную базу данных 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

Answer 3

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

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

Answer 4

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

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

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

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

Answer 5

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

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

2. Сортировка N записей в памяти, запись их во временный файл. Зацикливайтесь на T, пока не закончите.

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

---

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

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

---

Пример с номерами:

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

---

EDITED

Вы упомянули многопоточное приложение, так что мне интересно ...

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

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

---

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

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

Answer 6

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

Создайте функцию 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

Теперь вы можете отсортировать каждый отдельный файл.Что поменяет местами «Джон Доу» и «Джонни Кэш» в,Теперь, если вы просто объедините эти 3 файла, у вас будет отсортированная версия ввода.

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

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

Answer 7

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

Answer 8

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

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

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

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

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

Answer 9

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

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

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

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

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

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

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

Answer 10

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