Бэтчер
Cтраница 1
Бэтчера без операции тдьхтгжия, соответствующей сетям, представленным на рис. 1L5, Эта программа представляет собой компактную к элегантную лбценную ( не испольгуюшую дополнительного пространства оперативной памяти) функцию слияния, которую возможна легче помять, если считать се чередующимся представлением сетей, в то же время прямое дпйазытелмлтю того, что она правильно завершает задачу слияния, сачо но себе очень интересно. [1]
Сортировка Бэтчера прсдстарляст с6ой н точклсги иискодяьцую С ( ] рти ринку U, описанную в раэде ЕС S. TOMh что вместо одной адаптивных реализаций слиянии нз главы 8 она истмиуст нечетко-четкое слияние Бат-тсср ь нрсдсглл ющес собой н адаптийное нисходящее рекурсивное слияние. [2]
Сети Бэтчера были первым более-менее приемлемым решением этой задачи, а некоторые исследователи даже полагали, что сети Бэтчера оптимальны. Сети слияния Бэтчера оптимальны, так что любая сеть сортировки с существенно меньшим числом компараторов может быть построена только в рамках подхода, отличного от рекурсивной сортировки слиянием. [3]
Сортировка Бэтчера представляет собой в точности нисходящую сортировку слиянием, описанную в разделе 8.3; различие состоит лишь в том, что вместо одной из адаптивных реализаций слияний из главы 8 она использует нечетно-четное слияние Бэтчера, представляющее собой неадаптивное нисходящее рекурсивное слияние. Программа 8.3 сама по себе вообще не выполняет доступа к данным, так что из факта использования нами неадаптивного слияния следует, что и сама сортировка неадаптивная. [4]
Параллельное слияние Бэтчера состоит из ряда многоэтапных просмотров. Предварительные просмотры размещают элементы так, чтобы на последнем этапе последнего просмотра ни один элемент не был бы удален более чем на одну позицию от его итогового места. Каждый элемент в течение последнего этапа последнего просмотра может быть упорядочен надлежащим образом путем сравнения ( и, возможно, обмена) с его соседом. На последнем этапе все сравнения непересекающиеся и могут выполняться параллельно. [5]
Лемма 11.3. Сети нечетно-четной сортировки Бэтчера используют приблизительно Ar ( lg7V) 2 / 4 компараторов и могут быть выполнены за ( IgA) / 2 параллельных шагов. [6]
Программа 11.3. является восходящей реализацией слияния Бэтчера без операции тасования, соответствующей сетям, представленным на рис. 11.5. Эта программа представляет собой компактную и элегантную обменную ( не использующую дополнительного пространства оперативной памяти) функцию слияния, которую, возможно, легче понять, если считать ее чередующимся представлением сетей, в то же время прямое доказательство того, что она правильно завершает задачу слияния, само по себе очень интересно. [7]
Если удалить все операции тасования, то для выполнения слияния Бэтчера применительно к нашему примеру потребуется 25 операций слияния-обмена, изображенных на этой диаграмме. [8]
Последняя фаза, когда р равно N, и есть нечетно-четное слияние Бэтчера. Предпоследняя фаза, когда р равно N / 2, есть нечетно-четное слияние с первым каскадом, и все компараторы, которые пересекаются с любой линией, кратной N / 2, удаляются; третья фаза с конца, когда р равно W / 4, есть нечетно-четное слияние с двумя первыми каскадами, а все компараторы, которые пересекаются с любой линией, кратной W / 4, удаляются, и так далее. [9]
Найти 16-линейную сеть сортировки, которая использует меньшее число компараторов, чем сеть Бэтчера. [11]
На рис. 11.11. показаны динамические характеристики как восходящего метода, так и версии нечетно-четного слияния Бэтчера с полным тасованием. [12]
Последняя фаза, когда р равно W, и есть нечет но - четной Слияние Бэтчера. Предпоследняя фаза, когда р равно N / 2, есть нечетно-четное слияние с первым каскадом, и асе компараторы, которые пересекаются с любой линией, крэгной N / 2, удаляются; третьи фаза с конца, когда р равно W / 4, есть нечетно-четное слияние с двумя первыми каскадами, а все компараторы, которые г е pec e каются с любой линией, кратной ЧЧ удаляются, и так далее. [13]
Сети Бэтчера были первым более-менее приемлемым решением этой задачи, а некоторые исследователи даже полагали, что сети Бэтчера оптимальны. Сети слияния Бэтчера оптимальны, так что любая сеть сортировки с существенно меньшим числом компараторов может быть построена только в рамках подхода, отличного от рекурсивной сортировки слиянием. [14]
Сортировка Бэтчера представляет собой в точности нисходящую сортировку слиянием, описанную в разделе 8.3; различие состоит лишь в том, что вместо одной из адаптивных реализаций слияний из главы 8 она использует нечетно-четное слияние Бэтчера, представляющее собой неадаптивное нисходящее рекурсивное слияние. Программа 8.3 сама по себе вообще не выполняет доступа к данным, так что из факта использования нами неадаптивного слияния следует, что и сама сортировка неадаптивная. [15]
Страницы: 1 2