Алгоритм слияния

Алгоритм, объединяющий несколько отсортированных списков в один

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

Приложение

График, иллюстрирующий сортировку слиянием. Две красные стрелки, исходящие из одного и того же узла, указывают на подразделение, а две зеленые стрелки, заканчивающиеся в одном и том же узле, соответствуют выполнению алгоритма слияния.

Алгоритм слияния играет решающую роль в алгоритме сортировки слиянием , алгоритме сортировки на основе сравнения . Концептуально алгоритм сортировки слиянием состоит из двух этапов:

1. Рекурсивно разделите список на подсписки (примерно) одинаковой длины, пока каждый подсписок не будет содержать только один элемент, или, в случае итеративной (снизу вверх) сортировки слиянием, рассматривайте список из n элементов как n подсписков размера 1. список, содержащий один элемент, по определению отсортирован.
2. Повторно объединяйте подсписки, чтобы создать новый отсортированный подсписок, пока единый список не будет содержать все элементы. Единый список — это отсортированный список.

Алгоритм слияния неоднократно используется в алгоритме сортировки слиянием.

Пример сортировки слиянием приведен на иллюстрации. Он начинается с несортированного массива из 7 целых чисел. Массив разделен на 7 разделов; каждый раздел содержит 1 элемент и отсортирован. Затем отсортированные разделы объединяются для создания более крупных отсортированных разделов, пока не останется один раздел — отсортированный массив.

Объединение двух списков

Объединение двух отсортированных списков в один может осуществляться в линейном времени и линейном или постоянном пространстве (в зависимости от модели доступа к данным). Следующий псевдокод демонстрирует алгоритм, который объединяет входные списки ( связанные списки или массивы ) A и B в новый список C. ^{[1] [2] : 104} Заголовок функции возвращает первый элемент списка; «Удалить» элемент означает удалить его из списка, обычно путем увеличения указателя или индекса.

алгоритм merge(A, B) — это  входные данные A, B: список возвращает список C := новый пустой список пока A не пусто и B не пусто, сделать  , если head(A) ≤ head(B) , то добавить заголовок (A) к C уронить голову А еще добавить заголовок (B) к C уронить голову Б // К этому моменту либо A, либо B пусто. Осталось очистить другой входной список.  пока A не пусто, сделайте добавить заголовок (A) к C уронить голову А пока B не пусто, сделайте добавить заголовок (B) к C уронить голову Б вернуть С

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

В алгоритме сортировки слиянием эта подпрограмма обычно используется для объединения двух подмассивов A[lo..mid] , A[mid+1..hi] одного массива A . Это можно сделать, скопировав подмассивы во временный массив, а затем применив описанный выше алгоритм слияния. ^[1] Выделения временного массива можно избежать, но за счет скорости и простоты программирования. Были разработаны различные алгоритмы слияния на месте, ^[3] иногда жертвуя привязкой к линейному времени для получения алгоритма O ( n log n ) ; ^[4] см. раздел «Сортировка слиянием» § Варианты для обсуждения.

K-образное слияние

k -способ слияния обобщает двоичное слияние до произвольного числа k отсортированных входных списков. Приложения слияния k -способов возникают в различных алгоритмах сортировки, включая терпеливую сортировку ^[5] и внешний алгоритм сортировки, который делит входные данные на k =1/М− 1 блок, который помещается в память, сортирует их один за другим, затем объединяет эти блоки. ^{[2] : 119–120}

Существует несколько решений этой проблемы. Наивное решение — выполнить цикл по k спискам, чтобы каждый раз выбирать минимальный элемент, и повторять этот цикл, пока все списки не станут пустыми:

• Входные данные: список из k списков.
• Пока любой из списков не пуст:
  • Перебирайте списки, чтобы найти список с минимальным первым элементом.
  • Выведите минимальный элемент и удалите его из списка.

В худшем случае этот алгоритм выполняет ( k −1)( n −к/2) сравнения элементов для выполнения своей работы, если в списках всего n элементов. ^[6] Его можно улучшить, сохраняя списки в очереди с приоритетами ( min-heap ), ключом которой является их первый элемент:

• Создайте минимальную кучу h из k списков, используя первый элемент в качестве ключа.
• Пока любой из списков не пуст:
  • Пусть я = find-min( h ) .
  • Выведите первый элемент списка i и удалите его из этого списка.
  • Повторно собрать h .

Поиск следующего наименьшего элемента для вывода (find-min) и восстановление порядка кучи теперь можно выполнить за время O (log k ) (более конкретно, 2⌊log k ⌋ сравнения ^[6] ), и вся проблема может быть решена так: решено за время O ( n log k ) (приблизительно 2 n ⌊log k ⌋ сравнений). ^{[6] [2] : 119–120}

Третий алгоритм решения проблемы — это решение «разделяй и властвуй» , основанное на алгоритме двоичного слияния:

• Если k = 1 , выведите единственный входной список.
• Если k = 2 , выполните двоичное слияние.
• В противном случае рекурсивно объедините первые списки ⌊ k /2⌋ и последние списки ⌈ k /2⌉ , а затем объедините их в двоичном виде.

Когда входные списки для этого алгоритма упорядочены по длине, сначала самый короткий, это требует меньше, чем n ⌈log k ⌉ сравнений, т. е. меньше половины числа, используемого алгоритмом на основе кучи; на практике он может быть таким же быстрым или медленным, как алгоритм на основе кучи. ^[6]

Параллельное слияние

Параллельная версия алгоритма двоичного слияния может служить строительным блоком параллельной сортировки слиянием . Следующий псевдокод демонстрирует этот алгоритм в параллельном стиле «разделяй и властвуй» (адаптировано из Cormen et al. ^{[7] : 800} ). Он работает с двумя отсортированными массивами A и B и записывает отсортированный вывод в массив C. Обозначение A[i...j] обозначает часть A от индекса i до j , исключая.

алгоритм merge(A[i...j], B[k...ℓ], C[p...q]) — это  входные данные A, B, C: массив i, j, k, ℓ, p, q: индексы пусть m = j - i, п = ℓ - к если m < n , то поменяйте местами A и B // убедитесь, что A — больший массив: i, j по-прежнему принадлежат A; к, ℓ к B поменять местами м и н если m ≤ 0 , то  вернуть  // базовый случай, объединять нечего пусть r = ⌊(i + j)/2⌋ пусть s = двоичный поиск (A[r], B[k...ℓ]), пусть t = p + (r - i) + (s - k) С[т] = А[г] параллельно делаю merge(A[i...r], B[k...s], C[p...t]) merge(A[r+1...j], B[s...ℓ], C[t+1...q])

Алгоритм работает путем разделения A или B (в зависимости от того, что больше) на (почти) равные половины. Затем он разбивает другой массив на часть со значениями, меньшими, чем середина первого, и часть с большими или равными значениями. ( Подпрограмма двоичного поиска возвращает индекс в B , где было бы A [ r ] , если бы оно было в B ; что это всегда число между k и ℓ .) Наконец, каждая пара половин рекурсивно объединяется , и поскольку рекурсивные вызовы независимы друг от друга, их можно выполнять параллельно. Гибридный подход, в котором последовательный алгоритм используется для базового случая рекурсии, показал себя хорошо на практике ^[8]

Работа , выполняемая алгоритмом для двух массивов, содержащих в общей сложности n элементов, т. е. время работы его последовательной версии, равна O ( n ) . Это оптимально, поскольку в C необходимо скопировать n элементов . Чтобы вычислить диапазон алгоритма, необходимо вывести Рекуррентное соотношение . Поскольку два рекурсивных вызова слияния выполняются параллельно, необходимо учитывать только более затратный из двух вызовов. В худшем случае максимальное количество элементов в одном из рекурсивных вызовов не превышает, поскольку массив с большим количеством элементов идеально разбивается пополам. Добавляя стоимость двоичного поиска, мы получаем эту повторяемость как верхнюю границу: ${\textstyle {\frac {3}{4}}n}$ ${\displaystyle \Theta \left(\log(n)\right)}$

${\displaystyle T_{\infty }^{\text{merge}}(n)=T_{\infty }^{\text{merge}}\left({\frac {3}{4}}n\right)+\Theta \left(\log(n)\right)}$

Решение — это означает, что на идеальной машине с неограниченным количеством процессоров требуется столько же времени. ^{[7] : 801–802.} ${\displaystyle T_{\infty }^{\text{merge}}(n)=\Theta \left(\log(n)^{2}\right)}$

Примечание. Процедура нестабильна : если равные элементы разделены разделением A и B , они будут чередоваться в C ; также замена A и B разрушит порядок, если одинаковые элементы распределены между обоими входными массивами. В результате при использовании этого алгоритма для сортировки сортировка становится нестабильной.

Параллельное объединение двух списков

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

Существующие параллельные алгоритмы основаны на модификациях слияния битонического сортировщика или сортировки слиянием нечетно-четных . ^[9] В 2018 году Сайто М. и др. представила MMS ^[10] для FPGA, направленную на устранение канала передачи данных с многоцикловой обратной связью, который препятствовал эффективной конвейерной обработке в аппаратном обеспечении. Также в 2018 г. Папафилиппу П. и др. представила FLiMS ^[9] , которая улучшила использование аппаратного обеспечения и производительность, требуя только объединения этапов конвейера блоков сравнения и замены P/2 с параллелизмом P- элементов за цикл FPGA. ${\displaystyle \log _{2}(P)+1}$

Языковая поддержка

Некоторые языки программирования предоставляют встроенную или библиотечную поддержку объединения отсортированных коллекций .

С++

В стандартной библиотеке шаблонов C ++ есть функция std::merge , которая объединяет два отсортированных диапазона итераторов , и std::inplace_merge , которая объединяет два последовательных отсортированных диапазона на месте . Кроме того, класс std::list (связанный список) имеет собственный метод слияния , который объединяет другой список в себя. Тип объединяемых элементов должен поддерживать оператор «меньше» ( < ) или должен быть снабжен пользовательским компаратором.

C++17 допускает различные политики выполнения, а именно последовательную, параллельную и параллельно-неупорядоченную. ^[11]

Питон

Стандартная библиотека Python (начиная с версии 2.6) также имеет функцию слияния в модуле heapq , которая принимает несколько отсортированных итераций и объединяет их в один итератор. ^[12]

Смотрите также

• Слияние (контроль версий)
• Присоединяйтесь (реляционная алгебра)
• Присоединиться (SQL)
• Присоединяйтесь (Unix)

Рекомендации

1. Скиена, Стивен (2010). Руководство по разработке алгоритмов (2-е изд.). Springer Science+Business Media . п. 123. ИСБН 978-1-849-96720-4.
2. Курт Мельхорн ; Питер Сандерс (2008). Алгоритмы и структуры данных: базовый набор инструментов. Спрингер. ISBN 978-3-540-77978-0.
3. Катаджайнен, Юрки; Пасанен, Томи; Теухола, Юкка (1996). «Практическая сортировка слиянием на месте». Нордик Дж. Компьютерные технологии . 3 (1): 27–40. CiteSeerX 10.1.1.22.8523 . 
4. Ким, Пок-Сон; Куцнер, Арне (2004). Стабильное объединение минимального объема памяти посредством симметричных сравнений . Европейский симп. Алгоритмы. Конспекты лекций по информатике. Том. 3221. стр. 714–723. CiteSeerX 10.1.1.102.4612 . дои : 10.1007/978-3-540-30140-0_63. ISBN  978-3-540-23025-0.
5. Чандрамули, Бадриш; Гольдштейн, Джонатан (2014). Терпение — добродетель: новый взгляд на слияние и сортировку на современных процессорах . СИГМОД/ПОДС.
6. Грин, Уильям А. (1993). k-образное слияние и k-арная сортировка (PDF) . Учеб. 31-я ежегодная Юго-восточная конференция ACM. стр. 127–135.
7. Кормен, Томас Х .; Лейзерсон, Чарльз Э .; Ривест, Рональд Л .; Штейн, Клиффорд (2009) [1990]. Введение в алгоритмы (3-е изд.). MIT Press и McGraw-Hill. ISBN 0-262-03384-4.
8. Виктор Дж. Дуваненко (2011), «Параллельное слияние», Журнал доктора Добба
9. Папафилиппу, Филиппос; Люк, Уэйн; Брукс, Крис (2022). «FLiMS: быстрое и легкое двустороннее слияние для сортировки». Транзакции IEEE на компьютерах : 1–12. дои : 10.1109/TC.2022.3146509. hdl : 10044/1/95271 . S2CID  245669103.
10. Сайто, Макото; Эльсайед, Эльсайед А.; Чу, Тим Ван; Машимо, Сусуму; Кисе, Кенджи (апрель 2018 г.). «Высокопроизводительный и экономичный аппаратный сортировщик слиянием без обратной связи». 26-й ежегодный международный симпозиум IEEE по программируемым пользовательским вычислительным машинам (FCCM) , 2018 г. стр. 197–204. дои : 10.1109/FCCM.2018.00038. ISBN 978-1-5386-5522-1. S2CID  52195866.
11. "Стд: слияние". cppreference.com. 08.01.2018 . Проверено 28 апреля 2018 г.
12. «heapq — Алгоритм очереди кучи — документация Python 3.10.1» .

дальнейшее чтение

• Дональд Кнут . Искусство компьютерного программирования , Том 3: Сортировка и поиск , Третье издание. Аддисон-Уэсли, 1997. ISBN 0-201-89685-0 . Страницы 158–160 раздела 5.2.4: Сортировка путем слияния. Раздел 5.3.2: Слияние минимального сравнения, стр. 197–207. 

Внешние ссылки

• Высокопроизводительная реализация параллельного и последовательного слияния на C# с исходным кодом в GitHub и в C++ GitHub