Т. Кормен, Ч. Лейсерзон, Р. Риверст, К. Штайн - Алгоритмы. Построение и анализ (2013) (1162189), страница 186
Текст из файла (страница 186)
Часть 171 Избраииые вемы Наша стратегия "разделяй и властвуй" для многопоточного слияния, проиллюстрированная на рис. 27.6, работает с подмассивами массива Т. Предположим, что мы сливаем два отсортированных подмассива — Т[р~ .. гз] длиной пз = гз — рз+1 и Т[рг . тг] длиной пз = гг — рг + 1 — в подмассив А[рз .. гз] длиной пз = гз — рз + 1 = пз + пз. Без потери общности мы делаем упрощающее предположение о том, что пз > пг. Сначала находим средний элемент х = Т[щ] подмассива Т[рз ..гз], где дз = [(рз+г~)/2].
Поскольку подмассив отсортирован, х является медианой Т[рз .. г~]: любой элемент в Т[рз .. дз — Ц не превышает х, а любой элемент в Т[дз+1 .. гз] не меньше х. Затем мы используем бинарный поиск для того, чтобы найти индекс дз в подмассиве Т[рз .. гз], такой, чтобы подмассив оставался отсортированным, если мы вставим х между Т[дз — Ц и Т[дз]. Затем мы сливаем исходные подмассивы Т[рз ..
г,] и Т[рз ..гз] в А[рз ..гз] следующим образом. 1. Устанавливаем дз = рз+ (щ — рд+ (дз — рз). 2. Копируем х в А[дз]. 3. Рекурсивно сливаем Т[рз .. дз — Ц с Т[рз .. дз — Ц и размещаем результат в подмассиве А[рз дз — Ц. 4. Р о сливаем Т[д, + 1..гз] с Т[дз .гз] и Размещаем РезУльг массиве А[дз+ 1 . гз]. Когда мы вычисляем дз, величина дз — рз представляет собой количество элементов в подмассиве Т[рз .. д~ — Ц, а величина дз — рз — количество элементов в подмассиве Т[рз .. дз — Ц. Таким образом, их сумма равна количеству элементов, которые располагаются перед х в подмассиве А[рз ..
гз]. Мы имеем дело с базовым случаем, когда п~ — — пз = О; при этом мы не должны выполнять никакой работы по слиянию двух пустых подмассивов. Поскольку мы предполагаем, что подмассив Т[рз .. г~] имеет как минимум ту же длину, что и Т[рз .. гз], т.е. пз > пз, проверить базовый случай можно одной лишь проверкой пз = О. Мы должны также убедиться, что рекурсия корректно обрабатывает случай, когда пуст только один из двух подмассивов, которым, в соответствии с нашим предположением о том, что пг > пз, должен быть подмассив Т[рз ., гз]. Теперь превратим указанные идеи в псевдокод. Начнем с бинарного поиска, который выразим последовательно. Процедура Вичлку-йнлксн(х, Т,р,г) получает ключ х и подмассив Т[р., г] и возвращает одно из следующего списка.
Если Т[р .. г] пуст (г < р), то процедура возвращает индекс р. Если х < Т[р], а следовательно, не превышает все элементы Т[р .. г], то процедура возвращает индекс р. Если х > Т[р], то процедура возвращает наибольший индекс д в диапазоне р < д < г + 1, такой, что Т[д — Ц < х. А вот и сам псевдокод. Глана гк Мноюнаточные алюрнтмы ВВ9 В1нлку-Белксн(х, Т, р, т) 1 1оча еа р 2 ЬздЬ = тах(р,т+ 1) 3 ттййе 1ом < ЬздЬ 4 тЫ = [(1оча+ ЬздЬ)/2] 5 Ых < Т[пзЫ] 6 ЬздЬ = тЫ 7 е1зе 1очл = тпЫ+ 1 8 гезнгп ЬздЬ Р-Мексе(Т,рытмрг, тг, А,рз) 1 п1 = тч — р1 + 1 2 пг = тг — рг+ 1 3 1зп1<пг 4 Обменять р1 с рг 5 Обменять тз с тг 6 Обменять пз с пг 7 Н'пз ==0 // Оба пусты? 8 гецзгп 9 е!зе91 = [(р1+тз)/2] ГО д = В1нлку-Яелксн(Т[дз] Т Рг тг) 11 дз = Рз + (91 Р1) + (дг Рг) Г2 [дз] = Т[91] 13 зрачгн Р-МексеЕ(Т,ры91 — 1,рг,дг 1 А рз) 14 Р-Мексее(Т, 91 + 1, ты дг, тг, А, дз + 1) 15 зупс // Гарантируем, что пз > пг Процедура Р-Мекое работает следующим образом.
В строках 1 и 2 вычисляются длины п1 и пг подмассивов 7 [Р1 .. т1] и Т[рг ., тг] соответственно. Вызов Впчлку-Белксн(х,Т,р,т) требует еа(18п) последовательного времени в худшем случае (здесь п = т — р+ 1 — размер подмассива, с которым работает процедура). (См. упр.
2.3.5.) Поскольку В1нлку-Яелксн является последовательной процедурой, в наихудшем случае ее работа и интервал равны Е1(18 п). Теперь мы готовы написать псевдокод процедуры многопоточного слияния. Подобно процедуре МЕКОЕ на с. 54, в процедуре Р-МЕКОЕ предполагается, что два сливаемых подмассива находятся в одном и том же массиве.
Однако в отличие от процедуры МЕКОЕ, в процедуре Р-МЕКОЕ не предполагается, что сливаемые подмассивы граничат друг с другом, т.е. процедура Р-Мекае не требует выполнения равенства рг = т, + 1. Еше одно различие между Меые и Р-МЕКОЕ в том, что процедура Р-МЕкаЕ получает в качестве аргумента выходной подмассив А, в котором должны будут храниться слитые значения. Вызов Р-Менее(Т,рг,тырг,тг, А,рз) сливает два отсортированных подмассива, Т[р1 ..тт] и Т[рг ..тг], в подмассив А[рз ..тз], где тз = рз + (тз — р~ + 1) + (тг — Рг + 1) — 1 = Рз + (т1 — рз) + (тг — Рг) + 1 и не передается в качестве входного аргумента, я40 Часть Ггд Избрастые течи В строках 3-б обеспечивается выполнение предположения о том, что иг > пг. В строке 7 выполняется проверка базового случая, когда подмассив Т[р1 ..г1] пуст (а следовательно, пуст и подмассив Т[рг ..
гг]), и в этом случае выполняется простой возврат из процедуры. В строках 9 — 15 реализована стратегия "разделяй и властвуй". Строка 9 вычисляет среднюю точку подмассива Т[рг ..гг], а строка 1О находит точку дг в подмассиве Т[рг .. гг], такую, что все элементы в Т[рг .. дг — 1] меньше Т[д1] (соответствующего х), а все элементы в Т[дг ..
гг] не менее Т[д1]. В строке 11 вычисляется индекс дз элемента, который делит выходной подмассив А[рз., гз] на А[рз .. дз — 1] и А[дз + 1 .. гз], а затем строка 12 копирует Т[д1] непосредственно в А[да]. Затем выполняется рекурсия с применением вложенного параллелизма. Строка 13 запускает первую подзадачу, в то время как строка 14 параллельно вызывает вторую подзадачу. Инструкция зупс в строке 15 гарантирует, что обе подзадачи будут завершены до возврата из процедуры. (Поскольку каждая процедура неявно выполняет зупе перед возвратом, можно опустить инструкцию яупс в строке 15, но явное включение этой инструкции является хорошим стилем кодирования.) Имеется определенная тонкость при кодировании, обеспечивающая корректность работы при пустом подмассиве Т[рг .. гг].
Она заключается в том, что на каждом рекурсивном вызове медианный элемент подмассива Т[р1 .. г1 ] помещается в выходной подмассив, пока сам Т[р1 .. гг] не станет, наконец, пустым и тем самым осуществится базовый случай. Анализ многопоточного слияния Сначала выведем рекуррентное соотношение для интервала РМ (п) процедуры Р-МЕКОЕ, где два подмассива содержат в сумме и = пз + пг элементов.
Поскольку запуск в строке 13 и вызов в строке 14 работают логически параллельно, рассмотрим только более дорогостоящий из них. Ключевым моментом является понимание того, что в наихудшем случае максимальное число элементов любого из рекурсивных вызовов может быть не более Зп/4, что поясняется следующим образом. Поскольку строки 3 — б гарантируют, что пг < пн отсюда вытекает, что пг = 2иг/2 < (и1 + пг)/2 = и/2. В наихудшем случае один из двух рекурсивных вызовов сливает [п1/2] элементов подмассива Т[рз ..г1] со всеми пг элементами подмассива Т[рг.. гг], а следовательно, количество элементов, вовлеченных в вызов, составляет [пг/2] + пг < п1/2+ пг/2+ из!2 = (иг + пг)/2+ пг/2 < и/2+ и/4 = Зп/4. Добавив стоимость 9(18и) вызова Впчхку-БЕАКсн в строке 1О, мы получим следующее рекуррентное соотношение для интервала в наихудшем случае: РМ (и) = РМ (Зп/4) +сз(18п) .
(27.8) В4! Глоео 27. Моогоооточные оггоритыы (В базовом случае интервал равен 9(1)„поскольку строки 1-8 выполняются за константное время.) Это рекуррентное соотношение не подпадает ни под один из случаев основной теоремы, но соответствует условию из упр. 4.6.2. Следовательно, решением рекуррентного соотношения (27.8) является РМ„(п) = 9(182 п). Теперь проанализируем работу РМ1(п) процедуры Р-МЕкггЕ с п элементами, которая оказывается равной 9(п). Поскольку каждый из п элементов должен быть скопирован из массива Т в массив А, мы имеем РМ2(п) = П(п). Таким образом, остается только показать, что РМ2(п) = О(п).
Сначала мы выведем рекуррентное соотношение для работы в наихудшем случае. Бинарный поиск в строке 1О стоит в наихудшем случае 9(!КП), что доминирует нал прочей работой вне рекурсивных вызовов. Что касается последних, то заметим, что хотя рекурсивные вызовы в строках ! 3 и 14 могут сливать различные количества элементов, вместе эти два рекурсивных вызова сливают не более и элементов (в действительности — и — 1 элемент, поскольку Т(д!) не участвует ни в одном из рекурсивных вызовов). Кроме того, как мы видели в ходе анализа интервала, рекурсивный вызов работает не более чем с Зп/4 элементами.
Поэтому мы получаем рекуррентное соотношение РМ1 (п) = РМ!(ап) + РМ2((1 — а)п) + 0(18 п), (27.9) где а лежит в диапазоне 1/4 < а < 3/4, и следует отдавать себе отчет, что фактическое значение а может меняться для каждого уровня рекурсии. Докажем, что рекуррентное соотношение (27.9) имеет решение РМ! = 0(п), с помощью метода подстановки. Будем считать, что РМ2(п) < с2П вЂ” сз 18 п для некоторых положительных констант с! и сз. Подстановка дает РМ2(п) < (сзап — сз 1К(аи)) + (сз(1 — а)п — сз 18((1 — а)и)) + 9(18 и) = сз(а + (1 — а))п — с2(18(ап) + 1К((1 — а)п)) + 9(18 п) = с!и — с2(18 а + 1К п + 1К(1 — а) + 1К п) + 9 (1К п) = с2п с2 18 п — (с2(18п + 18(а(1 а))) 9(1КП)) < с1П вЂ” сз 1Кп, поскольку мы можем выбрать сз достаточно большим, таким, чтобы сз(18П + 18(а(1 — а))) доминировало над членом 9(18п).
Кроме того, можно выбрать с! достаточно большим для удовлетворения базовым условиям рекуррентного соотношения. Поскольку работа РМ2(п) процедуры Р-Мелел равна и П(п), и 0(п)„ мы имеем РМ2(и) = 9(п). Уровень параллелизма процедуры Р-МЕкОЕ равен РМ2(п)/РМ (п) 9(п/18 п). Многопоточная сортировка слиянием Теперь, когда у нас есть неплохо параллелизованная многопоточная процедура слияния, ее можно использовать в многопоточной сортировке слиянием. Эта версия сортировки слиянием подобна рассматривавшейся ранее процедуре ввг Чаеыь 171 Иэбранные аемы МЕКОЕ-БОКт', но в отличие от нее получает в качестве аргумента выходной под- массив В, в котором будут храниться отсортированные результаты.
В частности, вызов Р-Мекое-бокт(А, р, г, В, а) сортирует элементы в А[р .. г] и сохраняет нх в В [а .. в + г — р], Р-Мекое-ЯОкт(А, р, г, В, в) ! и=г — р+1 2 11п ==1 3 В[а] = А[р] 4 е1ае Т[1 .. и] — вновь созданный массив 5 д = [(р+г)/2] 6 д'=о — р+1 7 вратеп Р-МЕКОЕ-БОКт(А, р, о, Т, 1) 8 Р-МекОЕ-БОКт(А,о+1,г,Т,Ч'+1) 9 вупе 10 Р-МЕкоЕ(Т,1,9',9'+1,п,В,а) После вычисления в строке 1 числа и элементов во входном подмассиве А[р .. г] в строках 2 и 3 обрабатывается базовый случай, когда массив содержит только один элемент. В строках 4-6 настраиваются рекурсивный запуск (в строке 7) и вызов (в строке 8), выполняющиеся параллельно.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
