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

Учитывая входов , мы строим сеть случайной сортировки с воротами, итеративно выбирая две переменные с и добавляя вентиль компаратора, который меняет их, если . $n$ $x_0, \ldots, x_{n-1}$ $m$ $x_i, x_j$ $i < j$ $x_i > x_j$

Вопрос 1 : Для фиксированного , насколько большим должно быть , чтобы сеть правильно сортировала с вероятностью ? $n$ $m$ $> \frac{1}{2}$

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

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

sorting-network Джеффри Ирвинг
источник

Я думаю, что можно получить верхнюю границу , посмотрев на один вход за раз, а затем ограничивающий объединение, но это звучит далеко не точно.

O (n^{3} l o g^{O (1)})

$O(n^3log^{O(1)})$

Даниелло

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

O (\log^{2} n)

$O(\log^2 n)$

\tilde{O} (n)

$\tilde{O}(n)$

\tilde{O} (n)

$\tilde{O}(n)$

\tilde{O} (n)

$\tilde{O}(n)$

@DW: монотонность не обязательно держится. Рассмотрим последовательности Sequence works; нет (рассмотрим ввод (1, 0, 0)). Идея состоит в том, что сортирует любые входные данные, кроме (см. Здесь ). В , этот вход не может достичь . В это может.

\begin{array}{rcl} s & = & (x_{1}, x_{2}), (x_{0}, x_{2}), (x_{0}, x_{1}); \\ s^{'} & = & (x_{1}, x_{2}), (x_{0}, x_{1}), (x_{0}, x_{2}), (x_{0}, x_{1}) . \end{array}

$\begin{eqnarray*} s &=&(x_1, x_2), (x_0, x_2), (x_0, x_1);\\ s'&=&(x_1, x_2), \mathbf{(x_0, x_1)}, (x_0, x_2), (x_0, x_1).\end{eqnarray*}$

s

$s$

s^{'}

$s'$

(x_{0}, x_{2}), (x_{0}, x_{1})

$(x_0, x_2), (x_0, x_1)$

(0, 1, 0)

$(0, 1, 0)$

s

$s$

(x_{0}, x_{2}), (x_{0}, x_{1})

$(x_0, x_2), (x_0, x_1)$

s^{'}

$s'$

Нил Янг

Рассмотрим вариант, в котором сеть выбирается путем случайного выбора двух смежных переменных на каждом шаге. Теперь монотонность сохраняется (поскольку смежные свопы не создают инверсий). Примените идею @ DW к нечетно-четной сети сортировки , которая имеет раундов: в нечетных раундах он сравнивает все соседние пары, где нечетно, в четных раундах он сравнивает все соседние пары, где четно. Whp случайная сеть верна в сравнениях, так как она «включает» эту сеть. (Или я что-то упустил?)

x_{i}, x_{i + 1}

$x_i, x_{i+1}$

n

$n$

i

$i$

i

$i$

O (n^{2} \log n)

$O(n^2\log n)$

Нил Янг

Монотонность смежных сетей: Для , для определите . Скажите если ( ). Исправьте любое сравнение " ". Пусть и из и , выполняя это сравнение. 1. и . 2: если , то . Тогда покажите индуктивно: если

a, b \in {0, 1}^{n}

$a, b\in\{0,1\}^n$

j \in {0, 1, \dots, n}

$j\in\{0,1,\ldots,n\}$

s_{j} (a) = \sum_{i = 1}^{j} a_{i}

$s_j(a) = \sum_{i=1}^j a_i$

a ⪯ b

$a\preceq b$

s_{j} (a) \leq s_{j} (b)

$s_j(a) \le s_j(b)$

\forall j

$\forall j$

x_{i} < x_{i + 1}

$x_i < x_{i+1}$

a^{'}

$a'$

b^{'}

$b'$

a

$a$

b

$b$ $a' \preceq a$ $b' \preceq b$ $a\preceq b$ $a' \preceq b'$

y

$y$ является результатом сравнения последовательностей на входе и является результатом супер-последовательности из на , то . Так что, если отсортировано, то .

s

$s$

x

$x$

y^{'}

$y'$

s^{'}

$s'$

s

$s$

x

$x$

y^{'} ⪯ y

$y' \preceq y$

y

$y$

y^{'}

$y'$

Нил Янг

Ответы:

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

Для заданной бесконечной последовательности вентилей, извлеченных из этого распределения, мы можем приблизить число вентилей, необходимых для получения сети сортировки, путем сортировки множества случайных битовых последовательностей. Вот эта оценка для с учетом среднего значения по последовательностям затвора с битными последовательностями, использованными для аппроксимации подсчета: похоже, оно соответствует , такой же сложности, как и битовая сортировка. Если это так, мы не употребляем дополнительный коэффициент из-за проблемы с получением купона через каждые ворота. $n < 200$ $100$ $6400$ $\Theta(n \log^2 n)$ $\log n$

Подчеркнем: я использую только битных последовательностей для аппроксимации ожидаемого количества гейтов, а не . Требуемое среднее число затворов увеличивается с этим числом: для если я использую последовательности , и , оценки составляют , и . Таким образом, получение последних нескольких последовательностей увеличивает асимптотическую сложность, хотя интуитивно это кажется маловероятным. $6400$ $2^n$ $n = 199$ $6400$ $64000$ $640000$ $14270 \pm 1069$ $14353 \pm 1013$ $14539 \pm 965$

Редактировать : вот аналогичный график до , но с использованием точного числа вентилей (вычисленных с помощью комбинации выборки и Z3). Я перешел от степени двух к произвольному с вероятностью, пропорциональной . все еще выглядит правдоподобно. $n = 80$ $d = j-i$ $d \in [1,\frac{n}{2}]$ $\frac{\log n - \log d}{d}$ $\Theta(n \log^2 n)$

Джеффри Ирвинг
источник

Хороший эксперимент! Однако здесь может возникнуть проблема с сборщиком купонов: вы выбираете только небольшую часть из

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

тестирование в таких случайных сетях для всех

до которых вы готовы пойти. (

не должно быть слишком плохим, возможно даже

зависимости от того, какой язык и оборудование вы используете).

2^{n}

$2^n$

2^{n}

$2^n$

n

$n$

n = 20

$n=20$

n = 30

$n=30$

Джошуа Грохов

Это выглядит одинаково для точных значений до

, но я не считаю это убедительным.

n = 27

$n = 27$

Джеффри Ирвинг

@JoshuaGrochow: я добавил точные значения до

n = 80

$n = 80$

Джеффри Ирвинг

Ницца! По-видимому, существует растущий разброс к точным данным, что, возможно, указывает на верхнюю границу с дополнительным коэффициентом

? (То есть, если «спрэд» растет со скоростью

\log n

$\log n$

\log n

$\log n$

Джошуа Грохов

Да, мы не можем исключить дополнительный фактор. Я был бы удивлен, если бы это был

, так как до 80 у нас есть

а константа подозрительно близка к

противном случае. На данный момент я думаю, что теория должна победить. :)

\log n

$\log n$

\lg n \approx 6

$\lg n \approx 6$

1

$1$

Джеффри Ирвинг