Jump to content

Сортировочная сеть

Простая сортировочная сеть, состоящая из четырех проводов и пяти разъемов.

В информатике сети компараторов представляют собой абстрактные устройства, состоящие из фиксированного количества «проводов», несущих значения, и модулей компаратора, которые соединяют пары проводов, меняя местами значения на проводах, если они не находятся в желаемом порядке. Такие сети обычно предназначены для выполнения сортировки фиксированного количества значений, и в этом случае они называются сетями сортировки .

Сети сортировки отличаются от обычных сравнений тем, что они не способны обрабатывать сколь угодно большие входные данные и тем, что их последовательность сравнений устанавливается заранее, независимо от результатов предыдущих сравнений. Для сортировки большего количества ресурсов необходимо построить новые сортировочные сети. Эта независимость последовательностей сравнения полезна для параллельного выполнения и для аппаратной реализации . Несмотря на простоту сортировочных сетей, их теория удивительно глубока и сложна. Сортировочные сети были впервые изучены примерно в 1954 году Армстронгом, Нельсоном и О'Коннором. [1] который впоследствии запатентовал эту идею. [2]

Сортировочные сети могут быть реализованы как аппаратно , так и программно . Дональд Кнут описывает, как компараторы двоичных целых чисел могут быть реализованы как простые электронные устройства с тремя состояниями. [1] Бэтчер в 1968 году предложил использовать их для построения коммутационных сетей для компьютерного оборудования, заменив как шины , так и более быстрые, но более дорогие перекрестные коммутаторы . [3] С 2000-х годов сортировочные сети (особенно битоническая сортировка слиянием ) используются сообществом GPGPU для построения алгоритмов сортировки для работы на графических процессорах . [4]

Введение [ править ]

Демонстрация работы компаратора в сортировочной сети.

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

В формуле, если верхний провод несет x , а нижний провод несет y , то после попадания в компаратор провода несут и соответственно, поэтому пара значений сортируется. [5] : 635  Сеть проводов и компараторов, которая правильно сортирует все возможные входные данные в порядке возрастания, называется сортировочной сетью или концентратором Крускала. Отражая сеть, также можно отсортировать все входные данные в порядке убывания.

Полная работа простой сортировочной сети показана ниже. Очевидно, почему эта сортировочная сеть правильно сортирует входные данные; обратите внимание, что первые четыре компаратора «опускают» наибольшее значение вниз и «поднимают» наименьшее значение вверх. Последний компаратор сортирует два средних провода.

и Глубина эффективность

Эффективность сортировочной сети можно измерить ее общим размером, то есть количеством компараторов в сети, или ее глубиной , определяемой (неформально) как наибольшее количество компараторов, с которыми любое входное значение может столкнуться на своем пути через сеть. . Учитывая, что сортировочные сети могут выполнять определенные сравнения параллельно (представленные в графическом обозначении компараторами, лежащими на одной вертикальной линии), и предполагая, что все сравнения занимают единицу времени, можно увидеть, что глубина сети равна количество временных шагов, необходимых для его выполнения. [5] : 636–637 

Сети вставки и пузыря [ править ]

Мы можем легко построить сеть любого размера рекурсивно, используя принципы вставки и выбора. Предполагая, что у нас есть сортировочная сеть размера n , мы можем построить сеть размера n + 1 , «вставив» дополнительное число в уже отсортированную подсеть (используя принцип, лежащий в основе сортировки вставками ). Мы также можем добиться того же самого, сначала «выбрав» наименьшее значение из входных данных, а затем рекурсивно отсортировав оставшиеся значения (используя принцип, лежащий в основе пузырьковой сортировки ).

Сортировочная сеть, построенная рекурсивно, которая сначала опускает наибольшее значение вниз, а затем сортирует оставшиеся провода. На основе пузырьковой сортировки
Сортировочная сеть, построенная рекурсивно, которая сначала сортирует первые n проводов, а затем вставляет оставшееся значение. На основе сортировки вставками

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

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

Сеть вставки (или, что то же самое, пузырьковая сеть) имеет глубину 2 n - 3 , [1] где n — количество значений. Это лучше, чем время O ( n log n ), необходимое машинам с произвольным доступом , но оказывается, что существуют гораздо более эффективные сортировочные сети с глубиной всего O (log 2 n ) , как описано ниже .

Принцип ноль-один [ править ]

Хотя доказать достоверность некоторых сортировочных сетей (например, пузырькового сортировщика) легко, это не всегда так просто. Есть н ! перестановки чисел в n -проводной сети, и проверка всех из них заняла бы значительное количество времени, особенно когда n велико. Количество тест-кейсов можно существенно сократить, до 2-х. н , используя так называемый принцип нуля-единицы. Хотя это все еще экспоненциально, это меньше, чем n ! для всех n ≥ 4 , и разница довольно быстро растет с увеличением n .

Принцип «ноль-единица» гласит, что если сортировочная сеть может правильно отсортировать все 2 н последовательности нулей и единиц, то это справедливо и для произвольных упорядоченных входных данных. Это не только радикально сокращает количество тестов, необходимых для проверки достоверности сети, но и очень полезно при создании многих конструкций сортировочных сетей.

Этот принцип можно доказать, сначала наблюдая следующий факт о компараторах: когда монотонно возрастающая функция f к входным сигналам применяется , т. е. x и y заменяются на f ( x ) и f ( y ) , тогда компаратор выдает min( ж ( Икс ), ж ( у )) = ж ( мин ( Икс , У )) и Макс ( Ж ( Икс ), Ж ( У )) = Ж ( Макс ( Икс , У )) . Индукцией утверждающей по глубине сети этот результат можно расширить до леммы, , что если сеть преобразует последовательность a 1 , ..., an n в b 1 , ..., bn , она преобразует f ( a 1 ), ..., f ( a n ) в f ( b 1 ), ..., f ( b n ) . Предположим, что некоторые входные данные a 1 , ..., an n содержат два элемента a i < a j , и сеть неправильно меняет их местами на выходе. Тогда он также будет неправильно сортировать f ( a 1 ), ..., f ( a n ) для функции

Эта функция монотонна, поэтому в качестве противоположения мы имеем принцип ноль-единица . [5] : 640–641 

Построение сортировочных сетей [ править ]

Существуют различные алгоритмы построения сортировочных сетей глубины O (log 2 n ) (следовательно, размер O ( n log 2 n ) ), такие как нечетно-четная сортировка Бэтчера слиянием , битоническая сортировка , сортировка Шелла и сеть парной сортировки . Эти сети часто используются на практике.

Также возможно построить сети глубины O (log n ) (следовательно, размера O ( n log n ) ) с использованием конструкции, называемой сетью AKS , в честь ее первооткрывателей Айтаи , Комлоша и Семереди . [6] Несмотря на важное теоретическое открытие, сеть AKS имеет очень ограниченное практическое применение из-за большой линейной константы, скрытой за обозначением Big-O . [5] : 653  Частично это связано с построением графа-расширителя .

Упрощенная версия сети AKS была описана Патерсоном в 1990 году, который отметил, что «константы, полученные для границы глубины, все еще не позволяют конструкции иметь практическую ценность». [7]

Более поздняя конструкция, называемая зигзагообразной сортировочной сетью размера O ( n log n ), была обнаружена Гудричем в 2014 году. [8] Хотя его размер намного меньше, чем у сетей AKS, его глубина O ( n log n ) делает его непригодным для параллельной реализации.

Оптимальные сортировочные сети [ править ]

числа входов n Для небольшого фиксированного оптимальные можно построить сети сортировки либо минимальной глубины (для максимально параллельного выполнения), либо минимального размера (количества компараторов). Эти сети можно использовать для повышения производительности более крупных сортировочных сетей, возникающих в результате рекурсивных конструкций, например, Batcher, путем ранней остановки рекурсии и вставки оптимальных сетей в качестве базовых случаев. [9] В следующей таблице суммированы результаты оптимальности для небольших сетей, для которых известна оптимальная глубина:

н 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
Глубина [10] 0 1 3 3 5 5 6 6 7 7 8 8 9 9 9 9 10
Размер, верхняя граница [11] 0 1 3 5 9 12 16 19 25 29 35 39 45 51 56 60 71
Размер, нижняя граница (если отличается) [12] 43 47 51 55 60

Для более крупных сетей в настоящее время неизвестны ни оптимальная глубина, ни оптимальный размер. Известные на данный момент границы представлены в таблице ниже:

н 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32
Глубина, верхняя граница [10] [13] [14] 11 11 11 12 12 12 12 13 13 14 14 14 14 14 14
Глубина, нижняя граница [10] 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10
Размер, верхняя граница [14] 77 85 91 99 107 114 120 131 139 148 155 165 172 180 185
Размер, нижняя граница [12] 65 70 75 80 85 90 95 100 105 110 115 120 125 130 135

Первые шестнадцать сетей с оптимальной глубиной перечислены в « Искусстве компьютерного программирования» Кнута . [1] и существуют с издания 1973 года; однако, хотя оптимальность первых восьми была установлена ​​Флойдом и Кнутом в 1960-х годах, это свойство для последних шести не было доказано до 2014 года. [15] (решения по девятому и десятому делам были приняты в 1991 г. [9] ).

Для входных данных от одного до двенадцати известны минимальные (т.е. оптимальные по размеру) сортировочные сети, а для более высоких значений нижняя граница их размеров S ( n ) может быть получена индуктивно с использованием леммы Ван Вурхиса. [1] (стр. 240): S ( n ) ≥ S ( n - 1) + ⌈log 2 n . Первые десять оптимальных сетей известны с 1969 года, причем первые восемь снова стали известны как оптимальные со времен работ Флойда и Кнута, но оптимальности случаев n = 9 и n = 10 потребовалось время до 2014 года. для определения [11] Оптимальность наименьших известных сортировочных сетей для n = 11 и n = 12 была решена в 2020 году. [16] [1]

Некоторая работа по разработке оптимальной сортировочной сети была проделана с использованием генетических алгоритмов : Д. Кнут упоминает, что наименьшая известная сортировочная сеть для n = 13 была найдена Хьюгом Жюйе в 1995 году «путем моделирования эволюционного процесса генетического разведения». [1] (стр. 226), и что сети сортировки минимальной глубины для n = 9 и n = 11 были найдены Лорен Швиберт в 2001 году «с использованием генетических методов». [1] (с. 229).

Сложность тестирования сортировочных сетей [ править ]

Если P=NP , проблема проверки того, является ли сеть-кандидат сортирующей сетью, вероятно, останется сложной для сетей больших размеров из-за того, что проблема является ко-NP -полной. [17]

Ссылки [ править ]

  1. ^ Jump up to: а б с д и ж г час я Кнут, DE (1997). Искусство компьютерного программирования, Том 3: Сортировка и поиск (второе изд.). Аддисон-Уэсли. стр. 219–247. ISBN  978-0-201-89685-5 . Раздел 5.3.4: Сети сортировки.
  2. ^ США 3029413 , О'Коннор, Дэниел Г. и Нельсон, Рэймонд Дж., «Система сортировки с n -линейным сортировочным переключателем», опубликовано 10 апреля 1962 г.  
  3. ^ Бэтчер, К.Е. (1968). Сортировка сетей и их приложений . Учеб. Весенняя совместная компьютерная конференция AFIPS. стр. 307–314.
  4. ^ Оуэнс, доктор медицинских наук; Хьюстон, М.; Любке, Д.; Грин, С.; Стоун, Дж. Э.; Филлипс, Джей Си (2008). «ГПУ-вычисления». Труды IEEE . 96 (5): 879–899. дои : 10.1109/JPROC.2008.917757 . S2CID   17091128 .
  5. ^ Jump up to: а б с д Кормен, Томас Х .; Лейзерсон, Чарльз Э .; Ривест, Рональд Л. (1990). Введение в алгоритмы (1-е изд.). MIT Press и McGraw-Hill. ISBN  0-262-03141-8 .
  6. ^ Аджтай, М. ; Комлос, Дж .; Семереди, Э. (1983). O (n log n) Сортировочная сеть . СТОК '83. Материалы пятнадцатого ежегодного симпозиума ACM по теории вычислений . стр. 1–9. дои : 10.1145/800061.808726 . ISBN  0-89791-099-0 .
  7. ^ Патерсон, М.С. (1990). «Улучшенные сортировочные сети с глубиной O (log N ) ». Алгоритмика . 5 (1–4): 75–92. дои : 10.1007/BF01840378 . S2CID   2064561 .
  8. ^ Гудрич, Майкл (март 2014 г.). «Зигзагообразная сортировка». Материалы сорок шестого ежегодного симпозиума ACM по теории вычислений . стр. 684–693. arXiv : 1403.2777 . дои : 10.1145/2591796.2591830 . ISBN  9781450327107 . S2CID   947950 .
  9. ^ Jump up to: а б Парберри, Ян (1991). «Нижняя граница оптимальной глубины с помощью компьютера для сортировочных сетей с девятью входами» (PDF) . Теория математических систем . 24 : 101–116. CiteSeerX   10.1.1.712.219 . дои : 10.1007/bf02090393 . S2CID   7077160 .
  10. ^ Jump up to: а б с Кодиш, Майкл; Крус-Филипе, Луис; Элерс, Торстен; Мюллер, Майк; Шнайдер-Камп, Питер (2015). Сортировка сетей: до конца и обратно . arXiv : 1507.01428 . Бибкод : 2015arXiv150701428C .
  11. ^ Jump up to: а б Кодиш, Майкл; Крус-Филипе, Луис; Фрэнк, Майкл; Шнайдер-Камп, Питер (2014). Двадцать пять компараторов оптимально при сортировке девяти входных данных (и двадцать девять для десяти) . Учеб. Международная конференция. Инструменты с ИИ (ICTAI). стр. 186–193. arXiv : 1405.5754 . Бибкод : 2014arXiv1405.5754C .
  12. ^ Jump up to: а б Получено по лемме Ван Вурхиса и значению S (11) = 35.
  13. ^ Элерс, Торстен (февраль 2017 г.). «Объединение почти отсортированных последовательностей дает 24-сортировщик». Письма об обработке информации . 118 : 17–20. дои : 10.1016/j.ipl.2016.08.005 .
  14. ^ Jump up to: а б Доббелэр, Берт. «Сортер Хантер» . Гитхаб . Проверено 2 января 2022 г.
  15. ^ Бундала, Д.; Заводный, Ю. (2014). «Оптимальные сортировочные сети». Теория и приложения языка и автоматов . Конспекты лекций по информатике. Том. 8370. стр. 236–247. arXiv : 1310.6271 . дои : 10.1007/978-3-319-04921-2_19 . ISBN  978-3-319-04920-5 . S2CID   16860013 .
  16. ^ Хардер, Яннис (2020). «Ответ на задачу сортировки Бозе-Нельсона для 11 и 12 каналов». arXiv : 2012.04400 [ cs.DS ].
  17. ^ Парберри, Ян (1991). О вычислительной сложности проверки оптимальной сортировочной сети . Учеб. PARLE '91: Параллельные архитектуры и языки Европы, Том I: Параллельные архитектуры и алгоритмы, Эйндховен, Нидерланды . стр. 252–269.

Внешние ссылки [ править ]

Arc.Ask3.Ru: конец переведенного документа.
Arc.Ask3.Ru
Номер скриншота №: 1d3a344d120b38df19af784df44aac29__1714194720
URL1:https://arc.ask3.ru/arc/aa/1d/29/1d3a344d120b38df19af784df44aac29.html
Заголовок, (Title) документа по адресу, URL1:
Sorting network - Wikipedia
Данный printscreen веб страницы (снимок веб страницы, скриншот веб страницы), визуально-программная копия документа расположенного по адресу URL1 и сохраненная в файл, имеет: квалифицированную, усовершенствованную (подтверждены: метки времени, валидность сертификата), открепленную ЭЦП (приложена к данному файлу), что может быть использовано для подтверждения содержания и факта существования документа в этот момент времени. Права на данный скриншот принадлежат администрации Ask3.ru, использование в качестве доказательства только с письменного разрешения правообладателя скриншота. Администрация Ask3.ru не несет ответственности за информацию размещенную на данном скриншоте. Права на прочие зарегистрированные элементы любого права, изображенные на снимках принадлежат их владельцам. Качество перевода предоставляется как есть. Любые претензии, иски не могут быть предъявлены. Если вы не согласны с любым пунктом перечисленным выше, вы не можете использовать данный сайт и информация размещенную на нем (сайте/странице), немедленно покиньте данный сайт. В случае нарушения любого пункта перечисленного выше, штраф 55! (Пятьдесят пять факториал, Денежную единицу (имеющую самостоятельную стоимость) можете выбрать самостоятельно, выплаичвается товарами в течение 7 дней с момента нарушения.)