जलाशय नमूना एल्गोरिथ्म

टैंक नमूना (संलग्न। "जलाशय नमूना") अग्रिम में बड़े और / या अज्ञात आकार के मौजूदा वेक्टर से तत्वों की एक निश्चित संख्या को बेतरतीब ढंग से नमूना करने के लिए एक सरल और कुशल एल्गोरिदम है। मुझे इस एल्गोरिथ्म के बारे में Habré पर कोई लेख नहीं मिला और इसलिए मैंने इसे स्वयं लिखने का निर्णय लिया।

तो, हम किस बारे में बात कर रहे हैं। वेक्टर से एक यादृच्छिक तत्व का चयन एक प्राथमिक कार्य है:

// C++ std::random_device rd; std::mt19937 gen(rd()); std::uniform_int_distribution<> dis(0, vect.size() — 1); auto result = vect[dis(gen)]; 

"आकार एन के एक वेक्टर से कश्मीर यादृच्छिक तत्वों को लौटाने" का कार्य पहले से ही मुश्किल है। यहां आप पहले से ही एक गलती कर सकते हैं - उदाहरण के लिए, K पहले तत्वों को लें (यह यादृच्छिकता की आवश्यकता का उल्लंघन करता है) या प्रायिकता K / N के साथ प्रत्येक तत्व को लेते हैं (यह बिल्कुल K तत्वों को लेने की आवश्यकता का उल्लंघन करता है)। इसके अलावा, औपचारिक रूप से सही लागू करना संभव है, लेकिन बेहद अप्रभावी समाधान "बेतरतीब ढंग से सभी तत्वों को मिलाते हैं और के पहले लेते हैं।" और सब कुछ और भी दिलचस्प हो जाता है अगर हम इस शर्त को जोड़ते हैं कि एन बहुत बड़ी संख्या है (हमारे पास सभी एन तत्वों को बचाने के लिए पर्याप्त मेमोरी नहीं है) और / या अग्रिम में ज्ञात नहीं है। उदाहरण के लिए, कल्पना करें कि हमारे पास किसी प्रकार की बाहरी सेवा है जो हमें एक समय में एक तत्व भेजती है। हम नहीं जानते कि उनमें से कितने लोग आएंगे, और हम उन सभी को नहीं बचा सकते हैं, लेकिन हम चाहते हैं कि किसी भी समय प्राप्त होने वाले लोगों से बिल्कुल K चयनित यादृच्छिक तत्वों का एक सेट हो।

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

चलो एक सरलीकृत कार्य के साथ शुरू करते हैं।

आज्ञा देना K = 1, अर्थात्। हमें आवक से केवल एक तत्व का चयन करने की आवश्यकता है - लेकिन इसलिए कि आने वाले प्रत्येक तत्व को चयनित होने की समान संभावना थी। एल्गोरिथ्म खुद सुझाव देता है:

चरण 1 : बिल्कुल एक तत्व को मेमोरी आवंटित करें। हम इसमें बचत करते हैं पहला तत्व आ गया है।



अब तक, सब कुछ ठीक है - केवल एक तत्व हमारे पास आया है, 100% की संभावना के साथ (फिलहाल) इसे चुना जाना चाहिए - यह है।

चरण 2 : दूसरे आने वाले तत्व को चयनित 1 के रूप में 1/2 की संभावना के साथ फिर से लिखा गया है।



यहां भी, सब कुछ ठीक है: अब तक, केवल दो तत्व हमारे पास आए हैं। पहले वाले को 1/2 की संभावना के साथ चुना गया, दूसरे ने इसे 1/2 की संभावना के साथ फिर से लिखा।

चरण 3 : 1/3 की संभावना वाले तीसरे आने वाले तत्व को फिर से चयनित के रूप में लिखा गया है।



तीसरे तत्व के साथ सब कुछ ठीक है - इसके चुने जाने की संभावना ठीक 1/3 है। लेकिन क्या हमने किसी भी तरह से पिछले तत्वों की समान संभावना का उल्लंघन किया है? नहीं। इस चरण में चयनित आइटम को अधिलेखित नहीं किए जाने की संभावना 1 - 1/3 = 2/3 है। और चूंकि चरण 2 में हमने चयनित होने वाले प्रत्येक तत्वों के लिए समान अवसरों की गारंटी दी है, तो चरण 3 के बाद उनमें से प्रत्येक को 2/3 * 1/2 = 1/3 के अवसर के साथ चुना जा सकता है। तीसरे तत्व के समान ही मौका।

चरण एन : 1 / एन की संभावना के साथ, तत्व नंबर एन को चयनित के रूप में फिर से लिखा गया है। पिछले आइटम में से प्रत्येक के पास चयनित रहने के लिए समान 1 / N मौका है।



लेकिन K = 1 के साथ यह एक सरलीकृत कार्य था।

K> 1 के लिए एल्गोरिथ्म कैसे बदलेगा?

चरण 1 : हम K तत्वों पर मेमोरी आवंटित करते हैं। हम इसमें लिखते हैं कि पहले K तत्व आए थे।



K तत्वों से K तत्व लेने का एकमात्र तरीका उन सभी को लेना है :)

चरण एन : (प्रत्येक एन> के लिए): 1 से एन तक एक यादृच्छिक संख्या एक्स उत्पन्न करें। यदि एक्स> के तो हम इस तत्व को छोड़ देते हैं और अगले पर जाते हैं। यदि X <= K, तो X के साथ तत्व को फिर से लिखें। चूंकि X का मान समान रूप से 1 से N तक की सीमा में होगा, शर्त X <= K के तहत यह 1 से K तक की सीमा में समान रूप से यादृच्छिक होगा। इस प्रकार, हम एकरूपता सुनिश्चित करते हैं। पुन: लिखने योग्य वस्तुओं का चयन।



जैसा कि आप देख सकते हैं, आने वाले प्रत्येक अगले तत्व का चयन किए जाने की कम और कम संभावना है। फिर भी, यह हमेशा K / N होगा (पिछले तत्वों में से प्रत्येक के लिए)।

इस एल्गोरिथ्म का लाभ यह है कि हम किसी भी समय रोक सकते हैं, उपयोगकर्ता को वर्तमान वेक्टर के दिखा सकते हैं - और यह आने वाले तत्वों के अनुक्रम से ईमानदारी से चयनित यादृच्छिक तत्वों का वेक्टर होगा। शायद यह उपयोगकर्ता को सूट करेगा, या शायद वह आने वाले मूल्यों को संसाधित करना जारी रखना चाहेगा - हम किसी भी समय ऐसा कर सकते हैं। इस मामले में, जैसा कि शुरुआत में बताया गया है, हम कभी भी O (K) मेमोरी से अधिक का उपयोग नहीं करते हैं।

अरे हाँ, मैं पूरी तरह से भूल गया, एसटीडी :: नमूना फ़ंक्शन, जो वास्तव में ऊपर वर्णित किया गया है, आखिरकार मानक सी 17 लाइब्रेरी में शामिल है। मानक इसे केवल जलाशय के नमूने का उपयोग करने के लिए उपकृत नहीं करता है, लेकिन यह O (N) चरणों में काम करने के लिए बाध्य करता है - ठीक है, यह संभावना नहीं है कि मानक पुस्तकालय में इसके कार्यान्वयन के डेवलपर्स कुछ एल्गोरिदम का चयन करेंगे जो O (K) मेमोरी से अधिक का उपयोग करता है (और कम भी विफल होगा। - परिणाम कहीं संग्रहीत करने की आवश्यकता है)।

संबंधित सामग्री

• आंतरिक कोड आधार (34 वें मिनट से) का उपयोग करके उनके खोज इंजन में जलाशय का नमूना कैसे उपयोग किया गया, इस पर फेसबुक डेवलपर रिपोर्ट ।
• विकिपीडिया लेख
• std :: cppreference पर नमूना