Apakah struktur data pencarian probabilistik berguna?

9

SkipList menyediakan batas untuk pencarian sebagai pohon seimbang dengan keuntungan yang tidak perlu diseimbangkan ulang. Karena SkipList dibuat menggunakan membalik koin acak, batas-batas ini hanya berlaku selama struktur SkipList cukup "seimbang". Secara khusus, dengan probabilitas untuk beberapa konstanta , struktur seimbang mungkin hilang setelah memasukkan elemen. $O(\log n)$ $1/n^c$ $c>0$

Katakanlah saya ingin menggunakan daftar lewati sebagai backend penyimpanan dalam aplikasi web yang berpotensi berjalan selamanya. Jadi setelah sejumlah operasi polinomial, struktur yang seimbang dari SkipList sangat mungkin hilang.

Apakah alasan saya benar? Apakah struktur data pencarian / penyimpanan probabilistik memiliki aplikasi praktis dan jika demikian, bagaimana masalah di atas dihindari?

Sunting: Saya menyadari bahwa ada varian deterministik dari SkipList, yang jauh lebih rumit untuk diterapkan dibandingkan dengan SkipList acak (klasik).

data-structures search-trees probabilistic-algorithms seseorang
sumber

1

Aplikasi spesifik apa yang Anda pikirkan?

Pratik Deoghare

6

Saya tidak berpikir ada kemungkinan jumlahnya banyak untuk kehilangan 'keseimbangan'. Setelah Anda memasukkan elemen dalam daftar lewati, Anda membangun menara salinan di atasnya dengan membalik koin sampai muncul kepala.

Jadi Anda memiliki lapisan dengan lebih sedikit dan lebih sedikit elemen saat Anda mencapai puncak. Karena sebuah menara memiliki ketinggian dengan probabilitas , ada elemen pada ketinggian dengan probabilitas (ikatan terikat) kurang dari . Karenanya memiliki elemen pada level memiliki kemungkinan kurang dari . Menara tinggi memiliki probabilitas subpolinomial. Biarkan menjadi level maksimum, maka kita miliki $k$ $2^{-k}$ $k$ $n/2^k$ $c\log n$ $1/n^c$ $\omega(\log n)$ $M$

E [M.] = \sum_{k \geq 1} P r (M. \geq k) \leq catatan (n) + \sum_{k \leq catatan (n)} n / 2^{k} = catatan (n) + 2.

$E[M] = \sum_{k\geq 1} Pr(M\geq k) \leq \log(n) + \sum_{k\le \log(n)} n/2^k = \log(n) + 2.$

Selanjutnya, pada level ada elemen dengan probabilitas sangat tinggi, karena ini adalah jumlah dari variabel acak independen dan Anda dapat menggunakan ikatan Chernov. $k$ $n/2^k$ $n$

Karena Anda juga dapat menunjukkan bahwa Anda hanya melakukan sejumlah langkah per level (dengan probabilitas sangat tinggi!), Biaya pencarian bersifat logaritmik.

Jadi, Anda harus benar-benar tidak beruntung untuk berakhir dengan daftar yang tidak seimbang. Perhatikan bahwa 'keberuntungan' di sini tidak tergantung pada data Anda, tidak seperti misalnya di pohon pencarian yang tidak seimbang. Membalik koin dalam Daftar Lewati selalu acak.

Sejauh yang saya tahu, daftar lompatan adalah kepentingan praktis yang besar, karena relatif mudah untuk menerapkannya sebagai struktur pencarian bebas kunci, dengan manfaat yang jelas. Pohon-B di sisi lain agak sulit untuk membuat pemain di bawah akses bersamaan.

adrianN
sumber

Kedalaman yang diharapkan dari pohon pencarian biner juga logaritmik; mengapa situasinya lebih baik di sini? (Juga, Anda menganggap permutasi acak, benar?)

Raphael

2

Dalam pohon pencarian, kedalamannya tergantung pada data. Jika Anda memberinya angka acak, ia memiliki kedalaman logaritmik dengan probabilitas sangat tinggi. Namun, dalam praktiknya, data tidak acak. Abaikan daftar tidak menggunakan data sebagai sumber keacakan, sehingga masalah ini tidak ada.

adrianN

1

Abaikan daftar memiliki properti lain yang mungkin membuatnya menarik dalam situasi di mana operasi selain hanya menyisipkan / mencari / menghapus digunakan.

$O(1)$ $O(1)$

Selain itu, daftar lompatan telah menjadi cara populer untuk menerapkan struktur pencarian berbasis perbandingan secara bersamaan. Secara historis, pohon pencarian seimbang tidak berkinerja baik di bawah pertikaian serentak yang tinggi.

jbapple
sumber

Apakah struktur data pencarian probabilistik berguna?

Jawaban: