Alias method
कम्प्यूटिंग में, उपनाम विधि एक असतत संभावना वितरण से नमूने लेने के लिए कुशल एल्गोरिदम का एक परिवार है, जिसे 1974 में ए. जे. वॉकर द्वारा प्रकाशित किया गया था। अर्थात्, यह कुछ मनमाने संभाव्यता वितरण के अनुसार पूर्णांक मान देता है। एल्गोरिदम आम तौर पर समय का उपयोग या पूर्व-प्रसंस्करण करते हैं, जिसके बाद समय पर वितरण से यादृच्छिक मान निकाले जा सकते हैं। ऑपरेशन आंतरिक रूप से, एल्गोरिथ्म दो तालिकाओं, एक संभाव्यता तालिका और एक उपनाम तालिका (के लिए) से परामर्श करता है। एक यादृच्छिक परिणाम उत्पन्न करने के लिए, दो तालिकाओं में एक सूचकांक निर्धारित करने के लिए एक उचित पासा घुमाया जाता है। उस सूचकांक में संग्रहीत संभावना के आधार पर, एक पक्षपाती सिक्के को फ़्लिप किया जाता है, और फ़्लिप के परिणाम का उपयोग और के परिणाम के बीच चयन करने के लिए किया जाता है। अधिक ठोस रूप से, एल्गोरिथ्म निम्नानुसार काम करता हैः एक समान यादृच्छिक विविधता उत्पन्न करें। चलो और। (यह समान रूप से वितरित और समान रूप से वितरित किया जाता है।) अगर, तो वापस आ जाएँ। यह पक्षपाती सिक्का पलट है। अन्यथा वापस आ जाएँ। मार्सग्लिया एट अल द्वारा प्रस्तावित संभाव्यता तालिका का एक वैकल्पिक सूत्रीकरण। "वर्गाकार हिस्टोग्राम" विधि के रूप में, गणना के बजाय तीसरे चरण (जहाँ) में स्थिति का उपयोग करता है। तालिका उत्पादन वितरण को एक सुविधाजनक मूल्य तक बढ़ाने के लिए अतिरिक्त संभावनाओं के साथ गद्देदार किया जा सकता है, जैसे कि दो की शक्ति। तालिका बनाने के लिए, पहले आरंभ करें। ऐसा करते समय, तालिका प्रविष्टियों को तीन श्रेणियों में विभाजित करेंः "अति पूर्ण" समूह, जहाँ, "अल्प पूर्ण" समूह, जहाँ और कहाँ आरंभ नहीं किया गया है, और "बिल्कुल पूर्ण" समूह, जहाँ या कहाँ आरंभ किया गया है। यदि, संबंधित मूल्य से कभी भी परामर्श नहीं किया जाएगा और यह महत्वहीन है, लेकिन इसका मूल्य विवेकपूर्ण है। जब तक सभी तालिका प्रविष्टियाँ पूरी तरह से भरी नहीं हैं, तब तक निम्नलिखित चरणों को दोहराएंः मनमाने ढंग से एक अति पूर्ण प्रविष्टि और एक अल्प पूर्ण प्रविष्टि चुनें। (यदि इनमें से एक मौजूद है, तो दूसरा भी होना चाहिए।) परिणाम की प्रविष्टि में अप्रयुक्त स्थान को सेटिंग द्वारा आवंटित करें। आवंटित स्थान को बदलकर प्रविष्टि से हटा दें। प्रवेश अब बिल्कुल भरा हुआ है। के नए मूल्य के आधार पर उपयुक्त श्रेणी में प्रविष्टि निर्धारित करें। प्रत्येक पुनरावृत्ति कम से कम एक प्रविष्टि को "बिल्कुल पूर्ण" श्रेणी में ले जाती है (और अंतिम चाल दो), इसलिए प्रक्रिया को अधिक से अधिक पुनरावृत्तियों के बाद समाप्त करने की गारंटी है। प्रत्येक पुनरावृत्ति समय पर की जा सकती है, इसलिए तालिका को समय पर स्थापित किया जा सकता है। वोज़ बताते हैं कि फ्लोटिंग-पॉइंट राउंडिंग त्रुटियों के कारण चरण 1 में निर्दिष्ट गारंटी का उल्लंघन हो सकता है। यदि एक श्रेणी दूसरे से पहले खाली हो जाती है, तो शेष प्रविष्टियाँ नगण्य त्रुटि के साथ 1 पर सेट हो सकती हैं। तैरते बिंदु के लिए समाधान लेखांकन को कभी-कभी वॉकर-वोज़ विधि या वोज़ उपनाम विधि कहा जाता है। उपनाम संरचना अद्वितीय नहीं है। चूँकि खोज प्रक्रिया थोड़ी तेज़ है यदि (क्योंकि परामर्श की आवश्यकता नहीं है), तालिका निर्माण के दौरान एक लक्ष्य तालिका के योग को अधिकतम करना है। इसे बेहतर तरीके से करना एन. पी. कठिन साबित होता है, लेकिन एक लालची एल्गोरिदम उचित रूप से करीब आता हैः सबसे अमीर से लूटें और सबसे गरीब को दें। अर्थात्, प्रत्येक चरण में सबसे बड़ा और सबसे छोटा चुनें। क्योंकि इसके लिए छँटाई की आवश्यकता होती है, इसमें समय लगता है। दक्षता हालांकि उपनाम विधि बहुत कुशल है यदि एक समान विचलन उत्पन्न करना अपने आप में तेज़ है, ऐसे मामले हैं जहां यह यादृच्छिक बिट उपयोग के मामले में इष्टतम से बहुत दूर है। ऐसा इसलिए है क्योंकि यह हर बार एक पूर्ण-परिशुद्धता यादृच्छिक विविधता का उपयोग करता है, तब भी जब केवल कुछ यादृच्छिक बिट्स की आवश्यकता होती है। एक मामला तब उत्पन्न होता है जब संभावनाएं विशेष रूप से अच्छी तरह से संतुलित होती हैं, इतनी अधिक होती हैं और इसकी आवश्यकता नहीं होती है। उत्पादन करना समय की बर्बादी है। उदाहरण के लिए यदि, तो 32-बिट यादृच्छिक विविधता का उपयोग 32 विकल्प बनाने के लिए किया जा सकता है, लेकिन उपनाम विधि केवल एक उत्पन्न करेगी। एक अन्य मामला तब सामने आता है जब संभावनाएं प्रबल रूप से असंतुलित होती हैं। उदाहरण के लिए यदि और, तो अधिकांश समय, केवल कुछ यादृच्छिक बिट्स की आवश्यकता होती है यह निर्धारित करने के लिए कि मामला 1 लागू होता है। ऐसे मामलों में, मार्साग्लिया एट अल द्वारा वर्णित तालिका विधि। अधिक कुशल है। यदि हम समान संभावना के साथ कई विकल्प चुनते हैं तो हमें औसतन एक निष्पक्ष यादृच्छिक बिट से बहुत कम की आवश्यकता हो सकती है। अंकगणितीय कोडिंग तकनीकों का उपयोग करके हम द्विआधारी एन्ट्रापी फलन द्वारा दी गई सीमा तक पहुँच सकते हैं। साहित्य डोनाल्ड क्नुथ, द आर्ट ऑफ कंप्यूटर प्रोग्रामिंग, खंड 2: सेमीन्यूमेरिकल एल्गोरिदम, खंड 3.4.1। कार्यान्वयन http://www.keithschwarz.com/darts-dice-coins कीथ श्वार्जः विस्तृत व्याख्या, वोज़ के एल्गोरिथ्म का संख्यात्मक रूप से स्थिर संस्करण, और जावा कार्यान्वयन https://jugit.fz-juelich.de/mlz/ransampl जोआचिम वुटकेः एक छोटे सी पुस्तकालय के रूप में कार्यान्वयन। https://gist.github.com/0b5786e9bfc73e75eb8180b5400cd1f8 लियाम हुआंग का C + + https://github.com/joseftw/jos.weightedresult/blob/develop/src/JOS.WeightedResult/AliasMethodVose.cs C #में वोज़ के एल्गोरिदम का कार्यान्वयन। फ्लोटिंग पॉइंट अस्थिरता के बिना वोज़ के एल्गोरिथ्म का https://github.com/cdanek/KaimiraWeightedList C #कार्यान्वयन। संदर्भ स्यूडोरैंडम संख्या जनित्र