Сортировка данных больше, чем размер оперативной памяти

Question

Это вопрос интервью Google: по двум машинам, каждый из которых имеет 64 ГБ оперативной памяти и содержит все целые числа (8 байт), сортирует все 128 ГБ данных.Вы можете предположить небольшой объем дополнительной оперативной памяти.Расширьте это, чтобы отсортировать данные, хранящиеся на 1000 машинах.

Я придумал внешнюю сортировку.При этом мы делим все данные на куски и используем сортировку слиянием на них.Это первое, что нужно отсортировать куски и положить их обратно, получить их снова по частям и объединить их.Есть ли способ лучше?В чем будет сложность?

Answer 1

ChingPing предлагает O (n log n) сортировку для каждого подмножества с последующим линейным слиянием (путем замены элементов). Проблема с быстрой сортировкой (и большей частью из n n n сортировок) заключается в том, что им требуется n памяти. Я бы рекомендовал вместо этого использовать SmoothSort , который использует постоянную память, все еще работает в O (n log n).

В худшем случае у вас есть что-то вроде:

setA = [maxInt .. 1]
setB = [0..minInt]

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

(ИМО - более понятное) объяснение решения ChingPing:

Have a pointers 'pointerA', 'pointerB' initialized at the beginning of each array
While setA's pointer is not at the end
  if (setA[pointerA] < setB[pointerB])
    then { pointerA++; }
    else { swap(setA[pointerA], setB[pointerB]); pointerB++; }

Теперь оба набора должны быть отсортированы.

Answer 2

Уже есть ответы для случая с двумя машинами.

Я предполагаю, что 128 ГБ данных для сортировки хранятся в виде одного файла на одном жестком диске (или любом внешнем устройстве).Независимо от того, сколько машин или жестких дисков используется, время, необходимое для чтения исходного файла объемом 128 ГБ и записи отсортированного файла объемом 128 ГБ, остается неизменным.Единственная экономия происходит во время внутренних сортировок на основе оперативной памяти для создания фрагментов отсортированных данных.Время, необходимое для слияния с n + 1 жесткими дисками, чтобы выполнить n-способ слияния в один отсортированный файл 128 ГБ на оставшийся жесткий диск, снова остается тем же, ограниченным временем, необходимым для записи отсортированного файла 128 ГБ на этот оставшийсяжесткий диск.

Для n машин данные будут разбиты на куски 128 ГБ / n.Каждая из машин может чередовать субчастоты чтения, возможно, по 64 МБ за раз, чтобы уменьшить издержки произвольного доступа, так что «последняя» машина не ждет, пока все предыдущие машины прочитают все свои блоки, прежде чем она даже запустится.

Для n машин (по 64 ГБ оперативной памяти каждый) и n + 1 жестких дисков с n> = 4 радикальная сортировка с O (n) сложностью по времени может использоваться каждой машиной для создания блоков размером 32 ГБ или меньше.n работающих жестких дисков одновременно с последующим n-way слиянием с целевым жестким диском.

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

Answer 3

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

использует ту же концепцию для сортировки всех N RAM. Возьмите их пары и сортируйте, используя метод выше. Вы остались с N / 2 отсортированных ОЗУ. Используйте ту же концепцию выше рекурсивно.