Как отсортировать ценность на 100 ГБ строк
Учитывая жесткий диск с 120 ГБ, 100 из которых заполнены строками длины 256 и 2 ГБ Ram, как я сортирую те строки в Java наиболее эффективно?Как много времени это займет?
6 ответов
Я в основном повторяю ответ Кристиана , но уточняю:
Да, вам нужно сделать это более или менее на месте , так как у вас мало оперативной памяти. Но наивная сортировка на месте была бы здесь катастрофой только из-за стоимости перемещения струн.
Вместо того, чтобы на самом деле перемещать струны, просто отслеживайте, какие струны должны поменяться местами с какими другими, и фактически переместите их один раз, в конце, на свое последнее место. То есть, если у вас было 1000 строк, сделайте массив из 1000 int. array [i] - это место, где должна закончиться строка i. Если в конце array [17] == 133, это означает, что строка 17 должна закончиться на месте строки 133. array [i] == i для начала всех i. Таким образом, обмен строк - это всего лишь вопрос замены двух целых чисел.
Тогда любой алгоритм на месте, например быстрая сортировка, работает довольно хорошо.
В продолжительности звучания, безусловно, преобладает последнее движение струн. Предполагая, что каждый из них перемещается, вы перемещаете около 100 ГБ данных при записи разумного размера. Я могу предположить, что диск / контроллер / ОС могут перемещаться за вас со скоростью около 100 МБ / с. Итак, 1000 секунд или около того? 20 минут?
А в памяти ли помещается? У вас есть 100 ГБ строк, каждая из которых имеет размер 256 байт. Сколько струн? 100 * 2 ^ 30/2 ^ 8, или около 419 млн строк. Вам нужно 419M int, каждый по 4 байта, или около 1,7 ГБ. Вуаля, умещается в твоих 2ГБ.
A1. Вы, вероятно, захотите реализовать некоторую форму сортировки слиянием .
A2: Дольше, чем если бы на вашем компьютере было 256 ГБ ОЗУ.
Правка: уязвленный критикой, я цитирую статью в Википедии о сортировке слиянием:
Сортировка слиянием настолько последовательна по своей сути, что практично запускать ее, используя медленные ленточные накопители в качестве устройств ввода и вывода. Для этого требуется очень мало памяти, и требуемая память не зависит от количества элементов данных.
По той же причине это также полезно для сортировки данных на диске, который слишком велик, чтобы полностью поместиться в первичную память. На ленточных накопителях, которые могут работать как в прямом, так и в обратном направлении, проходы слияния могут выполняться в обоих направлениях , избегая времени перемотки назад.
Похоже на задачу, которая требует метода внешней сортировки . Том 3 книги «Искусство программирования» содержит раздел, в котором подробно обсуждаются методы внешней сортировки.
Вы должны использовать дерево (также известное как префиксное дерево ): для построения древовидной структуры, которая позволяет вам легко перемещаться по вашим строкам в упорядоченном виде, сравнивая их префиксы. Фактически, вам не нужно хранить его в памяти. Вы можете построить дерево в виде дерева каталогов в вашей файловой системе (очевидно, не той, из которой поступают данные).
Вот как бы я это сделал:
Фаза 1 - разделить 100Gb на 50 разделов по 2Gb, прочитать каждый из 50 разделов в память, отсортировать с помощью quicksort и выписать. Отсортированные разделы должны находиться в верхней части диска.
Фаза 2 заключается в объединении 50 отсортированных разделов. Это самый сложный момент, потому что у вас недостаточно места на диске для хранения разделов и конечного отсортированного результата. Поэтому ...
Выполните слияние 50 разделов, чтобы заполнить первые 20 Гб в нижней части диска.
Переместите оставшиеся данные в 50 разделах наверх, чтобы освободить еще 20 Гб свободного пространства, примыкающего к концу первых 20 Гб.
Повторяйте шаги 1. и 2. до завершения.
Это делает много дисковых операций ввода-вывода, но вы можете использовать 2 Гб памяти для буферизации на этапах копирования и объединения, чтобы получить пропускную способность данных за счет минимизации количества обращений к диску, и делать большие передачи данных.
EDIT - @meriton предложил умный способ уменьшить копирование. Вместо скольжения он предлагает сортировать разделы в обратном порядке и читать их в обратном направлении на этапе слияния. Это позволит алгоритму освободить дисковое пространство, используемое разделами (фаза 2, шаг 2), просто усекая файлы разделов.
Потенциальными недостатками этого являются увеличение фрагментации диска и потеря производительности из-за чтения разделов в обратном направлении. (В последнем случае чтение файла в обратном направлении в Linux / UNIX требует больше системных вызовов, а реализация FS может быть не в состоянии выполнять "чтение с опережением" в обратном направлении.)
Наконец, я хотел бы отметить, что любые теоретические предсказания времени, затрачиваемого этим алгоритмом (и другими), в значительной степени являются догадками. Поведение этих алгоритмов на реальной JVM + реальной ОС + реальных дисках просто слишком сложно, чтобы расчеты "с обратной стороны конверта" могли дать надежные ответы. Для правильного лечения потребуется реальная реализация, настройка и сравнительный анализ.
AFAIK, сортировка слиянием требует столько свободного места, сколько у вас есть данных. Это может быть требованием для любой внешней сортировки, исключающей произвольный доступ, хотя я в этом не уверен.