Prawdopodobieństwo działania losowej sieci sortującej

Biorąc pod uwagę $n$ wejścia $x_0, \ldots, x_{n-1}$ , budujemy losową sieć sortująca z $m$ bram poprzez iteracyjne zbieranie dwóch zmiennych $x_i, x_j$ z $i < j$ i dodanie bramę komparatora że swapy nich, jeśli $x_i > x_j$ .

Pytanie 1 : W przypadku stałej $n$ , jak duża musi być $m$ aby sieć poprawnie sortowała z prawdopodobieństwem $> \frac{1}{2}$ ?

Mamy co najmniej dolną granicę $m = \Omega(n^2 \log n)$ ponieważ wejście, które jest poprawnie posortowane, z wyjątkiem tego, że każda kolejna para jest zamieniana, zajmie $\Theta(n^2 \log n^2)$ czasu dla każdej pary, która zostanie wybrana jako komparator . Czy to także górna granica, być może z większą czynników $\log n$ ?

Pytanie 2 : Czy istnieje rozkład bramek komparatora, który osiąga , być może poprzez wybór bliskich komparatorów z większym prawdopodobieństwem? $m = \tilde{O}(n)$

sorting-network

— Geoffrey Irving
źródło

Chyba można dostać

górną granicę

, patrząc na jedno wejście na raz, a następnie granicę związkową, ale to nie jest zbyt ścisłe.

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

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

— daniello

Pomysł na pytanie 2: wybierz sieć sortującą o głębokości

. Na każdym kroku losowo wybierz jedną z bram sieci sortującej i wykonaj to porównanie. Po krokach

wszystkie bramki w pierwszej warstwie zostaną zastosowane. Po kolejnych krokach

zostaną zastosowane wszystkie bramki w drugiej warstwie. Jeśli możesz wykazać, że jest to monotoniczne (wstawienie dodatkowych porównań w środku sieci sortującej nie zaszkodzi), uzyskasz rozwiązanie z

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)$ średnio komparatory. Nie jestem jednak pewien, czy tak naprawdę utrzymuje się monotyczność.

— DW

@DW: Monotoniczność niekoniecznie się utrzymuje. Rozważ sekwencje

Sekwencja

prace;

nie (rozważ dane wejściowe (1, 0, 0)). Chodzi o to, że

\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)$ sortuje wszystkie otrzymywane dane wejściowe oprócz

(patrz tutaj ). W

, to nie może dotrzeć do wejścia

. W

może.

(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'$

— Neal Young,

Rozważ wariant, w którym sieć jest wybierana przez losowe wybranie dwóch sąsiednich zmiennych

na każdym etapie. Teraz obowiązuje monotoniczność (ponieważ sąsiednie zamiany nie powodują inwersji). Zastosuj pomysł @ DW do sieci sortowania nieparzystych parzystych , która ma

rund: w nieparzystych rundach porównuje wszystkie sąsiednie pary, gdzie

jest nieparzysta, w parzystych rundach porównuje wszystkie sąsiednie pary, w których

jest parzyste. Whp losowa sieć jest poprawna w porównaniach

, ponieważ „obejmuje” tę sieć. (Czy coś mi brakuje?)

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)$

— Neal Young

Monotoniczność sąsiednich sieci: Biorąc pod uwagę

, dla

zdefiniuj

. Powiedz

jeśli

(

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$ ). Napraw dowolne porównanie "

x_{i} < x_{i + 1}

$x_i < x_{i+1}$ ”. Niech

pochodzą z i

robiąc tego porównania. Zastrzeżenie 1. i . Zastrzeżenie 2: jeśli , to . Następnie pokaż indukcyjnie: jeśli

jest wynikiem sekwencji porównania

na wejściu

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$ , and

y^{'}

$y'$ is the result of super-sequence

s^{'}

$s'$ of

s

$s$ on

x

$x$ , then

y^{'} ⪯ y

$y' \preceq y$ . So if

y

$y$ is sorted, so is

y^{'}

$y'$ .

— Neal Young

Here's some empirical data for question 2, based on D.W.'s idea applied to bitonic sort. For $n$ variables, choose $j - i = 2^k$ with probability proportional to $\lg n - k$ , then select $i$ uniformly at random to get a comparator $(i,j)$ . This matches the distribution of comparators in bitonic sort if $n$ is a power of 2, and approximates it otherwise.

Dla danej nieskończonej sekwencji bramek wyciągniętych z tego rozkładu, możemy przybliżać liczbę bramek wymaganych do uzyskania sieci sortującej, sortując wiele losowych sekwencji bitów. Oto szacunek dla biorąc pod uwagę średnią ponad sekwencji z sekwencjami bitowymi użytymi do przybliżenia liczby: Wygląda na to, że odpowiada , takiej samej złożoności jak sortowanie bitoniczne. Jeśli tak, nie jemy dodatkowego współczynnika ze względu na problem kolektora kuponów napotykający każdą bramę. $n < 200$ $100$ $6400$ $\Theta(n \log^2 n)$ $\log n$

Dla podkreślenia: używam tylko sekwencji bitowych do przybliżenia oczekiwanej liczby bramek, a nie . Średnia wymagana liczba bramek rośnie wraz z tą liczbą: dla jeśli sekwencji , i , szacunki wynoszą , i . Zatem możliwe jest uzyskanie ostatnich kilku sekwencji zwiększa asymptotyczną złożoność, choć intuicyjnie wydaje się to mało prawdopodobne. $6400$ $2^n$ $n = 199$ $6400$ $64000$ $640000$ $14270 \pm 1069$ $14353 \pm 1013$ $14539 \pm 965$

Edit: Here's a similar plot up to $n = 80$ , but using the exact number of gates (computed via a combination of sampling and Z3). I've switched from power of two $d = j-i$ to arbitrary $d \in [1,\frac{n}{2}]$ with probability proportional to $\frac{\log n - \log d}{d}$ . $\Theta(n \log^2 n)$ still looks plausible.

— Geoffrey Irving
źródło

Nice experiment! There's a different way the coupon collector issue could arise here, though: you're only sampling a small fraction of the

2^{n}

$2^n$ bit sequences needed to verify correctness on all inputs. It seems we can conclude (scientifically, not mathematically of course) from your experiment that a random network of this type and size sorts a random permutation whp. I'd also be curious to see exhaustive

2^{n}

$2^n$ testing on such random networks for all

n

$n$ up to which you're willing to go. (

n = 20

$n=20$ shouldn't be too bad, maybe even

n = 30

$n=30$ depending on what language & hardware you're using).

— Joshua Grochow

It looks the same for exact up to

n = 27

$n = 27$ , but I don’t view that as conclusive.

— Geoffrey Irving

@JoshuaGrochow: I've added exact values up to

n = 80

$n = 80$ .

— Geoffrey Irving

Nice! There does appear to be a growing spread to the exact data though, which perhaps indicates an upper bound with an extra factor of

\log n

$\log n$ ? (That is, if the "spread" is growing at a rate of

\log n

$\log n$ .)

— Joshua Grochow

Yeah, we can't rule out an extra factor. I'd be surprised if it was

\log n

$\log n$ , though, since up at 80 we have

\lg n \approx 6

$\lg n \approx 6$ and the constant is suspiciously close to

1

$1$ otherwise. At this point I think theory has to take over. :)

— Geoffrey Irving