Вероятность того, что сеть случайной сортировки работает

14

Учитывая входов , мы строим сеть случайной сортировки с воротами, итеративно выбирая две переменные с и добавляя вентиль компаратора, который меняет их, если .x 0 , , x n - 1 m x i , x j i < j x i > x jnx0,,xn1mxi,xji<jxi>xj

Вопрос 1 : Для фиксированного , насколько большим должно быть , чтобы сеть правильно сортировала с вероятностью ?m > 1nm>12

У нас есть по крайней мере нижняя граница поскольку вход, который правильно отсортирован, за исключением того, что каждая последовательная пара поменялась местами, займет \ Theta (n ^ 2 \ log n ^ 2) время для каждого пара будет выбрана в качестве компаратора. Это также верхняя граница, возможно, с большим количеством \ log n факторов?Θ ( n 2 log n 2 ) log nm=Ω(n2logn)Θ(n2logn2)logn

Вопрос 2 : Существует ли распределение компараторов, которое достигает m=O~(n) , возможно, путем выбора близких компараторов с более высокой вероятностью?

Джеффри Ирвинг
источник
1
Я думаю, что можно получить верхнюю границу , посмотрев на один вход за раз, а затем ограничивающий объединение, но это звучит далеко не точно. O(n3logO(1))
Даниелло
2
Идея для вопроса 2: выбрать сортировочную сеть глубины . На каждом шаге случайным образом выбирайте один из вентилей сортировочной сети и выполняйте это сравнение. После шагов все ворота в первом слое будут применены. После еще одного шага все ворота второго уровня будут применены. Если вы можете показать, что это монотонно (вставка дополнительных сравнений в середину сортировочной сети не повредит), вы получите решение с компараторами в среднем в среднем. Я не уверен, действительно ли монотичность сохраняется. ~ О ( п ) ~ О ( п ) ~ О ( п )O(log2n)O~(n)O~(n)O~(n)
DW
2
@DW: монотонность не обязательно держится. Рассмотрим последовательности Sequence works; нет (рассмотрим ввод (1, 0, 0)). Идея состоит в том, что сортирует любые входные данные, кроме (см. Здесь ). В , этот вход не может достичь . В это может. ss(x0,x2),(x0,x1)(0,1,0)
s=(x1,x2),(x0,x2),(x0,x1);s=(x1,x2),(x0,x1),(x0,x2),(x0,x1).
ss(x0,x2),(x0,x1)(0,1,0)( x 0 , x 2 ) , ( x 0 , x 1 ) s s(x0,x2),(x0,x1)s
Нил Янг
3
Рассмотрим вариант, в котором сеть выбирается путем случайного выбора двух смежных переменных на каждом шаге. Теперь монотонность сохраняется (поскольку смежные свопы не создают инверсий). Примените идею @ DW к нечетно-четной сети сортировки , которая имеет раундов: в нечетных раундах он сравнивает все соседние пары, где нечетно, в четных раундах он сравнивает все соседние пары, где четно. Whp случайная сеть верна в сравнениях, так как она «включает» эту сеть. (Или я что-то упустил?)xi,xi+1i i O ( n 2 log n )niiO(n2logn)
Нил Янг
2
Монотонность смежных сетей: Для , для определите . Скажите если ( ). Исправьте любое сравнение " ". Пусть и из и , выполняя это сравнение. 1. и . 2: если , то . Тогда покажите индуктивно: если j { 0 , 1 , , n } s j ( a ) = j i = 1 a i a s b s j ( a ) s j ( b ) j x i < x i + 1 a b a,b{0,1}nj{0,1,,n}sj(a)=i=1jaiabsj(a)sj(b)jxi<xi+1abбab b baabb a b ababyявляется результатом сравнения последовательностей на входе и является результатом супер-последовательности из на , то . Так что, если отсортировано, то . x y s s x y y y y sxyssxyyyy
Нил Янг

Ответы:

3

Вот некоторые эмпирические данные для вопроса 2, основанные на идее DW, примененной к битовой сортировке. Для переменных выберите с вероятностью, пропорциональной , затем выберите случайным образом равномерно, чтобы получить компаратор . Это соответствует распределению компараторов в битонном виде, если - степень 2, и аппроксимирует его в противном случае.j - i = 2 k lg n - k i ( i , j ) nnji=2klgnki(i,j)n

Для заданной бесконечной последовательности вентилей, извлеченных из этого распределения, мы можем приблизить число вентилей, необходимых для получения сети сортировки, путем сортировки множества случайных битовых последовательностей. Вот эта оценка для с учетом среднего значения по последовательностям затвора с битными последовательностями, использованными для аппроксимации подсчета: похоже, оно соответствует , такой же сложности, как и битовая сортировка. Если это так, мы не употребляем дополнительный коэффициент из-за проблемы с получением купона через каждые ворота.100 6400 Θ ( n log 2 n ) log nn<2001006400Приблизительное количество воротΘ(nlog2n)logn

Подчеркнем: я использую только битных последовательностей для аппроксимации ожидаемого количества гейтов, а не . Требуемое среднее число затворов увеличивается с этим числом: для если я использую последовательности , и , оценки составляют , и . Таким образом, получение последних нескольких последовательностей увеличивает асимптотическую сложность, хотя интуитивно это кажется маловероятным.64002nn=19964006400064000014270±106914353±101314539±965

Редактировать : вот аналогичный график до , но с использованием точного числа вентилей (вычисленных с помощью комбинации выборки и Z3). Я перешел от степени двух к произвольному с вероятностью, пропорциональной . все еще выглядит правдоподобно.n=80d=jid[1,n2]lognlogddΘ(nlog2n)

Точные номера ворот

Джеффри Ирвинг
источник
2
Хороший эксперимент! Однако здесь может возникнуть проблема с сборщиком купонов: вы выбираете только небольшую часть из битных последовательностей, необходимых для проверки правильности на всех входах. Кажется, мы можем сделать вывод (с научной точки зрения, а не математически, конечно) из вашего эксперимента, что случайная сеть такого типа и размера сортирует случайную перестановку whp. Мне также было бы любопытно увидеть исчерпывающее 2 n тестирование в таких случайных сетях для всех n, до которых вы готовы пойти. ( n = 20 не должно быть слишком плохим, возможно даже n = 30 в зависимости от того, какой язык и оборудование вы используете).2n2nnn=20n=30
Джошуа Грохов
1
Это выглядит одинаково для точных значений до , но я не считаю это убедительным. n=27
Джеффри Ирвинг
1
@JoshuaGrochow: я добавил точные значения до . n=80
Джеффри Ирвинг
1
Ницца! По-видимому, существует растущий разброс к точным данным, что, возможно, указывает на верхнюю границу с дополнительным коэффициентом ? (То есть, если «спрэд» растет со скоростью log n .)lognlogn
Джошуа Грохов
1
Да, мы не можем исключить дополнительный фактор. Я был бы удивлен, если бы это был , так как до 80 у нас есть lg n 6, а константа подозрительно близка к 1 в противном случае. На данный момент я думаю, что теория должна победить. :)lognlgn61
Джеффри Ирвинг