stringtranslate.com

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

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

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

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

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

Введение

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

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

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

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

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

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

Сети вставок и пузырьков

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

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

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

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

Принцип «ноль-один»

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

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

Принцип можно доказать, сначала наблюдая следующий факт о компараторах: когда монотонно возрастающая функция f применяется к входам, т. е. x и y заменяются на f ( x ) и f ( y ) , то компаратор выдает min( f ( x ), f ( y )) = f (min( x , y )) и max( f ( x ), f ( y )) = f (max( x , y )) . Индукцией по глубине сети этот результат можно расширить до леммы, утверждающей, что если сеть преобразует последовательность a 1 , ..., a n в b 1 , ..., b n , она преобразует f ( a 1 ), ..., f ( a n ) в f ( b 1 ), ..., f ( b n ) . Предположим, что некоторые входные данные a 1 , ..., a 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] и существуют с издания 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 , проблема проверки того, является ли сеть-кандидат сортировочной сетью, вероятно, останется сложной для сетей больших размеров, поскольку проблема является co-NP -полной. [17]

Ссылки

  1. ^ abcdefghi Knuth, DE (1997). Искусство программирования, том 3: Сортировка и поиск (Второе издание). Addison–Wesley. стр. 219–247. ISBN 978-0-201-89685-5.Раздел 5.3.4: Сети для сортировки.
  2. ↑ US 3029413, O'Connor, Daniel G. & Nelson, Raymond J., «Система сортировки с n -линейным сортировочным переключателем», опубликовано 10 апреля 1962 г. 
  3. ^ Batcher, KE (1968). Сортировочные сети и их приложения. Труды AFIPS Spring Joint Computer Conference. С. 307–314.
  4. ^ Оуэнс, Дж. Д.; Хьюстон, М.; Любке, Д.; Грин, С.; Стоун, Дж. Э.; Филлипс, Дж. К. (2008). «Вычисления на графических процессорах». Труды IEEE . 96 (5): 879–899. doi :10.1109/JPROC.2008.917757. S2CID  17091128.
  5. ^ abcd Кормен, Томас Х .; Лейзерсон, Чарльз Э .; Ривест, Рональд Л. (1990). Введение в алгоритмы (1-е изд.). MIT Press и McGraw-Hill. ISBN 0-262-03141-8.
  6. ^ Ajtai, M. ; Komlós, J. ; Szemerédi, E. (1983). Сеть сортировки O(n log n) . STOC '83. Труды пятнадцатого ежегодного симпозиума ACM по теории вычислений . стр. 1–9. doi :10.1145/800061.808726. ISBN 0-89791-099-0.
  7. ^ Патерсон, М.С. (1990). «Улучшенные сортировочные сети с глубиной O (log N ) ». Algorithmica . 5 (1–4): 75–92. doi :10.1007/BF01840378. S2CID  2064561.
  8. ^ Гудрич, Майкл (март 2014 г.). «Зигзагообразная сортировка». Труды сорок шестого ежегодного симпозиума ACM по теории вычислений . С. 684–693. arXiv : 1403.2777 . doi :10.1145/2591796.2591830. ISBN 9781450327107. S2CID  947950.
  9. ^ ab Parberry, Ian (1991). "Компьютерная оптимальная нижняя граница глубины для сортировочных сетей с девятью входами" (PDF) . Математическая теория систем . 24 : 101–116. CiteSeerX 10.1.1.712.219 . doi :10.1007/bf02090393. S2CID  7077160. 
  10. ^ abc Кодиш, Майкл; Крус-Филипе, Луис; Элерс, Торстен; Мюллер, Майк; Шнайдер-Камп, Питер (2015). Сортировочные сети: до конца и обратно . arXiv : 1507.01428 . Bibcode : 2015arXiv150701428C.
  11. ^ ab Codish, Michael; Cruz-Filipe, Luís; Frank, Michael; Schneider-Kamp, Peter (2014). Двадцать пять компараторов — оптимальное решение при сортировке девяти входов (и двадцати девяти для десяти) . Proc. Int'l Conf. Tools with AI (ICTAI). стр. 186–193. arXiv : 1405.5754 . Bibcode :2014arXiv1405.5754C.
  12. ^ ab Получено по лемме Ван Вурхиса и значению S (11) = 35.
  13. ^ Элерс, Торстен (февраль 2017 г.). «Слияние почти отсортированных последовательностей дает 24-сортировщик». Information Processing Letters . 118 : 17–20. doi :10.1016/j.ipl.2016.08.005.
  14. ^ аб Доббеларе, Берт. «Сортер Хантер». Гитхаб . Проверено 2 января 2022 г.
  15. ^ Bundala, D.; Závodný, J. (2014). "Optimal Sorting Networks". Language and Automata Theory and Applications . Lecture Notes in Computer Science. Vol. 8370. pp. 236–247. arXiv : 1310.6271 . doi :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.

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