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

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

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

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

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

Вступление

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

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

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

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

SimpleSortingNetworkFullOperation.svg

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

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

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

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

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

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

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

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

Принцип нуля или единицы

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

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

Принцип может быть подтвержден, сначала наблюдая следующий факт о компараторах: когда монотонно возрастающий функция ж применяется ко входам, т.е. Икс и у заменены на ж(Икс) и ж(у), то компаратор выдает мин (ж(Икс), ж(у)) = ж(мин (Икс, у)) и Максимум(ж(Икс), ж(у)) = ж(Максимум(Икс, у)). К индукция на глубине сети этот результат может быть расширен до лемма заявляя, что если сеть преобразует последовательность а1, ..., ап в б1, ..., бп, это преобразует ж(а1), ..., ж(ап) в ж(б1), ..., ж(бп). Предположим, что какой-то ввод а1, ..., ап содержит два предмета ая < аj, и сеть неправильно меняет их местами на выходе. Тогда он также будет неправильно сортировать ж(а1), ..., ж(ап) для функции

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

Построение сортировочных сетей

Существуют различные алгоритмы построения сортировочных сетей глубины. О(бревно2 п) (отсюда размер О(п бревно2 п)) Такие как Сортировка по четным и нечетным дозаторам, битоническая сортировка, Сортировка оболочки, а Сеть попарной сортировки. Эти сети часто используются на практике.

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

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

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

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

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

п1234567891011121314151617
Глубина[10]013355667788999910
Размер, верхняя граница[11]01359121619252935394551566071
Размер, нижняя граница (если отличается)[12]4347515560

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

п181920212223242526272829303132
Глубина, верхняя граница[10][13][14]111111121212121313141414141414
Глубина, нижняя граница[10]101010101010101010101010101010
Размер, верхняя граница[14]778591100107115120132139150155165172180185
Размер, нижняя граница[12]65707580859095100105110115120125130135


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

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

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

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

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

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

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

внешняя ссылка