Сортировка огромного количества целых чисел с жесткого диска

Question

Учитывая 100 ГБ целочисленных данных на жестком диске с оперативной памятью объемом 2 ГБ, как отсортировать целые числа с минимальными операциями на диске. Здесь выбор одного номера с диска рассматривается как одна операция на диске (хотя в действительности блок данных может быть выбран).

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

Answer 1

Как заметили другие люди, вы можете использовать счетную сортировку O (n) .Однако есть некоторые дополнительные проблемы, которые вы должны рассмотреть.Предположим, что вы храните 32-битные целые числа, поэтому 100GB ~ ​​27e9 дюймов.

Если все целые числа одинаковы, то это произойдет ~ 27e9 раз, что больше, чем 32-битное int.Следовательно, ваши счетчики должны быть 64-разрядными целыми числами.

С 2 ГБ ОЗУ вы можете одновременно хранить в памяти только ~ 125e6 счетчиков.Если мы не можем делать какие-либо предположения о распределении целых чисел, мы должны либо:

• индивидуально увеличивать счетчики на HD, либо
• игнорировать все встречающиеся целые числа,находятся не в массиве счетчиков, который мы сейчас храним в ОЗУ.

Я думаю, что последний вариант лучше.Поскольку нам нужны 64e-битные счетчики ~ 4e9 и мы можем хранить только 2 ГБ, нам нужно будет пройти через весь массив ~ 16 раз.Первый вариант явно не годится, если мы рассмотрим последовательность целых чисел, например 0,1 << 31,0.Эти счетчики не будут храниться в ОЗУ одновременно, и поэтому требуется как минимум 2 записи HD. </p>

Из-за этого, я думаю, для конкретного размера вашей проблемы (100 ГБ), N-way merge сортировка будет лучше, так как для этого потребуется только чтение всего массива log_2 (100) ~ 8 раз.

Однако, если интервьюер немедленно изменил вопрос на "массив 10TB, все равно2 ГБ ОЗУ ", тогда счетчик легко выиграет.

Answer 2

Поскольку сортируемые данные имеют целочисленный тип (4 байта), а объем данных составляет 100 ГБ (где ГБ 2 ^ 30), у вас будет 26 843 545 600 целых чисел для сортировки. Поскольку у вас есть 4 294 967 296 возможных целочисленных значений, вы можете представить эти данные в виде массива длин, которые служат счетчиками, которые занимают около 34 ГБ дискового пространства. Прочитайте 100 ГБ данных один раз, увеличивая отдельные счетчики для каждого возможного целочисленного значения (общий доступ к диску 300 ГБ, чтобы прочитать значение, прочитать счетчик, записать увеличенный счетчик), затем прочитать счетчики по порядку, записав число значений, которые вы читаете для каждого значения (общий доступ к диску 134 ГБ).

Это позволит отсортировать данные, используя всего 434 ГБ доступа к диску. Если вы используете ОЗУ для хранения части диапазона счетчиков целочисленных значений, технически вы можете еще больше уменьшить доступ к диску.

Answer 3

Для меня ответ на этот вопрос кардинально зависит от ожидаемого распределения чисел в файле.

В 100 гигабайтах данных int содержится 12,5 млрд. Int.Также существует всего ~ 4,3 миллиарда различных целых.

При абсолютно равномерном распределении по всем возможным целым числам вы должны ожидать, что каждое целое число будет отображаться примерно в 3 раза больше или меньше.Этот низкий уровень дублирования не гарантирует изменения по сравнению со стандартной подпрограммой сортировки (той, которая сортирует порции за раз, а затем объединяет порции вместе).

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

Answer 4

Я думаю, что для быстрого алгоритма необходимо еще 100 ГБ свободного места на жестком диске.

Просто используйте любой вид на куски 2 ГБ и поместите их обратно.Теперь у вас есть 50 отсортированных фрагментов в файле, и вы можете использовать сортировку слиянием, как предложено Михиром.Запишите выходной буфер, как он заполняет выходной файл.Вам просто нужно точно настроить размеры входного и выходного буфера.

Есть несколько решений с подсчетом.Его нельзя использовать на таком большом диапазоне и максимально возможном количестве.Вы можете хранить только счетчики QWORD на диске, но это означает много случайных обращений, которые, безусловно, будут медленнее, чем работа с большими буферами.

Answer 5

100 ГБ целочисленных данных означает, что у вас будет большое количество дублированных данных. Я лично выбрал бы подход (bucketsort / selection) / mergesort в качестве своего первого инстинкта, если я пытаюсь минимизировать дисковый ввод-вывод.

Сначала прочитайте немного меньше 1 Гб данных в память, объедините эти данные в памяти. Флеш на диск. Повторите для каждого куска памяти. Затем вы можете пройти каждый кусок данных и захватить все 0, повторить для каждого целого числа. Это займет много времени, но это только 203 ГБ для чтения и 200 ГБ для записи в худшем случае (теоретически).

Answer 6

Merge Sort - это популярный подход, когда речь идет об ограниченной памяти