Слияние k отсортированных массивов - Очередь приоритетов против традиционного слияния с сортировкой слиянием, когда и какой использовать?

Question

При условии, что нам даны k отсортированные массивы (каждый размером n), в этом случае приоритетная куча использует лучше, чем традиционное слияние (аналогично тому, которое используется в сортировке слиянием).) и наоборот?

Подход с приоритетной очередью: В этом подходе у нас есть min куча размера k (изначально первый элемент из каждого массива добавляется вкуча).Теперь мы удалим элемент min (из одного из входных массивов), поместим его в окончательный массив и вставим новый элемент из того же входного массива.Этот подход занимает O(kn log k) время и O(kn) пространство.Примечание: он занимает O(kn) пробел, потому что это размер конечного массива, и он доминирует над размером кучи при расчете сложности асимптотического пространства.

Традиционное слияние: В этом подходемы объединяем первые 2 массива, чтобы получить отсортированный массив размером 2n.Мы повторяем это для всех входных массивов и после первого прохода получаем k/2 отсортированных массивов, каждый из которых имеет размер 2n.Мы повторяем этот процесс, пока не получим окончательный массив.Каждый проход имеет временную сложность O(kn), так как один элемент будет добавлен в соответствующий выходной массив после каждого сравнения.И у нас есть лог k ​​пропусков.Итак, общая сложность времени составляет O(kn log k).И поскольку мы можем удалять входные массивы после каждого прохода, пространство, используемое в любой точке, равно O(kn).

. Как мы видим, асимптотические временные и пространственные сложности абсолютно одинаковы в обоих подходах.Итак, когда именно мы предпочитаем одно над другим?Я понимаю, что для внешней сортировки лучше подходит Priority Queue , потому что вам нужно только 1029 * пространство в памяти, и вы можете читать и записывать каждый элемент с диска и обратно на диск.Но как эти подходы складываются друг против друга, когда у нас достаточно памяти?

Answer 1

Общее количество операций, сравнений + ходов, примерно одинаково в любом случае. K-way merge делает больше сравнений, но меньше движений. Моя система имеет 8-стороннюю кэш-память (Intel 3770K 3,5 ГГц), которая в случае четырехсторонней сортировки слиянием позволяет использовать 4 строки кэша для 4 входных циклов и 1 строку кэша для объединенного выходного цикла. В 64-битном режиме имеется 16 регистров, которые могут использоваться для рабочих переменных, 8 из них используются для указателей на текущую и конечную позицию каждого «прогона» (оптимизация компилятора).

В моей системе я сравнил четырехстороннее слияние (без кучи, ~ 3 сравнения на перемещенный элемент) с двухсторонним слиянием (~ 1 сравнение за ход, но в два раза больше проходов), четырехстороннее в 1,5 раза больше количество сравнений, но в 0,5 раза больше количества ходов, так что, по сути, такое же количество операций, но 4-й способ примерно на 15% быстрее из-за проблем с кешем.

Я не знаю, достаточно ли 16 регистров для слияния 6 путей, чтобы быть чуть-чуть быстрее, а 16 регистров недостаточно для слияния 8 путей (некоторые из рабочих переменных будут основаны на памяти / кэше). Попытка использовать кучу, вероятно, не поможет, поскольку куча будет основываться на памяти / кэше (не на основе регистра).

K-way слияние в основном полезно для внешних сортировок, где время сравнения игнорируется из-за гораздо больших накладных расходов на ходы.