Kemungkinan jaringan sortir acak berfungsi

Diberikan $n$ input $x_0, \ldots, x_{n-1}$ , kami membangun jaringan sortir acak dengan gerbang dengan secara iteratif memilih dua variabel dengan dan menambahkan gerbang komparator yang menukar mereka jika . $m$ $x_i, x_j$ $i < j$ $x_i > x_j$

Pertanyaan 1 : Untuk tetap , berapa besar harus untuk jaringan untuk mengurutkan dengan benar dengan probabilitas ? $n$ $m$ $> \frac{1}{2}$

Kami memiliki setidaknya batas bawah karena input yang diurutkan dengan benar, kecuali bahwa setiap pasangan berurutan akan bertukar waktu untuk setiap pasangan menjadi dipilih sebagai pembanding. Apakah itu juga batas atas, mungkin dengan lebih banyak faktor ? $m = \Omega(n^2 \log n)$ $\Theta(n^2 \log n^2)$ $\log n$

Pertanyaan 2 : Apakah ada distribusi gerbang pembanding yang mencapai , mungkin dengan memilih pembanding dekat dengan probabilitas lebih tinggi? $m = \tilde{O}(n)$

sorting-network Geoffrey Irving
sumber

Saya kira salah satu bisa mendapatkan

atas terikat dengan melihat satu input pada satu waktu dan melompat-lompat maka serikat pekerja, tapi itu suara jauh dari ketat.

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

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

daniello

Ide untuk Pertanyaan 2: pilih jaringan sortir kedalaman

. Pada setiap langkah, pilih secara acak salah satu gerbang jaringan penyortiran, dan lakukan perbandingan itu. Setelah

langkah, semua gerbang di lapisan pertama akan diterapkan. Setelah langkah

, semua gerbang di lapisan kedua akan diterapkan. Jika Anda dapat menunjukkan bahwa ini monoton (menyisipkan perbandingan ekstra di tengah jaringan penyortiran tidak ada salahnya), Anda akan mendapatkan solusi dengan

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)$ komparator total rata-rata. Namun, saya tidak yakin apakah kebersamaan benar-benar berlaku.

@DW: Monotonitas tidak selalu berlaku. Pertimbangkan urutan

Urutan

karya;

tidak (pertimbangkan input (1, 0, 0)). Idenya adalah bahwa

\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)$ macam input apa pun yang diterimanya kecuali

(lihat di sini ). Dalam

, input itu tidak dapat mencapai

. Dalam

itu bisa.

(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

Pertimbangkan varian di mana jaringan dipilih dengan memilih dua variabel yang berdekatan

secara acak di setiap langkah. Sekarang monotonitas berlaku (karena swap yang berdekatan tidak membuat inversi). Terapkan ide @ DW ke jaringan sorting ganjil-genap , yang memiliki

putaran: dalam ganjil ronde ini membandingkan semua pasangan yang berdekatan di mana

ganjil, dalam ronde genap membandingkan semua pasangan yang berdekatan di mana

genap. Whp jaringan acak benar dalam perbandingan

, karena "termasuk" jaringan ini. (Atau aku melewatkan sesuatu?)

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

Monotonicity of adjacent networks: Given

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

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

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

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

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

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

a ⪯ b

$a\preceq b$ if

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

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

\forall j

$\forall j$ ). Fix any comparison "

x_{i} < x_{i + 1}

$x_i < x_{i+1}$ ". Let

a^{'}

$a'$ and

b^{'}

$b'$ come from

a

$a$ and

b

$b$ by doing that comparison. Claim 1. $a' \preceq a$ and $b' \preceq b$ . Claim 2: if $a\preceq b$ , then $a' \preceq b'$ . Then show inductively: if

y

$y$ is the result of comparison sequence

s

$s$ on input

x

$x$ , Dan

adalah hasil dari super-urutan

dari

pada

, maka

. Jadi jika

diurutkan, begitu juga

y^{'}

$y'$

s^{'}

$s'$

s

$s$

x

$x$

y^{'} ⪯ y

$y' \preceq y$

y

$y$

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.

Untuk urutan gerbang tanpa batas tertentu yang ditarik dari distribusi ini, kami dapat memperkirakan jumlah gerbang yang diperlukan untuk mendapatkan jaringan sortir dengan mengurutkan banyak urutan bit acak. Inilah perkiraan untuk mengambil rata-rata lebih dari urutan gerbang dengan urutan bit yang digunakan untuk mendekati penghitungan: Tampaknya cocok dengan , kompleksitas yang sama dengan jenis bitonic. Jika demikian, kita tidak makan tambahan faktor karena masalah kolektor kupon datang di setiap gerbang. $n < 200$ $100$ $6400$ $\Theta(n \log^2 n)$ $\log n$

Untuk menekankan: Saya hanya menggunakan urutan bit untuk memperkirakan jumlah gerbang yang diharapkan, bukan . Gerbang yang diperlukan rata-rata naik dengan angka itu: untuk jika saya menggunakan urutan , , dan perkiraannya adalah , , dan . Dengan demikian, mungkin mendapatkan beberapa urutan terakhir akan meningkatkan kompleksitas asimptotik, meskipun secara intuitif rasanya tidak mungkin. $6400$ $2^n$ $n = 199$ $6400$ $64000$ $640000$ $14270 \pm 1069$ $14353 \pm 1013$ $14539 \pm 965$

Sunting : Berikut plot yang sama hingga , tetapi menggunakan jumlah gerbang yang tepat (dihitung melalui kombinasi sampling dan Z3). Saya telah beralih dari kekuatan dua ke sembarang $n = 80$ $d = j-i$ dengan probabilitas sebanding dengan $d \in [1,\frac{n}{2}]$ . masih terlihat masuk akal. $\frac{\log n - \log d}{d}$ $\Theta(n \log^2 n)$

Geoffrey Irving
sumber

Eksperimen yang bagus! Namun, ada cara berbeda yang dapat timbul masalah pengumpul kupon: Anda hanya mengambil sampel sebagian kecil dari urutan

bit yang diperlukan untuk memverifikasi kebenaran pada semua input. Tampaknya kita dapat menyimpulkan (secara ilmiah, tentu saja tidak secara matematis) dari percobaan Anda bahwa jaringan acak jenis dan ukuran ini mengurutkan permutasi acak whp. Saya juga akan penasaran untuk melihat lengkap

pengujian pada jaringan acak seperti untuk semua

sampai dengan yang Anda bersedia untuk pergi. (

tidak boleh terlalu buruk, bahkan mungkin

tergantung pada bahasa & perangkat keras apa yang Anda gunakan).

2^{n}

$2^n$

2^{n}

$2^n$

n

$n$

n = 20

$n=20$

n = 30

$n=30$

Joshua Grochow

Kelihatannya sama persis hingga

, tapi saya tidak menganggapnya konklusif.

n = 27

$n = 27$

Geoffrey Irving

@ JoshuaGrochow: Saya telah menambahkan nilai yang tepat hingga

n = 80

$n = 80$

Geoffrey Irving

Bagus! Tampaknya ada penyebaran yang berkembang ke data yang tepat, yang mungkin menunjukkan batas atas dengan faktor tambahan

? (Yaitu, jika "spread" tumbuh pada tingkat

\log n

$\log n$

\log n

$\log n$

Joshua Grochow

Ya, kami tidak bisa mengesampingkan faktor tambahan. Saya akan terkejut jika

, karena sejak 80 kita memiliki

dan konstanta curiga mendekati

jika tidak. Pada titik ini saya pikir teori harus mengambil alih. :)

\log n

$\log n$

\lg n \approx 6

$\lg n \approx 6$

1

$1$

Geoffrey Irving

Kemungkinan jaringan sortir acak berfungsi

Jawaban: