लोड पासा के लिए डेटा संरचना?

Question

मान लीजिए कि मेरे पास एक एन-पक्षीय भारित मर है जहां प्रत्येक पक्ष के पास कुछ रोलबैक है, तो _k आने पर आने के बाद। मैं उत्सुक हूं कि इस जानकारी को स्थिर रूप से संग्रहीत करने के लिए अच्छा एल्गोरिदम है (यानी संभावनाओं के एक निश्चित सेट के लिए) ताकि मैं मरने के यादृच्छिक रोल को कुशलतापूर्वक अनुकरण कर सकूं।

वर्तमान में, मेरे पास इस समस्या के लिए ओ (एलजी एन) समाधान है। विचार सभी के लिए पहले के पक्षों की संचयी संभावना की एक तालिका को स्टोर करना है, उन्हें श्रेणी [0, 1) में एक यादृच्छिक वास्तविक संख्या उत्पन्न करने के लिए और तालिका में एक बाइनरी खोज करने के लिए सबसे बड़ी अनुक्रमणिका प्राप्त करने के लिए जिसका संचयी मान चयनित मूल्य से अधिक नहीं है। मैं इस समाधान को पसंद करता हूं, लेकिन ऐसा लगता है कि रनटाइम संभावनाओं को ध्यान में नहीं लेता है। विशेष रूप से, एक तरफ के चरम मामलों में हमेशा आने या मूल्यों को समान रूप से वितरित किया जा रहा है, एक निष्पक्ष दृष्टिकोण का उपयोग करके ओ (1) में रोल के परिणाम उत्पन्न करना संभव है, हालांकि मेरा समाधान अभी भी कई कदमों को लॉगरिदमिक ले जाएगा।

क्या किसी के पास इस समस्या को हल करने के तरीके के बारे में कोई सुझाव है जो किसी भी तरह के रनटाइम में "अनुकूली" है?

संपादित: इस सवाल के जवाब के आधार पर, मैं an article describing many approaches to this problem ऊपर लिखा है, उनके विश्लेषण के साथ। ऐसा लगता है कि ऊर्फ विधि के वोस के कार्यान्वयन Θ (एन) प्रीप्रोकैसिंग समय और ओ (1) समय प्रति मर रोल देता है, जो वास्तव में प्रभावशाली है। उम्मीद है कि यह उत्तर में निहित जानकारी के लिए एक उपयोगी अतिरिक्त है!

Answer 1

आप alias method जो एक निश्चित असतत संभावना वितरण पैदा करने के लिए एक हे (1) तरीका प्रदान करता है के लिए देख रहे हैं (यह मानते हुए आप निरंतर समय में n लंबाई की एक सरणी में प्रविष्टियों का उपयोग कर सकते हैं) एक बार की है O (एन) सेट अप। आप इसे chapter 3 (PDF) में "Non-Uniform Random Variate Generation" में ल्यूक देवरो द्वारा दस्तावेज में पा सकते हैं।

विचार संभावनाओं पी _{कश्मीर} के अपने सरणी लेने के लिए और तीन नए एन-तत्व सरणियों, क्ष _{कश्मीर}, एक _{कश्मीर}, और ख _{कश्मीर} उत्पादन होता है। प्रत्येक क्यू _के 0 और 1 के बीच एक संभावना है, और प्रत्येक _के और बी _के 1 और n के बीच एक पूर्णांक है।

हम 0 और 1 के बीच दो यादृच्छिक संख्या, आर और एस उत्पन्न करके 1 और एन के बीच यादृच्छिक संख्या उत्पन्न करते हैं। मैं = मंजिल (आर * एन) +1 दें। क्ष _मैं < रों फिर एक _{वापस नहीं आ जाते मैं मैं ख बाकी वापसी}। उपनाम विधि में काम q _k, _के और बी _के का उत्पादन करने के तरीके को समझने में है।

Answer 2

मैं आपकी मेज को दबाने की सोच रहा हूं।

प्रत्येक मरने के मूल्य के संचयी के साथ एक टेबल रखने के बजाय, आप लम्बाई एक्सएन की एक पूर्णांक सरणी बना सकते हैं, जहां एक्स आदर्श रूप से संभावना की सटीकता बढ़ाने के लिए एक उच्च संख्या है।

संचयी मान के रूप में इंडेक्स (xN द्वारा सामान्यीकृत) का उपयोग करके इस सरणी को पॉप्युलेट करें और सरणी में प्रत्येक 'स्लॉट' में, यह सूचकांक आने पर पासा रोल को स्टोर करें।

तीन पासा का उपयोग करना::

शायद मैं एक उदाहरण के साथ आसान समझा सकता है पी (1) = 0.2, पी (2) = 0.5, पी (3) = 0,3

एक सरणी बनाएँ, में इस मामले में मैं एक साधारण लंबाई का चयन करेंगे, 10 कहते हैं (जो है, एक्स = 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 

तो संभावना प्राप्त करने के लिए, बस 0 और 10 के बीच की संख्या randomize और बस उस सूचकांक का उपयोग।

यह विधि सटीकता को खो सकती है, लेकिन एक्स और सटीकता में वृद्धि पर्याप्त होगी।

Answer 3

संतुलित बाइनरी खोज पेड़ (या सरणी में बाइनरी खोज) का उपयोग करें और ओ (लॉग एन) जटिलता प्राप्त करें। प्रत्येक मरने के परिणाम के लिए एक नोड रखें और चाबी अंतराल हो जो उस परिणाम को ट्रिगर करेगी।

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) 

इस समाधान के बारे में अच्छी बात यह है कि लागू करने के लिए बहुत आसान है, लेकिन अभी भी अच्छा जटिलता है।