1. प्रश्न
एक विज्ञापन प्रणाली में N उम्मीदवार हैं, जहां प्रत्येक वेट चयन के सापेक्ष अवसर का प्रतिनिधित्व करता है। इनिशियलाइज़ेशन के बाद लाखों सिंगल-आइटम ड्रॉ किए जाते हैं, इसलिए प्रत्येक ड्रॉ O(1) के करीब होना चाहिए जबकि बैच वेट अपडेट्स संभव बने रहें। एक एलियास टेबल डिज़ाइन करें और शून्य वेट्स, फ्लोटिंग-पॉइंट एरर, और रैंडम-नंबर सीमाओं को कवर करें।
2. सीमाएं और स्पष्टीकरण
- रिप्लेसमेंट के साथ एक ड्रॉ से शुरुआत करें; बिना रिप्लेसमेंट के सैंपलिंग और सिंगल-वेट अपडेट्स एक्सटेंशन हैं।
- वेट्स गैर-ऋणात्मक हैं और उनका योग सकारात्मक होना चाहिए; शून्य-वेट वाले आइटम को कभी नहीं चुना जाना चाहिए।
- सैंपलर
[0, 1)में एक यूनिफॉर्म इंटीजर और एक यूनिफॉर्म रियल नंबर का उपयोग कर सकता है। - वेट बैच के बाद
O(N)में पुनर्निर्माण स्वीकार्य है, लेकिन एक पुरानी टेबल नए वेट्स का प्रतिनिधित्व नहीं कर सकती।
3. मुख्य दृष्टिकोण
प्रत्येक वेट को p_i = w_i * N / sum(w) पर स्केल करें, जिसका औसत 1 है। लंबाई N के prob और alias एरे बनाए रखें। एक बकेट prob[i] की संभावना के साथ खुद को लौटाती है; अन्यथा यह alias[i] पर कूदती है। प्रीप्रोसेसिंग के दौरान, 1 से कम मानों को small में और 1 से अधिक मानों को large में रखें; प्रत्येक तरफ से एक की जोड़ी बनाएं, छोटी बकेट को भरें, और बची हुई क्षमता को बड़ी बकेट में वापस लौटाएं जब तक कि सभी बकेट पूरी न हो जाएं।
सैंपलिंग पहले समान रूप से एक बकेट चुनती है, फिर एक यूनिफॉर्म रियल की तुलना prob[i] से करती है। प्रत्येक मूल आइटम को असाइन किया गया कुल क्षेत्र उसकी नॉर्मलाइज़्ड संभावना के बराबर होता है, इसलिए इसकी लॉन्ग-रन फ्रीक्वेंसी इसके वेट के समानुपाती होती है।
4. संदर्भ कार्यान्वयन
build(weights):
n = len(weights)
scale = n / sum(weights)
scaled = [w * scale for w in weights]
prob = array(n)
alias = array(n)
small, large = [], []
for i, value in enumerate(scaled):
(small if value < 1 else large).append(i)
while small and large:
s = small.pop()
l = large.pop()
prob[s] = scaled[s]
alias[s] = l
scaled[l] -= 1 - scaled[s]
(small if scaled[l] < 1 else large).append(l)
for i in small + large:
prob[i] = 1
alias[i] = i
return prob, alias
sample(prob, alias, rng):
i = rng.uniform_int(0, len(prob))
return i if rng.uniform01() < prob[i] else alias[i]5. जटिलता और शुद्धता
प्रीप्रोसेसिंग में O(N) समय और स्थान लगता है। प्रत्येक सैंपल के लिए एक यूनिफॉर्म बकेट चयन, एक तुलना, और अधिकतम एक एरे लुकअप की आवश्यकता होती है, इसलिए यह O(1) है। अवशिष्ट फ्लोटिंग-पॉइंट एरर के बाद prob को [0, 1] में क्लैंप करें; पूर्णांक रेंज को हाफ-ओपन के रूप में परिभाषित करें ताकि अंतिम बकेट छूट न जाए।
वैलिडेशन के लिए कुछ से अधिक ड्रॉ की आवश्यकता होती है। पर्याप्त सैंपल जनरेट करें, प्रत्येक प्रेक्षित फ्रीक्वेंसी की तुलना w_i / sum(w) से करें, और महत्वपूर्ण पूर्वाग्रह का पता लगाने के लिए कॉन्फिडेंस इंटरवल्स या ची-स्क्वेर्ड टेस्ट का उपयोग करें। पुनर्निर्मित टेबल को एटॉमिक रूप से बदलें ताकि सैंपलर कभी भी मिश्रित संस्करण न देखे।
6. फ़ॉलो-अप और जाल
- एलियास टेबल स्टैटिक या बैच-अपडेटेड डिस्ट्रीब्यूशन के लिए उपयुक्त हैं। लगातार सिंगल-वेट परिवर्तनों के लिए, फेनविक ट्री या सेगमेंट ट्री बेहतर विकल्प हो सकते हैं।
- नॉर्मलाइज़ेशन से पहले कुल योग का ओवरफ्लो होना अनुपातों को बिगाड़ देता है; व्यापक प्रिसिजन का उपयोग करें या पहले स्केल करें।
- “O(1)” में पुनर्निर्माण लागत शामिल नहीं है और यह रैंडम-नंबर जनरेटर को मुफ़्त नहीं बनाता है।
- शून्य योग कोई डिस्ट्रीब्यूशन परिभाषित नहीं करता है। प्रत्येक आइटम को समान रूप से लौटाने के बजाय इसे अस्वीकार करें।
7. आगे पढ़ना
बाइनरी सर्च के साथ प्रीफिक्स सम, फेनविक ट्री, रिज़र्वॉयर सैंपलिंग, और एलियास टेबल की तुलना करें: प्रीफिक्स संरचनाएं O(log N) सैंपलिंग के साथ डायनामिक अपडेट का समर्थन करती हैं, रिज़र्वॉयर स्ट्रीम के अनुकूल होते हैं, और एलियास टेबल हाई-थ्रूपुट O(1) ड्रॉ के लिए O(N) प्रीप्रोसेसिंग का ट्रेड-ऑफ करते हैं।
8. साक्षात्कार स्कोरिंग बिंदु
छोटी और बड़ी बकेट्स बना सकते हैं
उम्मीदवार को वेट्स को औसत क्षमता 1 में स्केल करने और एक छोटी और बड़ी बकेट के बीच बची हुई क्षमता को स्थानांतरित करने की व्याख्या करनी चाहिए।
सैंपलिंग संभावना को सिद्ध कर सकते हैं
उन्हें केवल कोड पढ़ने के बजाय यह दिखाना चाहिए कि यूनिफॉर्म बकेट चयन और एक एलियास जंप प्रत्येक आइटम को उसका लक्षित कुल क्षेत्र कैसे देता है।
संख्यात्मक और सीमा मामलों को संभाल सकते हैं
उन्हें शून्य वेट्स, शून्य कुल, फ्लोटिंग-पॉइंट क्लैंपिंग, हाफ-ओपन रैंडम रेंज, और एटॉमिक टेबल रिप्लेसमेंट को कवर करना चाहिए।
सही डेटा संरचना चुन सकते हैं
उन्हें बैच पुनर्निर्माण लागत की तुलना डायनामिक अपडेट से करनी चाहिए और यह जानना चाहिए कि एलियास टेबल के बजाय फेनविक ट्री या प्रीफिक्स सम का उपयोग कब करना है।