Soalan
Diberikan semesta integer tetap dengan kekunci dari 0 hingga U-1, laksanakan Pokok van Emde Boas yang menyokong pemasukan, pemadaman, keahlian, minimum, maksimum, pendahulu, dan pengganti. Terangkan penguraian tinggi dan rendah, struktur ringkasan, pengendalian kelompok kosong, dan sebab operasi mengambil masa O(log log U) dan bukannya O(log U).
Perkara yang diuji oleh penemu duga
- Sama ada anda memahami bahawa Pokok vEB menganggap semesta integer tetap dan operasi bit, jadi ia tidak menggantikan pokok perbandingan secara langsung untuk objek sewenang-wenangnya.
- Sama ada anda boleh mengira indeks kelompok dan ofset dengan betul serta memastikan ringkasan sentiasa peka terhadap kelompok yang tidak kosong.
- Sama ada anda mengendalikan pokok kosong, singleton, kekunci sempadan, pemadaman nilai minimum, dan pembersihan selepas sesuatu kelompok menjadi kosong.
- Sama ada anda boleh menyatakan kekompleksan teori dan kos ruang O(U), kemudian menamakan bila y-fast trie, tatasusunan terisih, atau pokok seimbang biasa lebih diutamakan.
Jawapan model
Katakan U ialah kuasa bagi dua dengan lebar bit w. Setiap nod vEB memiliki sub-semesta bersaiz u dan memecahkan kekunci kepada indeks kelompok tinggi dan ofset rendah. Dalam definisi rekursif biasa, kedua-dua bahagian menggunakan kira-kira separuh daripada bit tersebut, jadi satu nod mempunyai kira-kira sqrt(u) kelompok. Setiap kelompok ialah satu lagi vEB bersaiz sqrt(u), dan ringkasan bersaiz sqrt(u) merekodkan kelompok mana yang tidak kosong.
Nod tersebut juga menyimpan min dan max supaya operasi biasa tidak berulang secara rekursif hingga ke daun. Memasukkan elemen pertama akan menetapkan kedua-dua nilai; pemasukan seterusnya menukar kekunci yang lebih kecil ke dalam min dan memasukkan min lama ke dalam kelompoknya. Pemadaman mesti mengendalikan penyingkiran min atau max, mencari kelompok tidak kosong seterusnya melalui ringkasan, dan mengeluarkan kelompok daripada ringkasan apabila ia menjadi kosong.
Kerehasannya ialah T(u)=T(sqrt(u))+O(1). Punca kuasa dua yang berulang mengurangkan separuh daripada eksponen pada setiap peringkat, jadi kedalamannya ialah O(log log U). Dengan susun atur naif, penunjuk kelompok dan ringkasan merentasi nod rekursif menggunakan ruang O(U). Susun atur jarang mengurangkan pemalar tetapi tidak menghapuskan kebergantungan semesta itu sendiri.
Lakaran pelaksanaan
Pseudokod ini menggunakan high, low, dan index untuk penguraian dan penggabungan semula, tanpa memasukkan kolam memori dan pengesahan argumen.
high(x, bits) = x >> ceil(bits / 2)
low(x, bits) = x & ((1 << floor(bits / 2)) - 1)
index(h, l, bits) = (h << floor(bits / 2)) | l
insert(v, x):
if v.min is empty:
v.min = x; v.max = x; return
if x < v.min:
swap(x, v.min)
if v.bits > 1:
h = high(x, v.bits); l = low(x, v.bits)
if v.cluster[h].min is empty:
insert(v.summary, h)
insert(v.cluster[h], l)
if x > v.max:
v.max = x
successor(v, x):
if v.min is empty or x >= v.max: return empty
if v.bits == 1:
return v.max if v.max > x else empty
if x < v.min: return v.min
h = high(x, v.bits); l = low(x, v.bits)
c = v.cluster[h]
if c is not empty and l < c.max:
return index(h, successor(c, l), v.bits)
next_h = successor(v.summary, h)
if next_h is empty: return empty
return index(next_h, v.cluster[next_h].min, v.bits)Pelaksanaan pemadaman sebenar mesti mengekalkan peraturan kelompok kosong yang simetri. Nod daun boleh menggunakan peta bit kecil atau dua nilai dan bukannya memperuntukkan objek secara rekursif. Tetapkan lebar bit terlebih dahulu, kemudian bandingkan jujukan operasi rawak dengan set teratur supaya keputusan pendahulu dan pengganti adalah selaras.
Perangkap biasa
- Menganggap U sebagai bilangan elemen n dan mendakwa setiap operasi adalah O(log log n). Parameternya ialah saiz semesta U.
- Mengabaikan pembundaran apabila U bukan kuasa bagi dua, menyebabkan high, low, dan index bukan lagi operasi songsang.
- Melaksanakan keahlian dan minimum tetapi tidak pernah mengeluarkan kelompok kosong daripada ringkasan selepas pemadaman.
- Menganggap vEB sentiasa lebih pantas daripada pokok merah-hitam sambil mengabaikan ruang O(U), lokaliti cache, dan taburan kekunci sebenar.
- Memberikan ringkasan struktur rekursif yang sama tanpa menyatakan sempadan semesta dan perwakilan kosongnya.
Pertukaran kekompleksan
Untuk integer kata mesin, semesta yang diketahui, dan beban kerja yang berpusat pada pendahulu dan pengganti, O(log log U) adalah menarik secara teori. Jika U hampir dengan julat perkataan tetapi set itu jarang, susun atur naif membazirkan memori. x-fast atau y-fast trie menjadikan ruang lebih bergantung pada n, dengan kos pencincangan, kerawakan, atau kerumitan pelaksanaan.
Pokok seimbang biasa menyediakan operasi O(log n), ruang O(n), dan semantik lelaran yang lebih mudah. Tatasusunan terisih sesuai untuk set statik dan pertanyaan kelompok. Dalam temu duga, buat pilihan berdasarkan domain kekunci, nisbah kemas kini, belanjawan memori, dan kebolehselenggaraan berbanding hanya melaporkan batas asimptotik terpantas.
Mulakan dengan U bersamaan 2, 4, dan 16, berserta semesta bukan kuasa bagi dua, untuk menguji penguraian sempadan. Jana jujukan pemasukan, pemadaman, dan pertanyaan rawak serta bandingkan minimum, maksimum, keahlian, pendahulu, dan pengganti dengan set teratur bahasa pengaturcaraan tersebut. Gandakan juga liputan untuk pemasukan pendua, pemadaman kekunci yang tiada, pemadaman kekunci terakhir, dan pemadaman berulang bagi minimum atau maksimum.
Rujukan
- Syarahan van Emde Boas Trees MIT OpenCourseWare: kelompok rekursif, ringkasan, dan terbitan operasi.
- Syarahan 7 Algoritma Siswazah Carnegie Mellon: analisis kerehasan O(log log U) dan butiran pelaksanaan.
- Tinjauan carian pendahulu Springer: karya asal van Emde Boas dan konteks masalah pendahulu.
Soalan susulan
Mengapakah struktur ringkasan diperlukan?
Apabila kelompok semasa tidak mempunyai elemen yang lebih besar, pokok tersebut mesti mencari kelompok tidak kosong seterusnya dengan cepat. Ringkasan mengubah "kelompok mana yang tidak kosong" menjadi masalah pendahulu atau pengganti yang lain dan bukannya mengimbas kelompok secara linear.
Mengapakah min dan max boleh berada di luar kelompok?
Menyimpan min dan max secara berasingan menjadikan operasi pokok kosong dan singleton beroperasi dalam masa malar serta mengurangkan rekursi. Pemasukan menukar nilai yang lebih kecil ke dalam min; pemadaman mencari pengganti ekstrem melalui ringkasan dan memulihkan invariannya.
Bagaimana jika U bukan kuasa bagi dua?
Bundarkan ke atas kepada semesta kuasa bagi dua yang merangkumi setiap kekunci yang sah dan tolak kekunci di luar julat asal. Sebagai alternatif, laksanakan sempadan kelompok yang dibundarkan, tetapi buktikan bahawa high, low, dan index kekal sebagai operasi songsang dan kekompleksan masih dikekalkan.
Bagaimanakah anda boleh mengurangkan ruang O(U)?
Gunakan kelompok jarang, x-fast trie, atau y-fast trie. Terangkan pelanggaran cincangan, kerawakan, semantik lelaran, dan faktor pemalar dan bukannya hanya membandingkan tatatanda Big-O.
Bilakah anda patut mengelakkan vEB?
Gunakan pokok seimbang atau pokok B apabila domain kekunci adalah sangat besar dan jarang, semesta tidak boleh ditetapkan, pembanding umum diperlukan, atau tingkah laku lelaran yang matang lebih penting daripada batas teori.