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

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

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

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

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

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

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

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

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

SimpleSortingNetworkFullOperation.svg

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

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

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

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

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

Структура этих двух сортировочных сетей очень похожа. Конструкция двух различных вариантов, которая соединяет вместе компараторы, которые могут выполняться одновременно, показывает, что на самом деле они идентичны. [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 (макс ( х , у )) . По индукции по глубине сети, этот результат может быть расширен до леммы о томчто если сеть преобразует последовательность 1 , ..., п в б 1 , ..., б п , она будет преобразовывать п ( a 1 ), ..., f ( a n ) в f ( b 1 ), ..., f ( b n ) . Предположим, что некоторый вход a1 , ..., a n содержит два элемента a i < a j , и сеть неправильно меняет их местами на выходе. Тогда он также будет неправильно отсортировать f ( a 1 ), ..., f ( a n ) для функции

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

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

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

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

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

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

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

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

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

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

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

Первые шестнадцать глубины оптимальных сетей перечислены в Кнута Искусство программирования , [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]Оптимальная сеть для размера 11 была найдена в декабре 2019 года Яннисом Хардером, который также сделал нижнюю границу для 12 совпадающей с верхней границей. [16]

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

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

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

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

  1. ^ a b c d e f g h Knuth, DE (1997). Искусство программирования, Том 3: Сортировка и поиск (Второе изд.). Аддисон-Уэсли. С. 219–247. ISBN 978-0-201-89685-5. Раздел 5.3.4: Сети для сортировки.
  2. ^ США 3029413 , O'Connor, Daniel G. & Raymond J. Nelson, "Сортировка система с п -линии сортировки переключатель", опубликованном 10 апреля 1962 
  3. ^ Дозаторы, KE (1968). Сортировка сетей и их приложений . Proc. Весенняя совместная компьютерная конференция AFIPS. С. 307–314.
  4. ^ Оуэнс, JD; Хьюстон, М .; Luebke, D .; Green, S .; Стоун, Дж. Э .; Филлипс, JC (2008). «Вычисления на GPU». Труды IEEE . 96 (5): 879–899. DOI : 10.1109 / JPROC.2008.917757 . S2CID 17091128 . 
  5. ^ a b c d Кормен, Томас Х .; Лейзерсон, Чарльз Э .; Ривест, Рональд Л. (1990). Введение в алгоритмы (1-е изд.). MIT Press и McGraw-Hill. ISBN 0-262-03141-8.
  6. ^ Ajtai, М. ; Komlós, J .; Семереди Э. (1983). О (п войти п) сортировка сети . СТОК '83. Материалы пятнадцатого ежегодного симпозиума ACM по теории вычислений . С. 1–9. DOI : 10.1145 / 800061.808726 . ISBN 0-89791-099-0.
  7. ^ Патерсон, MS (1990). «Улучшенная сортировка сетей с глубиной O (log N ) ». Алгоритмика . 5 (1–4): 75–92. DOI : 10.1007 / BF01840378 . S2CID 2064561 . 
  8. ^ Гудрич, Майкл (март 2014). Зигзагообразная сортировка: простой детерминированный алгоритм сортировки без учета данных, работающий за O (n log n) времени . Материалы 46-го ежегодного симпозиума ACM по теории вычислений - STOC '14 . С. 684–693. arXiv : 1403.2777 . DOI : 10.1145 / 2591796.2591830 . ISBN 9781450327107. S2CID  947950 .
  9. ^ a b Парберри, Ян (1991). «Компьютерная оптимальная нижняя граница глубины для сортировочных сетей с девятью входами» (PDF) . Математическая теория систем . 24 : 101–116. CiteSeerX 10.1.1.712.219 . DOI : 10.1007 / bf02090393 . S2CID 7077160 .   
  10. ^ a b c Кодиш, Майкл; Крус-Филипе, Луис; Элерс, Торстен; Мюллер, Майк; Шнайдер-Камп, Питер (2015). Сортировочные сети: до конца и обратно . arXiv : 1507.01428 . Bibcode : 2015arXiv150701428C .
  11. ^ a b Кодиш, Майкл; Крус-Филипе, Луис; Франк, Майкл; Шнайдер-Камп, Питер (2014). Двадцать пять компараторов оптимальны при сортировке девяти входов (и двадцать девять из десяти) . Proc. Международная конф. Инструменты с AI (ICTAI). С. 186–193. arXiv : 1405,5754 . Bibcode : 2014arXiv1405.5754C .
  12. ^ a b Получено по лемме Ван Вурхиса и значению S (11) = 35
  13. ↑ Ehlers, Thorsten (февраль 2017 г.). «Объединение почти отсортированных последовательностей дает 24 сортировщика». Письма об обработке информации . 118 : 17–20. DOI : 10.1016 / j.ipl.2016.08.005 .
  14. ^ a b Dobbelaere, Берт. «СортировщикХантер» . GitHub . Дата обращения 4 июля 2020 .
  15. ^ Bundala, D .; Závodný, J. (2014). Оптимальные сортировочные сети . Язык и теория автоматов и приложения . Конспект лекций по информатике. 8370 . С. 236–247. arXiv : 1310,6271 . DOI : 10.1007 / 978-3-319-04921-2_19 . ISBN 978-3-319-04920-5. S2CID  16860013 .
  16. ^ Сложнее, Яннис. "sortnetopt" . GitHub . Проверено 7 декабря 2019 .
  17. ^ Парберри, Ян (1991). О вычислительной сложности верификации оптимальной сортировочной сети . Proc. PARLE '91: Параллельные архитектуры и языки в Европе, Том I: Параллельные архитектуры и алгоритмы, Эйндховен, Нидерланды . С. 252–269.
  • Angel, O .; Холройд, AE; Ромик, Д .; Вираг, Б. (2007). «Сети случайной сортировки». Успехи в математике . 215 (2): 839–868. arXiv : math / 0609538 . DOI : 10.1016 / j.aim.2007.05.019 .

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

  • Сортировочные сети
  • ГЛАВА 28: СОРТИРОВОЧНЫЕ СЕТИ
  • Сортировочные сети
  • Инструмент для создания и построения графиков сортировочных сетей
  • Сортировочные сети и алгоритм END
  • Липтон, Ричард Дж .; Риган, Кен (24 апреля 2014 г.). «Галактические сортировочные сети» . Потерянное письмо Гёделя и P = NP .
  • Срок действия сети сортировки