В информатике алгоритмы слияния k -way или многопутевые слияния являются особым типом алгоритмов слияния последовательностей , которые специализируются на приеме k-сортированных списков и слиянии их в один отсортированный список. Эти алгоритмы слияния обычно относятся к алгоритмам слияния , которые принимают количество отсортированных списков больше двух. Двусторонние слияния также называются бинарными слияниями. Слияние k-way также является внешним алгоритмом сортировки.
Двустороннее слияние, или бинарное слияние, было тщательно изучено из-за его ключевой роли в сортировке слиянием . Примером такого слияния является классическое слияние, которое часто встречается в примерах сортировки слиянием. Классическое слияние выводит элемент данных с наименьшим ключом на каждом шаге; при наличии некоторых отсортированных списков оно создает отсортированный список, содержащий все элементы в любом из входных списков, и делает это за время, пропорциональное сумме длин входных списков.
Обозначим через A[1..p] и B[1..q] два массива, отсортированных по возрастанию. Далее, обозначим через C[1..n] выходной массив. Канонический алгоритм 2-стороннего слияния [1] сохраняет индексы i, j и k в A, B и C соответственно. Изначально эти индексы относятся к первому элементу, т. е. равны 1. Если A[i] < B[j], то алгоритм копирует A[i] в C[k] и увеличивает i и k. В противном случае алгоритм копирует B[j] в C[k] и увеличивает j и k. Особый случай возникает, если либо i, либо j достигли конца A или B. В этом случае алгоритм копирует оставшиеся элементы B или A в C и завершается.
Задача слияния k -способов состоит в слиянии k-отсортированных массивов для получения одного отсортированного массива с одинаковыми элементами. Обозначим через n общее количество элементов. n равно размеру выходного массива и сумме размеров k-входных массивов. Для простоты мы предполагаем, что ни один из входных массивов не пуст. Как следствие , что упрощает сообщаемое время выполнения. Задача может быть решена за время выполнения с пространством. Существует несколько алгоритмов, которые достигают этого времени выполнения.
Проблему можно решить итеративным слиянием двух массивов из k с помощью 2-стороннего слияния, пока не останется только один массив. Если массивы объединяются в произвольном порядке, то результирующее время выполнения составит всего O(kn). Это неоптимально.
Время выполнения можно улучшить, итеративно объединяя первый со вторым, третий с четвертым и т. д. Поскольку количество массивов уменьшается вдвое в каждой итерации, есть только Θ(log k) итераций. В каждой итерации каждый элемент перемещается ровно один раз. Таким образом, время выполнения на итерацию составляет Θ(n), поскольку n — это количество элементов. Таким образом, общее время выполнения составляет Θ(n log k).
Мы можем еще больше улучшить этот алгоритм, итеративно объединив два самых коротких массива. Очевидно, что это минимизирует время выполнения и, следовательно, не может быть хуже, чем стратегия, описанная в предыдущем абзаце. Таким образом, время выполнения составляет O(n log k). К счастью, в пограничных случаях время выполнения может быть лучше. Рассмотрим, например, вырожденный случай, когда все массивы, кроме одного, содержат только один элемент. Стратегия, описанная в предыдущем абзаце, требует Θ(n log k) времени выполнения, в то время как улучшенная требует только Θ(n + k log k) времени выполнения.
В этом случае мы бы одновременно объединили k-прогоны.
Простая реализация просканирует все массивы k, чтобы определить минимум. Эта простая реализация приводит к времени выполнения Θ(kn). Обратите внимание, что это упоминается только как возможность, для обсуждения. Хотя это и будет работать, это неэффективно.
Мы можем улучшить это, вычислив наименьший элемент быстрее. Используя кучи , турнирные деревья или сплайсовые деревья , наименьший элемент можно определить за время O(log k). Таким образом, результирующее время выполнения составляет O(n log k).
Куча используется чаще, хотя турнирное дерево на практике быстрее. Куча использует примерно 2*log(k) сравнений на каждом шаге, поскольку она обрабатывает дерево от корня до самого низа и должна сравнивать обоих потомков каждого узла. Между тем, турнирному дереву нужны только log(k) сравнений, поскольку оно начинается с самого низа дерева и идет до корня, выполняя только одно сравнение на каждом уровне. Поэтому турнирное дерево должно быть предпочтительной реализацией.
Идея состоит в том, чтобы поддерживать минимальную кучу из k списков, каждый из которых задается наименьшим текущим элементом. Простой алгоритм создает выходной буфер с узлами из кучи. Начните с создания минимальной кучи узлов, где каждый узел состоит из головного элемента списка и остальной части (или хвоста) списка. Поскольку списки изначально отсортированы, голова является наименьшим элементом каждого списка; свойство кучи гарантирует, что корень содержит минимальный элемент по всем спискам. Извлеките корневой узел из кучи, добавьте головной элемент в выходной буфер, создайте новый узел из хвоста и вставьте его в кучу. Повторяйте, пока в куче не останется только один узел, после чего просто добавьте этот оставшийся список (голову и хвост) в выходной буфер.
Используя указатели, алгоритм кучи на месте [2] выделяет минимальную кучу указателей во входных массивах. Первоначально эти указатели указывают на наименьшие элементы входного массива. Указатели сортируются по значению, на которое они указывают. На этапе предварительной обработки O(k) куча создается с использованием стандартной процедуры heapify. После этого алгоритм итеративно передает элемент, на который указывает корневой указатель, увеличивает этот указатель и выполняет стандартную процедуру уменьшения ключа для корневого элемента. Время выполнения процедуры увеличения ключа ограничено O(log k). Поскольку имеется n элементов, общее время выполнения составляет O(n log k).
Обратите внимание, что операция замены ключа и итеративное выполнение reduce-key или sift-down не поддерживаются многими библиотеками Priority Queue, такими как C++ stl и Java. Выполнение функции extract-min и insert менее эффективно.
Турнирное дерево [3] основано на турнире на выбывание, как в спортивных соревнованиях. В каждой игре соревнуются два входных элемента. Победитель переходит в следующий раунд. Таким образом, мы получаем бинарное дерево игр. Список отсортирован в порядке возрастания, поэтому победителем игры становится меньший из обоих элементов.
Для k-way merge более эффективно хранить только проигравшего в каждой игре (см. изображение). Поэтому структура данных называется деревом проигравших. При построении дерева или замене элемента следующим из его списка мы все равно продвигаем победителя игры наверх. Дерево заполняется как в спортивном матче, но узлы хранят только проигравшего. Обычно добавляется дополнительный узел над корнем, который представляет общего победителя. Каждый лист хранит указатель на один из входных массивов. Каждый внутренний узел хранит значение и индекс. Индекс внутреннего узла указывает, из какого входного массива взято значение. Значение содержит копию первого элемента соответствующего входного массива.
Алгоритм итеративно добавляет минимальный элемент к результату, а затем удаляет элемент из соответствующего входного списка. Он обновляет узлы на пути от обновленного листа к корню ( выбор замены ). Удаленный элемент является общим победителем. Таким образом, он выиграл каждую игру на пути от входного массива к корню. При выборе нового элемента из входного массива элемент должен соревноваться с предыдущими проигравшими на пути к корню. При использовании дерева проигравших партнер для повторного воспроизведения игр уже хранится в узлах. Проигравший каждой повторной игры записывается в узел, а победитель итеративно продвигается наверх. Когда достигается корень, новый общий победитель находится и может быть использован в следующем раунде слияния.
Изображения турнирного дерева и дерева проигравших в этом разделе используют одни и те же данные и могут быть сравнены, чтобы понять, как работает дерево проигравших.
Турнирное дерево можно представить как сбалансированное двоичное дерево, добавляя к входным спискам сторожевые элементы (т. е. добавляя элемент в конец каждого списка со значением бесконечности) и добавляя пустые списки (содержащие только сторожевой элемент) до тех пор, пока количество списков не станет степенью двойки. Сбалансированное дерево можно сохранить в одном массиве. Родительский элемент можно получить, разделив текущий индекс на два.
При обновлении одного из листьев все игры от листа до корня воспроизводятся заново. В следующем псевдокоде вместо массива используется объектно-ориентированное дерево, поскольку его легче понять. Кроме того, предполагается, что количество списков для слияния равно степени двойки.
функция merge(L1, ..., Ln) buildTree(головы L1, ..., Ln) в то время как дерево имеет элементы победитель := дерево.победитель выход победитель.значение новый := победитель.индекс.следующий replayGames(winner, new) // Выбор замены
функция replayGames(узел, новый) проигравший, победитель := playGame(node, new) узел.значение := проигравший.значение индекс.узла := индекс.проигравшего если узел != корень replayGames(узел.родитель, победитель)
функция buildTree(элементы) nextLayer := новый массив() пока элементы не пустые el1 := элементы.take() el2 := элементы.take() проигравший, победитель := playGame(el1, el2) родитель := новый узел(el1, el2, неудачник) следующийСлой.добавить(родительский) если nextLayer.size == 1 вернуть nextLayer // только корень иначе вернуть buildTree(nextLayer)
В начале дерево сначала создается за время Θ(k). На каждом шаге слияния необходимо переиграть только игры на пути от нового элемента к корню. В каждом слое необходимо только одно сравнение. Поскольку дерево сбалансировано, путь от одного из входных массивов к корню содержит только Θ(log k) элементов. Всего необходимо перенести n элементов. Таким образом, итоговое общее время выполнения составляет Θ(n log k). [3]
В следующем разделе содержится подробный пример для этапа выбора замены и один пример для полного слияния, содержащего несколько вариантов выбора замены.
Игры воспроизводятся снизу вверх. В каждом слое дерева соревнуются текущий сохраненный элемент узла и элемент, предоставленный слоем ниже. Победитель продвигается наверх, пока мы не найдем нового общего победителя. Проигравший сохраняется в узле дерева.
Для выполнения самого слияния общий наименьший элемент многократно заменяется следующим входным элементом. После этого игры до самого верха переигрываются.
В этом примере в качестве входных данных используются четыре отсортированных массива.
{2, 7, 16}{5, 10, 20}{3, 6, 21}{4, 8, 9}Алгоритм запускается с головками каждого входного списка. Используя эти элементы, строится двоичное дерево проигравших. Для слияния самый низкий элемент списка 2 определяется путем просмотра общего минимального элемента наверху дерева. Затем это значение выталкивается, а его лист заполняется 7, следующим значением во входном списке. Игры на пути к вершине воспроизводятся, как в предыдущем разделе о выборе замены. Следующий удаляемый элемент — 3. Начиная со следующего значения в списке, 6, игры воспроизводятся до корня. Это повторяется до тех пор, пока минимум дерева не станет равен бесконечности.
Можно показать, что не существует алгоритма слияния k -способов на основе сравнения со временем выполнения в O ( n f(k)), где f растет асимптотически медленнее логарифма, а n — общее число элементов. (Исключая данные с желаемыми распределениями, такими как непересекающиеся диапазоны.) Доказательство представляет собой прямое сокращение от сортировки на основе сравнения. Предположим, что такой алгоритм существует, тогда мы могли бы построить алгоритм сортировки на основе сравнения со временем выполнения O ( n f( n )) следующим образом: разбить входной массив на n массивов размера 1. Объединить эти n массивов с помощью алгоритма слияния k -способов. Результирующий массив отсортирован, и алгоритм имеет время выполнения в O ( n f( n )). Это противоречит известному результату, что не существует алгоритма сортировки на основе сравнения со временем выполнения в худшем случае ниже O ( n log n ).
k -way merges используются во внешних процедурах сортировки. [4] Внешние алгоритмы сортировки — это класс алгоритмов сортировки, которые могут обрабатывать огромные объемы данных. Внешняя сортировка требуется, когда сортируемые данные не помещаются в основную память вычислительного устройства (обычно ОЗУ) и вместо этого должны находиться в более медленной внешней памяти (обычно на жестком диске). k -way merge algorithms обычно используются на втором этапе внешних алгоритмов сортировки, так же как и для сортировки слиянием.
Многоканальное слияние позволяет объединять файлы вне памяти за меньшее количество проходов, чем при бинарном слиянии. Если необходимо объединить 6 проходов, то бинарное слияние потребует 3 прохода слияния, в отличие от одного прохода слияния при 6-канальном слиянии. Такое сокращение проходов слияния особенно важно, учитывая большой объем информации, который обычно сортируется в первую очередь, что позволяет добиться большего ускорения, а также сократить количество обращений к более медленному хранилищу.