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

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

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

Ответ 1

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

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

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

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

(IMO - более четкое) объяснение решения ChingPing:

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

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

Ответ 2

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

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

Ответ 3

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

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

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

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

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