Yüklenen zar için veri yapısı?

Question

Her bir k tarafının, onu döndürdüğümde gelme olasılığına sahip olduğu n taraflı bir yükleme kalıbına sahip olduğumu varsayalım. Bu bilgiyi statik olarak saklamak için iyi bir algoritma varsa (örn. Sabit bir olasılık kümesi için), kalıbın rasgele bir sırasını etkili bir şekilde simüle edebilmem için merak ediyorum.

Şu anda bu sorun için bir O (lg n) çözümüm var. Buradaki amaç, tüm k için ilk k taraflarının kümülatif olasılığını içeren bir tabloyu saklamak, [0, 1] aralığında rastgele bir gerçek sayı oluşturmak ve kümülatif olan en büyük endeksi elde etmek için tablo üzerinde bir ikili arama yapmaktır. Değer seçilen değerden daha büyük değildir. Bu çözümü tercih etmekteyim, ancak çalışma zamanının olasılıkları hesaba katmaması garip görünüyor. Özellikle, bir tarafın aşırı uç durumlarında veya her zaman eşit olarak dağılmış olan durumlarda, çözümümün hala birçok adımda logaritmik olarak alınmasına rağmen, O (1) 'deki rulo sonucunu saf bir yaklaşımla üretmek mümkündür.

Bu sorunun, bir şekilde çalışma zamanında "uyarlanabilir" olacak şekilde nasıl çözüleceği konusunda herhangi bir önerisi var mı?

DÜZENLEME: Bu sorunun yanıtları dayanarak, onların analizleri ile birlikte an article describing many approaches to this problem kadar yazdım. Vose'un takma adının uygulanması, Θ (n) ön işleme süresini ve her bir rulo rulosunda O (1) zamanını gerçekten etkileyici bir şekilde vermektedir. Umarım bu cevaplarda yer alan bilgilere faydalı bir katkıdır!

Answer 1

bir sabit aralıklı olasılık dağılımını oluşturmak için bir O (1) yöntem sağlar alias method Aradığınız (bir kerelik O ile (sabit zamanda n uzunluğunda bir dizi girişleri erişebilir varsayılarak) n) kurulum. Bunu, Luc Devroye tarafından "Non-Uniform Random Variate Generation"'un chapter 3 (PDF) belgesinde bulabilirsiniz.

fikri olasılıkları p _k dizinizi alıp üç yeni n elemanlı dizi, q _k, bir _k ve b _k üretmektir. Her bir _k, 0 ile 1 arasında bir olasılıktır ve her biri bir _k ve b _k 1 ve n arasında bir tamsayıdır.

1 ve n arasındaki rasgele sayıları, 0 ve 1 arasında iki rastgele sayı, r ve s üreterek üretiriz. I = kat (r * N) +1 olsun. Eğer q _i < s sonra _i i _i'a geri gönderin. Diğer ad yöntemindeki çalışma, _k, _k ve b _k'un nasıl üretileceğini bulmaktır.

Answer 2

Masanızı granüle etmeyi düşünüyorum.

Her bir kalıp değeri için birikimli bir tablo yerine, x'in uzunluğu olan bir tamsayı dizisi yaratabilirsiniz; burada x, olasılığın doğruluğunu artırmak için ideal olarak yüksek bir sayıdır.

Bu diziyi, kümülatif değer olarak dizini (xN ile normalleştirilen) kullanarak ve dizideki her 'yuvada' bu dizini oluşturuyorsa, zarın saklanan zarını saklayın. içerisinde: (1) = 0.2, P (2) = 0.5, P (3) =

0.3 dizisi yaratmak P:

üç zar kullanarak:

Belki bir örnekle daha kolay açıklayabilir Ben basit bir uzunluğa seçecektir Bu durumda, Sonra sadece 0 ile 10 arasında bir sayı rastgele, olasılık almak ve sadece o indeksine erişmek (yani 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 

10. söylüyorlar.

Bu yöntem hatasından kurtulabilir, ancak x ve doğruluğunu artırabilir.

Answer 3

Dengeli ikili bir arama ağacı (veya bir dizide ikili arama) kullanın ve O (log n) karmaşıklığını alın. Her bir kalıp sonucu için bir düğüme sahip olun ve bu sonuçları tetikleyecek aralıkların anahtarları olmasını sağlayın.

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) 

Bu çözümle ilgili iyi olan şey, uygulanması çok basit ancak yine de iyi bir karmaşıklığa sahip olmasıdır.