मूल्यों के बहुत बड़े सेट से तेजी से भारित यादृच्छिक चयन

Question

मैं वर्तमान में एक समस्या पर काम कर रहा हूं जिसके लिए एक सेट से किसी तत्व के यादृच्छिक चयन की आवश्यकता होती है। प्रत्येक तत्व में वजन (चयन संभावना) से जुड़ा होता है।

मेरी समस्या यह है कि तत्वों की एक छोटी संख्या के साथ सेट के लिए 5-10 कहते हैं, समाधान की जटिलता (चलने का समय) स्वीकार्य था, हालांकि तत्वों की संख्या 1K या 10K आदि के लिए कहती है, चलने का समय अस्वीकार्य हो जाता है।

मेरे वर्तमान रणनीति है:

1. श्रृंखला के साथ यादृच्छिक मान एक्स का चयन करें [0,1)
2. दोहराएं तत्वों उनके वजन संक्षेप जब तक योग
3. तत्व है जो योग की वजह से एक्स से अधिक है एक्स से अधिक होने के लिए चुना गया है और

बड़े सेटों और चयनों की एक बड़ी संख्या के लिए यह प्रक्रिया वर्गबद्ध व्यवहार को प्रदर्शित करने के लिए शुरू होती है, संक्षेप में एक तेज़ तरीका है? शायद एक बेहतर एल्गोरिदम?

Answer 1

मानते हैं कि तत्व भार तय किए गए हैं, आप प्रीकंप्यूटेड रकम के साथ काम कर सकते हैं। यह घनत्व समारोह की बजाय सीधे संचयी संभाव्यता फ़ंक्शन के साथ काम करने जैसा है।

लुकअप को बाइनरी खोज के रूप में कार्यान्वित किया जा सकता है, और इसलिए तत्वों की संख्या में लॉग (एन) होना चाहिए।

एक द्विआधारी खोज को वजन के कंटेनर को यादृच्छिक_एक्स की आवश्यकता होती है।

वैकल्पिक रूप से, std::map<> और upper_bound() विधि का उपयोग करें।

#include <iostream> 
#include <map> 
#include <stdlib.h> 

int main() 
{ 
    std::map<double, char> cumulative; 
    typedef std::map<double, char>::iterator It; 

    cumulative[.20]='a'; 
    cumulative[.30]='b'; 
    cumulative[.40]='c'; 
    cumulative[.80]='d'; 
    cumulative[1.00]='e'; 

    const int numTests = 10; 
    for(int i = 0; 
     i != numTests; 
     ++i) 
    { 
     double linear = rand()*1.0/RAND_MAX; 
     std::cout << linear << "\t" << cumulative.upper_bound(linear)->second << std::endl; 
    } 

    return 0; 
} 

Answer 2

आप वॉकर एल्गोरिदम का उपयोग करना चाहते हैं। एन तत्वों के साथ, ओ (एन) की एक सेट-अप लागत है। हालांकि, नमूना लागत ओ (1) है।

• ए जे वाकर, असतत यादृच्छिक चर और जनरल वितरण, एसीएम TOMS 3, 253-256 (1977) उत्पन्न करने के लिए एक कुशल विधि देखें।
• Knuth, TAOCP, वॉल्यूम 2, सेक्शन 3.4.1.ए.

a RandomLib की RandomSelect वर्ग इस एल्गोरिथ्म लागू करता है।

Answer 3

यदि आपके पास एक यादृच्छिक तत्व को समान रूप से नमूना देने का एक त्वरित तरीका है, तो आप अस्वीकृति नमूनाकरण का उपयोग कर सकते हैं; आपको केवल इतना जानने की जरूरत है कि अधिकतम वजन है। यह निम्नानुसार काम करेगा: मान लें कि अधिकतम वजन एम है। [0,1] में एक संख्या एक्स को समान रूप से चुनें। नमूना तत्व बार-बार जब तक आप उस व्यक्ति को नहीं पाते जिसका वजन कम से कम एम * एक्स है; इसे चुनें

या, अनुमानित समाधान: यादृच्छिक रूप से 100 तत्वों को समान रूप से चुनें; इस सेट के भीतर वजन के अनुपात में एक आनुपातिक चुनें।