Struktur data untuk dadu yang dimuat?

130

Misalkan saya memiliki n-sided die die di mana setiap sisi k memiliki beberapa kemungkinan pk untuk muncul ketika saya menggulungnya. Saya ingin tahu apakah ada algoritma yang baik untuk menyimpan informasi ini secara statis (yaitu untuk serangkaian probabilitas tetap) sehingga saya dapat secara efisien mensimulasikan gulungan acak cetakan.

Saat ini, saya punya solusi O (lg n) untuk masalah ini. Idenya adalah untuk menyimpan tabel probabilitas kumulatif sisi k pertama untuk semua k, mereka untuk menghasilkan bilangan real acak dalam kisaran [0, 1) dan melakukan pencarian biner di atas tabel untuk mendapatkan indeks terbesar yang kumulatifnya nilai tidak lebih besar dari nilai yang dipilih. Saya lebih suka solusi ini, tetapi tampaknya aneh bahwa runtime tidak memperhitungkan probabilitas. Secara khusus, dalam kasus ekstrem di satu sisi selalu muncul atau nilai-nilai didistribusikan secara seragam, dimungkinkan untuk menghasilkan hasil roll di O (1) menggunakan pendekatan naif, meskipun solusi saya masih akan mengambil banyak langkah logaritma.

Adakah yang punya saran untuk bagaimana mengatasi masalah ini dengan cara yang entah bagaimana "adaptif" dalam runtime itu?

EDIT : Berdasarkan jawaban atas pertanyaan ini, saya telah menulis sebuah artikel yang menggambarkan banyak pendekatan untuk masalah ini , beserta analisisnya. Sepertinya implementasi metode alias Vose memberi Θ (n) waktu preprocessing dan O (1) waktu per die roll, yang benar-benar mengesankan. Semoga ini adalah tambahan yang berguna untuk informasi yang terkandung dalam jawaban!

templatetypedef
sumber
2
Masuk akal jika ada solusi O (1) untuk setiap kasus tertentu .
Tim

Jawaban:

117

Anda mencari metode alias yang menyediakan metode O (1) untuk menghasilkan distribusi probabilitas diskrit tetap (dengan asumsi Anda dapat mengakses entri dalam array panjang n dalam waktu konstan) dengan pengaturan O (n) satu kali . Anda dapat menemukannya didokumentasikan dalam bab 3 (PDF) dari "Generasi Variabel Acak Tidak Seragam" oleh Luc Devroye.

Idenya adalah untuk mengambil array probabilitas p k dan menghasilkan tiga array n-elemen baru, q k , sebuah k , dan b k . Setiap q k adalah probabilitas antara 0 dan 1, dan setiap a k dan b k adalah bilangan bulat antara 1 dan n.

Kami menghasilkan angka acak antara 1 dan n dengan menghasilkan dua angka acak, r dan s, antara 0 dan 1. Biarkan i = lantai (r * N) +1. Jika q i <s kemudian mengembalikan saya kembali lagi b i . Pekerjaan dalam metode alias dalam mencari tahu bagaimana untuk menghasilkan q k , a k dan b k .

mhum
sumber
Untuk algoritma yang bermanfaat seperti itu, Metode Alias ​​secara mengejutkan tidak terlalu terkenal.
mhum
Sebagai catatan: Saya menerbitkan perpustakaan C kecil untuk pengambilan sampel acak menggunakan metode alias apps.jcns.fz-juelich.de/ransampl .
Joachim W
1
implementasi spesifik dari metode alias mungkin lebih lambat daripada metode dengan kompleksitas waktu yang lebih buruk seperti Roulette Wheel untuk diberikan ndan untuk sejumlah angka acak yang dipilih untuk menghasilkan karena faktor konstan yang terlibat dalam mengimplementasikan algoritma.
jfs
4

Gunakan pohon pencarian biner seimbang (atau pencarian biner dalam array) dan dapatkan kompleksitas O (log n). Memiliki satu simpul untuk setiap hasil mati dan memiliki kunci menjadi interval yang akan memicu hasil itu.

function get_result(node, seed):
    if seed < node.interval.start:
        return get_result(node.left_child, seed)
    else if seed < node.interval.end:
        // start <= seed < end
        return node.result
    else:
        return get_result(node.right_child, seed)

Hal yang baik tentang solusi ini adalah sangat sederhana untuk diimplementasikan tetapi masih memiliki kompleksitas yang baik.

hugomg
sumber
Pohon biner buatan tangan seperti di atas mudah diimplementasikan tetapi tidak dijamin seimbang
yusong
Anda dapat menjamin bahwa itu seimbang jika Anda membangunnya dalam urutan yang benar.
hugomg
3

Saya sedang memikirkan granulasi meja Anda.

Alih-alih memiliki tabel dengan kumulatif untuk setiap nilai mati, Anda bisa membuat array integer dengan panjang xN, di mana x idealnya angka yang tinggi untuk meningkatkan akurasi probabilitas.

Isi larik ini menggunakan indeks (dinormalkan oleh xN) sebagai nilai kumulatif dan, di setiap 'slot' dalam larik, simpan gulungan dadu calon jika indeks ini muncul.

Mungkin saya bisa menjelaskan dengan lebih mudah dengan contoh:

Menggunakan tiga dadu: P (1) = 0,2, P (2) = 0,5, P (3) = 0,3

Buat array, dalam hal ini saya akan memilih panjang yang sederhana, katakanlah 10. (yaitu, x = 3.33333)

arr[0] = 1,
arr[1] = 1,
arr[2] = 2,
arr[3] = 2,
arr[4] = 2,
arr[5] = 2,
arr[6] = 2,
arr[7] = 3,
arr[8] = 3,
arr[9] = 3

Kemudian untuk mendapatkan probabilitas, cukup acak angka antara 0 dan 10 dan cukup akses indeks itu.

Metode ini mungkin kehilangan akurasi, tetapi meningkatkan x dan akurasi akan cukup.

andrewjs
sumber
1
Untuk akurasi penuh Anda dapat melakukan pencarian array sebagai langkah pertama, dan untuk interval array yang sesuai dengan banyak sisi lakukan pencarian di sana.
aaz
1

Ada banyak cara untuk menghasilkan bilangan bulat acak dengan distribusi kustom (juga dikenal sebagai distribusi diskrit ). Pilihannya tergantung pada banyak hal, termasuk jumlah bilangan bulat untuk dipilih, bentuk distribusi, dan apakah distribusi akan berubah seiring waktu.

Salah satu cara paling sederhana untuk memilih integer dengan fungsi bobot kustom f(x)adalah metode sampel penolakan . Berikut ini mengasumsikan bahwa nilai tertinggi fadalah max. Kompleksitas waktu untuk sampel penolakan rata-rata konstan, tetapi sangat tergantung pada bentuk distribusi dan memiliki kasus terburuk untuk berjalan selamanya. Untuk memilih integer dalam [1, k] menggunakan sampel penolakan:

  1. Pilih integer acak seragam idalam [1,k ].
  2. Dengan probabilitas f(i)/max, kembali i. Jika tidak, lanjutkan ke langkah 1.

Algoritme lain memiliki waktu pengambilan sampel rata-rata yang tidak terlalu bergantung pada distribusi (biasanya konstan atau logaritmik), tetapi seringkali mengharuskan Anda untuk menghitung ulang bobot dalam langkah pengaturan dan menyimpannya dalam struktur data. Beberapa dari mereka juga ekonomis dalam hal jumlah bit acak yang mereka gunakan rata-rata. Banyak dari algoritma ini diperkenalkan setelah 2011, dan mereka termasuk—

  • struktur data ringkas Bringmann – Larsen ("Pengambilan Sampel Singkat dari Distribusi Diskrit", 2012),
  • Pencarian multi-level Yunpeng Tang ("Sebuah Studi Empiris Metode Pengambilan Sampel Acak untuk Mengubah Distribusi Diskrit", 2019), dan
  • yang Loaded Cepat Dice Roller (2020).

Algoritma lain termasuk metode alias (sudah disebutkan dalam artikel Anda), algoritma Knuth-Yao, struktur data MVN, dan banyak lagi. Lihat bagian saya " Catatan tentang Algoritma Pilihan Berbobot " untuk survei.

Peter O.
sumber