Какая сортировка k-слиянием будет более эффективной при внешней сортировке

Я работаю над проблемой, в которой у меня есть 80GB данных, которые мне нужно отсортировать. У меня есть только 1GB оперативной памяти для сортировки данных. Очевидно, здесь мы применим метод внешней сортировки. Но мой вопрос в том, какая сортировка k-слияния будет более эффективной?

  • 8-стороннее слияние, за которым следует 10-стороннее слияние
  • 5-стороннее слияние, за которым следует 16-стороннее слияние

Сложность сортировки K-слиянием равна O(nk^2), где n — количество элементов. Предположим, я использую этот метод для вычисления сложности:

8-стороннее слияние, за которым следует 10-стороннее слияние

8 way merge - O(n*8^2) => O(64n)
10 way merge - O(8n*10^2) => O(800n)

Total time complexity => O(64n) + O(800n)

5-стороннее слияние, за которым следует 16-стороннее слияние

5 way merge - O(n*5^2) => O(25n)
16 way merge - O(5n*16^2) => O(1280n)

Total time complexity => O(25n) + O(1280n)

Глядя на временную сложность 5 way merge followed by 16 way merge, кажется, требуется больше времени. Как вы думаете, мой процесс правильный? Я не очень уверен в этом.

введите здесь описание изображения

ОБНОВЛЕНИЕ: @rcgldr Поскольку вы говорите, что больший размер блока займет меньше времени для чтения/записи, так что вы думаете об этой формуле:

Time to read/write  1 block = Average Seek time + 
Average rotational latency + blocksize/Maximum Transfer Rate

Согласно этой формуле, если размер блока небольшой, общее время чтения/записи также будет меньше. Как вы думаете, здесь что-то не так? или нам нужно умножить общее количество блоков вместе с этим, чтобы получить точную картину общего требуемого времени.


merge sorting algorithm computer-science external-sorting
person python    schedule 07.12.2015    source источник

Ответы (1)


arrow_upward
2
arrow_downward

Это внешняя сортировка, поэтому обычная временная сложность не применяется, по крайней мере, в реальном случае.

Чтобы пояснить первое утверждение, k-стороннее слияние (не сортировка слиянием) в памяти (не во внешней) объединяет k массивов размера n, поэтому перемещается k n данных, а в простой версии выполняется k-1 сравнений для каждого двигаться, поэтому (k n) (k-1) = n k ^ 2 - n k => O (n k ^ 2). Если куча/приоритетная очередь/... используется для отслеживания текущего набора минимальных элементов, то количество сравнений уменьшается до log2(k), поэтому O(n k log2(k)).

k-ходовая сортировка слиянием n элементов в памяти занимает ⌈logk(n)⌉ == ceil(logk(n)) проходов, перемещая n элементов на каждом проходе, поэтому n ⌈logk(n)⌉. Использование кучи/приоритетной очереди/... для реализации сравнения k элементов требует ⌊log2(k)⌋ == floor(log2(k)), поэтому (n ⌈logk(n)⌉ ) (⌊log2(k)⌋ ). Если n — степень числа k, а k — степень числа 2, то сложность равна n logk(n) log2(k) = n log2(n). k не имеет значения для сложности, но фактическое время выполнения может быть лучше или хуже, k > 2 означает больше сравнений, но меньше перемещений, поэтому проблема заключается в накладных расходах на сравнение и на выполнение, таких как сортировка массива указателей на объекты.

Вернемся к внешней сортировке, предполагая, что процесс связан с вводом-выводом, тогда сложность связана с вводом-выводом, а не с операциями процессора.

Оба метода потребуют 3 прохода для чтения/записи 80 ГБ данных. Первый проход создает 80 экземпляров кластеров по 1 ГБ. Следующий проход объединяет 5 или 8 кластеров за раз, а последний проход объединяет 16 или 10 кластеров за раз. Основная проблема заключается в одновременном чтении или записи больших блоков данных для уменьшения накладных расходов на произвольный доступ. Слияние с 16 способами разбивает 1 ГБ памяти на более мелкие фрагменты, чем слияние с 10 способами, что может немного повлиять на накладные расходы на произвольный доступ, поэтому метод 8/10 может быть немного быстрее. Если для внешней сортировки используется твердотельный накопитель, то произвольный доступ/размер фрагмента гораздо менее проблематичен.

Другая проблема заключается в том, работает ли 10- или 16-канальное слияние в памяти достаточно быстро, чтобы процесс слияния был привязан к вводу-выводу.

person rcgldr    schedule 07.12.2015
comment
Если я просто использую одну 8 сортировку слиянием для внешней сортировки по сравнению с двухфазной 8/10 сортировкой слиянием для внешней сортировки. Не могли бы вы сказать мне, какая разница будет во времени работы? - person python; 07.12.2015
comment
Не могли бы вы немного описать, почему 2 phase merge sort более эффективен? Я читаю об этом в википедии, но не могу понять. - person python; 07.12.2015
comment
@python - сортировка слиянием 5/16 или 8/10 будет трехфазной сортировкой слияния. Сортировка слиянием с 80 способами будет состоять из 2 фаз, но, как уже упоминалось, сравните размеры служебных данных и буфера достаточно малы, чтобы 8/10 могли быть быстрее. - person rcgldr; 07.12.2015
comment
Не могли бы вы увидеть мое редактирование, я обновил вопрос там. Это будет последний вопрос? :) Не могли бы вы ответить на это! - person python; 07.12.2015