Как отсортировать строки на 100 ГБ

Question

При наличии жесткого диска с 120 ГБ, 100 из которых заполнены строками длиной 256 и 2 ГБ. Ram. Как наиболее эффективно отсортировать эти строки в Java?Сколько времени это займет?

Answer 1

A1. Вы, вероятно, хотите реализовать некоторую форму merge-sort .

A2: дольше, чем если бы на вашем компьютере было 256 ГБ ОЗУ.

Редактировать: обиженный критикой, я цитирую статью из Википедии о сортировке слиянием:

Сортировка слиянием настолько последовательна, что ее целесообразно использовать с медленными ленточными накопителями в качестве устройств ввода и вывода. Это требует очень мало памяти, а требуемая память не зависит от количества элементов данных.

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

Answer 2

Вот как я это сделаю:

Фаза 1 состоит в том, чтобы разделить 100Gb на 50 разделов по 2Gb, прочитать каждый из 50 разделов в память, отсортировать с помощью быстрой сортировки и выписать. Вы хотите отсортированные разделы в верхней части диска.

Этап 2 состоит в объединении 50 отсортированных разделов. Это сложный бит, потому что на диске недостаточно места для хранения разделов и окончательного отсортированного вывода. Итак ...

1. Выполните 50-полосное слияние, чтобы заполнить первые 20 ГБ в нижней части диска.

2. Сдвиньте оставшиеся данные в 50 разделах вверх, чтобы еще 20 ГБ свободного пространства были смежными с концом первых 20 ГБ.

3. Повторите шаги 1. и 2. до завершения.

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

EDIT - @meriton предложил умный способ уменьшить количество копий. Вместо скольжения он предлагает сортировать разделы в обратном порядке и читать в обратном порядке в фазе объединения. Это позволило бы алгоритму освободить дисковое пространство, используемое разделами (фаза 2, шаг 2), просто обрезая файлы разделов.

Потенциальными недостатками этого являются повышенная фрагментация диска и потеря производительности из-за чтения разделов в обратном направлении. (В последнем случае для чтения файла в обратном направлении в Linux / UNIX требуется больше системных вызовов, и реализация FS может быть не в состоянии выполнить «чтение вперед» в обратном направлении.)

Наконец, я хотел бы отметить, что любые теоретические предсказания времени, затраченного этим алгоритмом (и другими), в значительной степени являются догадками. Поведение этих алгоритмов на реальной JVM + реальной ОС + реальных дисках слишком сложное, чтобы расчеты «обратно в конверт» не давали надежных ответов. Правильная обработка потребует фактической реализации, настройки и тестирования.

Answer 3

Я в основном повторяю ответ Кристиана , но уточняю:

Да, вам нужно делать это более или менее на месте, поскольку у вас мало доступной оперативной памяти. Но наивные сортировки на месте были бы катастрофой только из-за стоимости перемещения строк.

Вместо того, чтобы на самом деле перемещать строки, просто следите за тем, какие строки должны поменяться местами с другими, и фактически переместите их, один раз в конце, к их конечному месту. То есть, если у вас было 1000 строк, создайте массив из 1000 дюймов. массив [i] - это место, где должна заканчиваться строка i. Если массив [17] == 133 в конце, это означает, что строка 17 должна заканчиваться на месте для строки 133. массив [i] == i для всех i, чтобы начать. Таким образом, обмен строк - это всего лишь обмен двух строк.

Тогда любой алгоритм на месте, такой как быстрая сортировка, работает очень хорошо.

Время исполнения, безусловно, определяется окончательным ходом струн. Предполагая, что каждый из них перемещается, вы перемещаете около 100 ГБ данных в записях разумного размера. Я мог бы предположить, что диск / контроллер / ОС может двигаться со скоростью около 100 МБ / с для вас. Итак, 1000 секунд или около того? 20 минут?

Но это умещается в памяти? У вас есть 100 ГБ строк, каждая из которых составляет 256 байтов. Сколько строк? 100 * 2 ^ 30/2 ^ 8 или около 419 миллионов строк. Вам нужно 419 МБ, каждый по 4 байта или около 1,7 ГБ. Вуаля, умещается в ваших 2 ГБ.

Answer 4

Похоже на задачу, которая вызывает Внешнюю сортировку метод.Том 3 «Искусство компьютерного программирования» содержит раздел с подробным обсуждением методов внешней сортировки.

Answer 5

Я думаю, что вы должны использовать BogoSort. Возможно, вам придется немного изменить алгоритм, чтобы обеспечить сортировку на месте, но это не должно быть слишком сложно. :)

Answer 6

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

Answer 7

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