k -сторонний алгоритм слияния

В информатике алгоритмы k -стороннего слияния или многосторонние слияния представляют собой особый тип алгоритмов слияния последовательностей , которые специализируются на приеме k отсортированных списков и объединении их в один отсортированный список. Эти алгоритмы слияния обычно относятся к алгоритмам слияния, которые принимают количество отсортированных списков больше двух. Двусторонние слияния также называются двоичными слияниями. K-стороннее слияние также является внешним алгоритмом сортировки.

Двустороннее слияние

Двустороннее слияние, или двоичное слияние, широко изучалось из-за его ключевой роли в сортировке слиянием . Примером такого подхода является классическое слияние, которое часто встречается в примерах сортировки слиянием. Классическое слияние выводит элемент данных с наименьшим ключом на каждом шаге; учитывая некоторые отсортированные списки, он создает отсортированный список, содержащий все элементы любого из входных списков, и делает это за время, пропорциональное сумме длин входных списков.

Обозначим через A[1..p] и B[1..q] два массива, отсортированные по возрастанию. Далее обозначим C[1..n] выходной массив. Канонический алгоритм двустороннего слияния ^[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 -образного слияния состоит в слиянии k отсортированных массивов для создания одного отсортированного массива с одинаковыми элементами. Обозначим через n общее количество элементов. n равно размеру выходного массива и сумме размеров k входных массивов. Для простоты будем считать, что ни один из входных массивов не пуст. Как следствие $k\leq n$ , что упрощает отчетное время работы. Проблему можно решить в ${\mathcal {O}}(n\cdot \log(k))$ время работы с ${\mathcal {O}}(n)$ космос. Существует несколько алгоритмов, позволяющих добиться такого времени работы.

Итеративное двустороннее слияние

Проблему можно решить путем итеративного объединения двух из k массивов с использованием двустороннего слияния до тех пор, пока не останется только один массив. Если массивы объединяются в произвольном порядке, то результирующее время работы составит всего O(kn). Это субоптимально.

Время выполнения можно улучшить, итеративно объединяя первое со вторым, третье с четвертым и так далее. Поскольку количество массивов уменьшается вдвое на каждой итерации, остается только Θ(log k) итераций. На каждой итерации каждый элемент перемещается ровно один раз. Таким образом, время работы на итерацию выражается в Θ(n), поскольку n — количество элементов. Таким образом, общее время работы выражается в Θ(n log k).

Мы можем улучшить этот алгоритм, итеративно объединяя два кратчайших массива. Понятно, что это минимизирует время работы и поэтому не может быть хуже стратегии, описанной в предыдущем пункте. Таким образом, время работы составляет O(n log k). К счастью, в пограничных случаях время работы может быть лучше. Рассмотрим, например, вырожденный случай, когда все массивы, кроме одного, содержат только один элемент. Стратегия, описанная в предыдущем абзаце, требует времени работы Θ(n log k), в то время как улучшенная стратегия требует только времени работы Θ(n + k log k).

Прямое k -образное слияние

В этом случае мы бы одновременно объединили k-серии вместе.

Простая реализация сканирует все k массивов, чтобы определить минимум. Эта простая реализация приводит к времени работы Θ(kn). Обратите внимание, что это упоминается только как возможность, ради обсуждения. Хоть это и сработало бы, но это неэффективно.

Мы можем улучшить эту ситуацию, быстрее вычисляя наименьший элемент. Используя кучи , турнирные деревья или деревья расширения , наименьший элемент можно определить за время O(log k). Таким образом, результирующее время работы составляет O(n log k).

Чаще используется куча, хотя на практике турнирное дерево работает быстрее. Куча использует примерно 2*log(k) сравнений на каждом этапе, поскольку она обрабатывает дерево от корня вниз и требует сравнения обоих дочерних элементов каждого узла. Между тем, турнирному дереву нужны только сравнения log(k), поскольку оно начинается с нижней части дерева и работает до корня, выполняя только одно сравнение на каждом уровне. Поэтому дерево турниров должно быть предпочтительной реализацией.

Куча

Идея состоит в том, чтобы поддерживать минимальную кучу из k списков, каждый из которых имеет ключ наименьшего текущего элемента. Простой алгоритм создает выходной буфер из узлов из кучи. Начните с создания минимальной кучи узлов, где каждый узел состоит из головного элемента списка и остальной части (или хвоста) списка. Поскольку списки изначально сортируются, заголовок является наименьшим элементом каждого списка; свойство кучи гарантирует, что корень содержит минимальный элемент во всех списках. Извлеките корневой узел из кучи, добавьте элемент head в выходной буфер, создайте новый узел из хвоста и вставьте его в кучу. Повторяйте до тех пор, пока в куче не останется только один узел, после чего просто добавьте оставшийся список (голову и хвост) в выходной буфер.

Использование указателей, алгоритма кучи на месте ^[2] выделяет минимальную кучу указателей во входные массивы. Первоначально эти указатели указывают на самые маленькие элементы входного массива. Указатели сортируются по значению, на которое они указывают. На этапе предварительной обработки O(k) куча создается с использованием стандартной процедуры heapify. Далее алгоритм итеративно передает элемент, на который указывает корневой указатель, увеличивает этот указатель и выполняет стандартную процедуру уменьшения ключа над корневым элементом. Время выполнения процедуры увеличения ключа ограничено O(log k). Поскольку элементов n, общее время работы равно O(n log k).

Обратите внимание, что операция замены ключа и итеративное выполнение уменьшения ключа или просеивания вниз не поддерживаются многими библиотеками приоритетной очереди, такими как C++ stl и Java. Выполнение функций извлечения-мин и вставки менее эффективно.

Дерево турниров

Дерево турниров ^[3] основан на отборочном турнире, как и в спортивных соревнованиях. В каждой игре соревнуются два входных элемента. Победитель переводится в следующий раунд. Таким образом, мы получаем бинарное дерево игр. Список отсортирован по возрастанию, поэтому победителем игры становится меньший из обоих элементов.

Для слияния k-путей более эффективно хранить только проигравшего в каждой игре (см. изображение). Поэтому структура данных называется деревом проигравших. При построении дерева или замене элемента на следующий из его списка мы все равно продвигаем победителя игры наверх. Дерево заполняется, как в спортивном матче, но в узлах сохраняется только проигравший. Обычно добавляется дополнительный узел над корнем, который представляет общего победителя. Каждый лист хранит указатель на один из входных массивов. Каждый внутренний узел хранит значение и индекс. Индекс внутреннего узла указывает, из какого входного массива получено значение. Значение содержит копию первого элемента соответствующего входного массива.

Алгоритм итеративно добавляет минимальный элемент к результату, а затем удаляет элемент из соответствующего входного списка. Он обновляет узлы на пути от обновленного листа до корня ( выбор замены ). Удаленный элемент становится абсолютным победителем. Следовательно, он выиграл каждую игру на пути от входного массива к корню. При выборе нового элемента из входного массива элемент должен конкурировать с предыдущими проигравшими на пути к корню. При использовании дерева проигравших партнер для повтора игр уже сохранен в узлах. Проигравший в каждой переигранной игре записывается в узел, а победитель итеративно продвигается на вершину. Когда корень достигнут, новый общий победитель найден и может быть использован в следующем раунде слияния.

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

Алгоритм

Турнирное дерево можно представить как сбалансированное двоичное дерево, добавляя контрольные значения во входные списки (т. е. добавляя элемент в конец каждого списка со значением бесконечности) и добавляя нулевые списки (содержащие только контрольные значения) до тех пор, пока количество списки - это степень двойки. Сбалансированное дерево может храниться в одном массиве. Родительский элемент можно получить, разделив текущий индекс на два.

При обновлении одного из листьев переигрываются все игры от листа до корня. В следующем псевдокоде вместо массива используется объектно-ориентированное дерево, поскольку его легче понять. Кроме того, предполагается, что количество списков для объединения равно степени двойки.

function merge(L1, ..., Ln)
    buildTree(heads of L1, ..., Ln)
    while tree has elements
        winner := tree.winner
        output winner.value
        new := winner.index.next
        replayGames(winner, new) // Replacement selection

function replayGames(node, new)
    loser, winner := playGame(node, new)
    node.value := loser.value
    node.index := loser.index
    if node != root
        replayGames(node.parent, winner)

function buildTree(elements)
    nextLayer := new Array()
    while elements not empty
        el1 := elements.take()
        el2 := elements.take()
        loser, winner := playGame(el1, el2)
        parent := new Node(el1, el2, loser)
        nextLayer.add(parent)
    if nextLayer.size == 1
        return nextLayer // only root
    else
        return buildTree(nextLayer)

Время работы

Вначале дерево создается за время Θ(k). На каждом этапе слияния необходимо переигрывать только игры на пути от нового элемента к корню. В каждом слое необходимо только одно сравнение. Поскольку дерево сбалансировано, путь от одного из входных массивов до корня содержит всего Θ(log k) элементов. Всего нужно перенести n элементов. Таким образом, итоговое общее время работы выражается в Θ(n log k). ^[3]

Пример

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

Выбор замены

Игры воспроизводятся снизу вверх. На каждом уровне дерева конкурируют текущий сохраненный элемент узла и элемент, предоставленный из нижнего уровня. Победитель продвигается на вершину до тех пор, пока мы не определим нового абсолютного победителя. Проигравший сохраняется в узле дерева.

Шаг	Действие
1	Лист 1 (абсолютный победитель) заменяется на 9, следующий элемент из входного списка.
2	Переигрывание игры 9 на 7 (предыдущий проигравший). 7 побед, потому что оно меньше. Таким образом, 7 перемещается наверх, а 9 сохраняется в узле.
3	Переигрывание игры 7 на 3 (предыдущий проигравший). 3 победы, потому что он меньше. Таким образом, 3 перемещается наверх, а 7 сохраняется в узле.
4	Переигрывание игры 3 на 2 (предыдущий проигравший). 2 победы, потому что он меньше. Таким образом, 2 перемещается наверх, а 3 сохраняется в узле.
5	Новый общий победитель 2 сохраняется над корнем.

Объединить

Чтобы выполнить само слияние, наименьший элемент неоднократно заменяется следующим входным элементом. После этого игры наверх переигрываются.

В этом примере в качестве входных данных используются четыре отсортированных массива.

{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 -сторонние слияния используются во внешних процедурах сортировки. ^[4] Алгоритмы внешней сортировки — это класс алгоритмов сортировки, которые могут обрабатывать огромные объемы данных. Внешняя сортировка требуется, когда сортируемые данные не помещаются в основную память вычислительного устройства (обычно ОЗУ) и вместо этого должны находиться в более медленной внешней памяти (обычно на жестком диске). Алгоритмы k -путевого слияния обычно используются на втором этапе алгоритмов внешней сортировки, так же, как и для сортировки слиянием.

Многоходовое слияние позволяет объединять файлы за пределами памяти за меньшее количество проходов, чем при двоичном слиянии. Если необходимо объединить 6 прогонов, то для двоичного слияния потребуется 3 прохода слияния, в отличие от одного прохода слияния при 6-стороннем слиянии. Такое сокращение количества проходов слияния особенно важно, учитывая большой объем информации, которая обычно сортируется в первую очередь, что позволяет добиться большего ускорения и одновременно сократить количество обращений к более медленному хранилищу.

Ссылки

^ Томас Х. Кормен ; Чарльз Э. Лейзерсон; Рональд Л. Ривест ; Клиффорд Стейн (2001). Введение в алгоритмы . С Прессой. стр. 28–29. ISBN 978-0-262-03293-3 .
^ Бентли, Джон Луи (2000). Жемчуг программирования (2-е изд.). Эддисон Уэсли. стр. 147–162. ISBN 0201657880 .
^ Перейти обратно: ^а ^б Кнут, Дональд (1998). «Глава 5.4.1. Многоходовое слияние и выбор замены». Сортировка и поиск . Искусство компьютерного программирования . Том. 3 (2-е изд.). Аддисон-Уэсли. стр. 252–255. ISBN 0-201-89685-0 .
^ Шаффер, Клиффорд А. (26 июля 2012 г.). Структуры данных и алгоритмический анализ в C++, третье издание . Курьерская корпорация. ISBN 9780486172620 .

[1] Томас Х. Кормен ; Чарльз Э. Лейзерсон; Рональд Л. Ривест ; Клиффорд Стейн (2001). Введение в алгоритмы . С Прессой. стр. 28–29. ISBN 978-0-262-03293-3 .

[2] Бентли, Джон Луи (2000). Жемчуг программирования (2-е изд.). Эддисон Уэсли. стр. 147–162. ISBN 0201657880 .

[knuth98-3] Перейти обратно: ^а ^б Кнут, Дональд (1998). «Глава 5.4.1. Многоходовое слияние и выбор замены». Сортировка и поиск . Искусство компьютерного программирования . Том. 3 (2-е изд.). Аддисон-Уэсли. стр. 252–255. ISBN 0-201-89685-0 .

[4] Шаффер, Клиффорд А. (26 июля 2012 г.). Структуры данных и алгоритмический анализ в C++, третье издание . Курьерская корпорация. ISBN 9780486172620 .

[1]

[2]

[3]

[4]