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

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

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

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

Да, стандарт C++ имеет очень специфические требования о том, когда объекты уничтожаются (в § 12.4/10), и в этом случае он не должен быть уничтожен до тех пор, пока не завершится выполнение всего другого кода в блоке.

Разрушение в C++ является детерминированным - означает, что компилятор не может свободно перемещать этот код. (Конечно, оптимизация может встроить деструктор, определить, что код деструктора не взаимодействует с //More code и выполнить некоторое изменение порядка команд, но это другая проблема)

Если вы не могли зависеть от вызова деструкторов, когда они должны быть вызваны, вы не могли использовать RII для захвата блокировок (или только о любой другой конструкции RII для этого вопроса):

{
    LockClass lock(lockData);
    // More code
} // Lock automatically released.

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

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

I Знаете, вы упомянули, не используя базу данных, независимо от того, насколько свет ... Итак, может быть, это не вариант. Но как насчет HSQLDB в памяти ... отправить его, отсортировать его по запросу, очистите его. Просто мысль.

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

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

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

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

2. Отсортируйте N записей в памяти, запишите их в временный файл. Остановитесь на T до тех пор, пока не закончите запись.

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

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

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

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

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

EDITED

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

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

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

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

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

Я бы раскрутил кластер EC2 и запустить Hadoop Mergesort .

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

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

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

Вы можете использовать следующую стратегию Divide-Anquer:

Создать функцию 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 (), очень сильно зависит от характера ваших входных данных. Как только у вас есть эта часть, остальное должно быть ветер.