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 #અમલ. સંદર્ભો સ્યુડોરાન્ડમ નંબર જનરેટર