Как рассчитать время внешней сортировки слиянием?

Question

Исходная проблема такова:
Вы должны отсортировать целые числа размером 1ПБ в диапазоне от -2^31 ~ 2^31 - 1 (int), у вас есть 1024 машины, каждая из которых имеет 1 ТБ дискового пространства и 16 ГБ памяти. Предположим, что скорость диска составляет 128 МБ / с (ч / б), а скорость памяти - 8 ГБ / с (ч / б). Время для процессора можно игнорировать. Время передачи по сети может быть проигнорировано для простоты. Вычислите приблизительное время, необходимое.

Я знаю, что с помощью внешней сортировки мы можем отсортировать данные объемом 1 ТБ на одной машине примерно за 10 часов, как показано ниже:

Доступ к диску (2r2w): 1T * 4 / 128 МБ / с = 2 ^ 15 с ~ 9 часов
Mem access:
сортировка 2^48 целых чисел в 64 частях (2 ^ 42 каждая) примерно занимает 1,3 минуты каждая. Таким образом, всего 1,4 часа.
63 способ слияния занимает несколько секунд и поэтому игнорируется.

Но как насчет следующего шага: комбинация данных 1024T? Я понятия не имею, как это вычисляется. Так что любая помощь, пожалуйста?

Answer 1

2^31 = 2 миллиарда (2 "гига"). Итак, вы смотрите на множество повторяющихся номеров и фиксированный диапазон. Так что рассмотрите Radix Sort ( http://en.wikipedia.org/wiki/Radix_sort).

Каждый процессор (для поднабора данных od) создает массив 'count' (x[0] содержит счетчик 0 и т. Д.). Затем вы можете объединить все результаты в один массив. Позже вы можете "построить" отсортированный массив.