В информатике , K -way алгоритмы слияния или многоходовые слияния представляют собой тип специфики алгоритмов последовательности слияния , которые специализируются в принятии в к отсортированным спискам и объединение их в единый отсортированный список. Эти алгоритмы слияния обычно относятся к алгоритмам слияния, которые принимают количество отсортированных списков больше двух. Двусторонние слияния также называются бинарными слияниями.
2-стороннее слияние [ править ]
Двустороннее слияние, или двоичное слияние, широко изучалось из-за его ключевой роли в сортировке слиянием . Примером этого является классическое слияние, которое часто встречается в примерах сортировки слиянием. Классическое слияние выводит элемент данных с наименьшим ключом на каждом шаге; учитывая некоторые отсортированные списки, он создает отсортированный список, содержащий все элементы в любом из входных списков, и делает это за время, пропорциональное сумме длин входных списков.
Обозначим через 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 -way слияние [ править ]
Проблема слияния k- way состоит в слиянии k отсортированных массивов для создания единого отсортированного массива с одинаковыми элементами. Обозначим n общее количество элементов. n равно размеру выходного массива и сумме размеров k входных массивов. Для простоты мы предполагаем, что ни один из входных массивов не пуст. Как следствие , это упрощает заявленное время работы. Проблему можно решить в беге времени с пространством. Существует несколько алгоритмов, позволяющих достичь этого времени работы.
Итеративное двухстороннее слияние [ править ]
Проблема может быть решена путем итеративного слияния двух из k массивов с помощью двухстороннего слияния, пока не останется только один массив. Если массивы объединяются в произвольном порядке, то результирующее время работы составляет всего O (kn). Это неоптимально.
Время работы можно улучшить, итеративно объединяя первое со вторым, третье с четвертым и так далее. Поскольку количество массивов уменьшается вдвое на каждой итерации, существует только Θ (log k) итераций. В каждой итерации каждый элемент перемещается ровно один раз. Таким образом, время выполнения на итерацию выражается в Θ (n), поскольку n - количество элементов. Таким образом, общее время работы выражается в Θ (n log k).
Мы можем дополнительно улучшить этот алгоритм, итеративно объединяя два самых коротких массива. Понятно, что это минимизирует время работы и поэтому не может быть хуже стратегии, описанной в предыдущем абзаце. Таким образом, время работы составляет O (n log k). К счастью, в пограничных случаях время работы может быть лучше. Рассмотрим, например, вырожденный случай, когда все массивы, кроме одного, содержат только один элемент. Стратегия, описанная в предыдущем абзаце, требует времени выполнения (n log k), в то время как улучшенная стратегия требует только времени работы (n).
Прямое слияние k- way [ править ]
В этом случае мы одновременно объединим 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).
Обратите внимание, что операция замены ключа и итеративного уменьшения или отсеивания не поддерживается многими библиотеками Priority Queue, такими как C ++ stl и Java. Выполнение функций extract-min и insert менее эффективно.
Дерево турниров [ править ]
Дерево турниров [3] основано на турнирах на выбывание, как и в спорте. В каждой игре соревнуются два элемента ввода. Победитель переходит в следующий раунд. Таким образом, мы получаем двоичное дерево игр. Список отсортирован в порядке возрастания, поэтому победителем в игре становится меньший из обоих элементов.
Для k-way слияния более эффективно хранить только проигравшего в каждой игре (см. Изображение). Поэтому структура данных называется деревом неудачников. При построении дерева или замене элемента на следующий из его списка мы по-прежнему продвигаем победителя игры на вершину. Дерево заполняется как в спортивном матче, но в узлах сохраняется только проигравший. Обычно над корнем добавляется дополнительный узел, который представляет общего победителя. Каждый лист хранит указатель на один из входных массивов. Каждый внутренний узел хранит значение и индекс. Индекс внутреннего узла указывает, из какого входного массива берется значение. Значение содержит копию первого элемента соответствующего входного массива.
Алгоритм итеративно добавляет минимальный элемент к результату, а затем удаляет элемент из соответствующего входного списка. Он обновляет узлы на пути от обновленного листа до корня ( выбор замены ). Удаленный элемент является абсолютным победителем. Следовательно, он выигрывал каждую игру на пути от входного массива к корню. При выборе нового элемента из входного массива элемент должен соревноваться с предыдущими проигравшими на пути к корню. При использовании дерева проигравших партнер для воспроизведения игр уже сохраняется в узлах. Проигравший в каждой воспроизведенной игре записывается в узел, а победитель итеративно продвигается на вершину. Когда корень достигнут, новый общий победитель найден и может быть использован в следующем раунде слияния.
В изображениях турнирного дерева и дерева проигравших в этом разделе используются одни и те же данные, и их можно сравнить, чтобы понять, как работает дерево проигравших.
Алгоритм [ править ]
Турнирное дерево может быть представлено как сбалансированное двоичное дерево путем добавления контрольных точек во входные списки и добавления списков до тех пор, пока количество списков не станет степенью двойки. Сбалансированное дерево можно хранить в одном массиве. К родительскому элементу можно получить доступ, разделив текущий индекс на два.
При обновлении одного из листьев воспроизводятся все игры от листа до корня. В следующем псевдокоде объектно-ориентированное дерево используется вместо массива, потому что его легче понять. Кроме того, предполагается, что количество объединяемых списков является степенью двойки.
функция слияния (L1,…, Ln) buildTree (главы L1,…, Ln) в то время как у дерева есть элементы победитель: = tree.winner выходной победитель.значение новое: = Windex.next replayGames (победитель, новый) // Выбор замены
функция replayGames (узел, новый) проигравший, победитель: = playGame (узел, новый) node.value: = loser.value node.index: = loser.index если узел! = корень replayGames (node.parent, победитель)
функция buildTree (элементы) nextLayer: = новый массив () пока элементы не пустые el1: = elements.take () el2: = elements.take () проигравший, победитель: = playGame (el1, el2) родитель: = новый узел (el1, el2, проигравший) nextLayer.add (родительский) if nextLayer.size == 1 return nextLayer // только корень 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 (nf (k)), где f растет асимптотически медленнее, чем логарифм. (Исключая данные с желаемым распределением, например непересекающиеся диапазоны.) Доказательство - прямое сокращение от сортировки на основе сравнения. Предположим, что такой алгоритм существует, тогда мы могли бы построить алгоритм сортировки на основе сравнения со временем выполнения O (nf (n)) следующим образом: Разбить входной массив на n массивов размера 1. Объединить эти n массивов с помощью k- способа. алгоритм слияния. Результирующий массив сортируется, и время выполнения алгоритма равно O (nf (n)). Это противоречит хорошо известному результату о том, что не существует алгоритма сортировки на основе сравнения с временем работы наихудшего случая ниже O (n log n).
Внешняя сортировка [ править ]
k- way слияния используются во внешних процедурах сортировки. [4] Внешние алгоритмы сортировки - это класс алгоритмов сортировки, которые могут обрабатывать большие объемы данных. Внешняя сортировка требуется, когда сортируемые данные не помещаются в основную память вычислительного устройства (обычно ОЗУ), а вместо этого они должны находиться в более медленной внешней памяти (обычно на жестком диске). Алгоритмы слияния k- way обычно имеют место на втором этапе алгоритмов внешней сортировки, так же, как и для сортировки слиянием.
Многостороннее слияние позволяет объединять файлы вне памяти за меньшее количество проходов, чем при двоичном слиянии. Если есть 6 прогонов, которые необходимо объединить, тогда для двоичного слияния потребуется 3 прохода слияния, в отличие от одиночного прохода слияния при 6-стороннем слиянии. Это сокращение проходов слияния особенно важно, учитывая большой объем информации, которая обычно сортируется в первую очередь, что позволяет увеличить скорость, а также уменьшить количество обращений к более медленной памяти.
Ссылки [ править ]
- ^ Томас Х. Кормен ; Чарльз Э. Лейзерсон; Рональд Л. Ривест ; Клиффорд Штайн (2001). Введение в алгоритмы . MIT Press. С. 28–29. ISBN 978-0-262-03293-3.
- ^ Бентли, Джон Луи (2000). Жемчуг программирования (2-е изд.). Эддисон Уэсли. С. 147–162. ISBN 0201657880.
- ^ a b Кнут, Дональд (1998). «Глава 5.4.1. Многостороннее объединение и выбор замены». Сортировка и поиск . Искусство программирования . 3 (2-е изд.). Эддисон-Уэсли. С. 252–255. ISBN 0-201-89685-0.CS1 maint: ref = harv ( ссылка )
- ^ Шаффер, Клиффорд А. (2012-07-26). Структуры данных и анализ алгоритмов в C ++, третье издание . Курьерская корпорация. ISBN 9780486172620.
