यादृच्छिक संख्या पीढ़ी पर मेरे पदों का विशाल बहुमत मुख्य रूप से विभिन्न पीढ़ी योजनाओं के गुणों से निपटता है। यह अप्रत्याशित हो सकता है, लेकिन रैंडमाइजेशन एल्गोरिदम का प्रदर्शन चुनी हुई पीढ़ी योजना पर नहीं, बल्कि अन्य कारकों पर निर्भर हो सकता है। इस पोस्ट में (जो मैं
डैनियल लेमर द्वारा एक उत्कृष्ट
लेख से प्रेरित था), हम यादृच्छिक संख्या पीढ़ी के प्रदर्शन में गिरावट के मुख्य कारणों की जांच करेंगे, जो अक्सर पीआरएन इंजन के प्रदर्शन से आगे निकल जाते हैं।
इस स्थिति की कल्पना करें:
होमवर्क के रूप में, जुआन और साशा सी ++ में समान यादृच्छिक एल्गोरिदम को लागू करते हैं, जो एक ही विश्वविद्यालय के कंप्यूटर पर और एक डेटा सेट के साथ चलेगा। उनका कोड लगभग समान है और केवल यादृच्छिक संख्याओं की पीढ़ी में भिन्न है। जुआन अपने संगीत सबक के लिए जल्दी में है, इसलिए उसने बस मेर्सन बवंडर को चुना। दूसरी ओर, साशा ने कुछ अतिरिक्त घंटे शोध में बिताए। साशा ने कई सबसे तेज़ PRNG के बेंचमार्क का संचालन किया, जिसे उन्होंने हाल ही में सोशल नेटवर्क से सीखा और सबसे तेज़ चुना। बैठक में, साशा डींग मारने के लिए अधीर थी, और उन्होंने जुआन से पूछा: "आपने क्या PRNG सिस्टम का उपयोग किया था?"
"व्यक्तिगत रूप से, मैंने सिर्फ मेर्सन भंवर लिया - यह भाषा में बनाया गया है और बहुत अच्छा काम करता है।"
"हा!" साशा ने जवाब दिया। “मैंने
jsf32 इस्तेमाल किया। यह पुराने और धीमी Mersenne बवंडर की तुलना में बहुत तेज है! मेरा कार्यक्रम 3 मिनट 15 सेकंड में चलता है! "
"हम्म, बुरा नहीं है, लेकिन मेरा यह एक मिनट से भी कम समय में हो सकता है," जुआन कहते हैं और सिकुड़ते हैं। "तो ठीक है, मुझे कॉन्सर्ट में जाना है। क्या तुम मेरे साथ आओगे? ”
"नहीं," साशा जवाब देती है। "मैं ... उह ... मेरे कोड को फिर से देखने की जरूरत है।"
यह अजीब काल्पनिक स्थिति विशेष रूप से काल्पनिक
नहीं है ; यह वास्तविक परिणामों पर आधारित है। यदि आपका रैंडमाइज्ड अल्गोरिथम उतनी तेजी से नहीं चल रहा है जितना हम चाहेंगे, और अड़चन रैंडम नंबर जनरेशन लगती है, तो, अजीब तरह से, समस्या रैंडम नंबर जनरेटर में नहीं हो सकती है!
परिचय: अभ्यास में रैंडम नंबर
अधिकांश आधुनिक उच्च-गुणवत्ता वाले रैंडम नंबर जनरेटर रैंडम बिट्स से भरे मशीन शब्द बनाते हैं, अर्थात, वे आमतौर पर अंतराल में नंबर उत्पन्न करते हैं [0..2
32 ) या [0..2
64 )। लेकिन उपयोग के कई मामलों में, उपयोगकर्ताओं को एक निश्चित अंतराल में संख्याओं की आवश्यकता होती है - उदाहरण के लिए, मरने के लिए या यादृच्छिक प्लेइंग कार्ड चुनने के लिए, छोटे निरंतर अंतराल में संख्याओं की आवश्यकता होती है। हालांकि, कई एल्गोरिदम,
मिश्रण और
जलाशय के नमूने से लेकर
यादृच्छिक बाइनरी सर्च पेड़ों तक, अन्य अंतराल से लिए गए नंबरों की आवश्यकता होती है।
तरीकों
हम कई अलग-अलग तरीकों को देखेंगे। चर्चा को सरल बनाने के लिए, अंतराल [
i ..
j ) या [
i ..
j ] में संख्याएँ उत्पन्न करने के बजाय, हम अंतराल [0 ..
k ) में संख्याएँ उत्पन्न करेंगे। इस तरह की योजना होने पर, हम उदाहरण के लिए,
k =
j -
i को सेट करके अंतराल [
i ..
j ) में संख्याएँ उत्पन्न कर सकते हैं, अंतराल [0 ..
k ) में एक संख्या उत्पन्न करते हैं, और फिर
मुझे इसमें जोड़ते हैं।
अंतर्निहित C ++ उपकरण
कई भाषाओं में एक निर्दिष्ट अंतराल में एक यादृच्छिक संख्या प्राप्त करने के लिए अंतर्निहित उपकरण होते हैं। उदाहरण के लिए, पर्ल और पाइथन जैसी स्क्रिप्टिंग भाषाओं में 52 कार्ड वाले डेक से एक कार्ड को निकालने के लिए, हम
random.randint(0,52) int(rand(52)) और
random.randint(0,52) लिख सकते
random.randint(0,52) । [नोट।
CryptoPirate उपयोगकर्ता:
यह मुझे यहाँ एक त्रुटि लगती है, Python randint में (a, b) b से b सहित संख्या उत्पन्न करता है। और चूंकि डेक में 52 कार्ड हैं और पहला "0" है, यह रैंडम होना चाहिए। वृंद (0,51) ।] C ++ में, हम
uniform_int_distribution ही
uniform_int_distribution एक
uniform_int_distribution उपयोग कर सकते हैं।
इस दृष्टिकोण को लागू करने के लिए C ++ कोड सरल है:
uint32_t bounded_rand(rng_t& rng, uint32_t range) { std::uniform_int_distribution<uint32_t> dist(0, range-1); return dist(rng); }
आमतौर पर, नीचे वर्णित तकनीकों में से एक का उपयोग अंतर्निहित उपकरणों में किया जाता है, लेकिन अधिकांश उपयोगकर्ता इन उपकरणों का उपयोग करते हैं, न कि "हुड के नीचे" क्या हो रहा है, इस बारे में सोचकर, इन उपकरणों को सही ढंग से डिज़ाइन किया गया और काफी प्रभावी है। C ++ में, अंतर्निहित टूल अधिक जटिल हैं, क्योंकि उन्हें काफी मनमाने ढंग से पीढ़ी के इंजन के साथ काम करने में सक्षम होना चाहिए - एक जनरेटर जो -3 से 17 तक के मानों का उत्पादन करता है, वह काफी मान्य हो सकता है और इसका उपयोग
std::uniform_int_distribution साथ किया जा सकता है
std::uniform_int_distribution किसी भी अंतराल में संख्या बनाने के लिए, उदाहरण के लिए [0..1000)। यही है, अंतर्निहित C ++ उपकरण अधिकांश मामलों के लिए बहुत जटिल हैं जिनमें उनका उपयोग किया जाता है।
विभाजन का क्लासिक शेष (तिरछा)
आइए एक अति-सरलीकृत दृष्टिकोण से एक बहुत ही सरल दृष्टिकोण की ओर बढ़ें।
जब मैंने प्रोग्रामिंग का अध्ययन किया, तो हमने शेष ऑपरेटर का उपयोग करके अंतराल (उदाहरण के लिए, 52 कार्ड के एक डेक में कार्ड का चयन करने के लिए) में संख्याएं उत्पन्न कीं। अंतराल में संख्या प्राप्त करने के लिए [0..52), हमने
rand() % 52 लिखा।
C ++ में, इस दृष्टिकोण को निम्नानुसार लागू किया जा सकता है:
uint32_t bounded_rand(rng_t& rng, uint32_t range) { return rng() % range; }
इस दृष्टिकोण की सादगी के बावजूद, यह इस कारण को दर्शाता है कि सही अंतराल में नंबर प्राप्त करना आमतौर पर एक धीमा काम है - इसमें विभाजन की आवश्यकता होती है (
% ऑपरेटर द्वारा प्राप्त शेष की गणना करने के लिए)। डिवाइडिंग आमतौर पर अन्य अंकगणितीय ऑपरेशनों की तुलना में कम से कम परिमाण का एक क्रम है, इसलिए एक एकल अंकगणितीय ऑपरेशन एक तेज PRNG द्वारा किए गए सभी कार्यों से अधिक समय लेता है।
लेकिन कम गति के अलावा, यह
तिरछा भी है। यह समझने के लिए कि
rand() % 52 ने तिरछी संख्या में रिटर्न कैसे किया, मान लीजिए कि
rand() अंतराल में नंबर बनाता है [0..2
32 ), और ध्यान दें कि 52 पूरी तरह से 2
32 को विभाजित नहीं करता है, यह शेष के साथ 82 595 524 बार विभाजित करता है। 48. यही है, अगर हम
rand() % 52 उपयोग करते हैं, तो हमारे पास डेक से पहले 48 कार्डों का चयन करने के लिए 82 595 525 और अंतिम चार कार्डों का चयन करने के लिए केवल 82 595 524 तरीके होंगे। दूसरे शब्दों में, इन अंतिम चार कार्डों के खिलाफ 0.00000121% का तिरछा हिस्सा है (शायद ये राजा हैं!)। जब मैं एक छात्र था और पासा या ड्रॉइंग कार्ड फेंकने के बारे में होमवर्क लिखा था, तो किसी को आमतौर पर इस तरह के छोटे विकृतियों की परवाह नहीं थी, लेकिन अंतराल में वृद्धि के साथ, विरूपण रैखिक रूप से बढ़ता है। 32-बिट PRNG के लिए, 2
24 से कम के सीमित अंतराल में 0.5% से कम का तिरछा होता है, लेकिन 2
31 के ऊपर 50% का तिरछा - कुछ संख्या दूसरों की तुलना में दो बार वापस आ जाएगी।
इस लेख में, हम मुख्य रूप से उन तकनीकों पर विचार करेंगे जो एक व्यवस्थित त्रुटि को खत्म करने के लिए रणनीतियों का उपयोग करते हैं, लेकिन यह शायद यह कहने योग्य है कि 64-बिट PRNG के लिए, सामान्य अनुप्रयोगों में तिरछा मूल्य नगण्य होने की संभावना है।
एक और समस्या यह हो सकती है कि कुछ जनरेटर में कम बिट्स होते हैं। उदाहरण के लिए, GPRS परिवार Xoroshiro + और Xoshiro + के पास कम बिट्स हैं जो सांख्यिकीय परीक्षण पास नहीं करते हैं। जब हम
% 52 निष्पादित करते हैं (क्योंकि 52 सम है), हम आउटपुट पर सीधे कम-क्रम बिट पास करते हैं।
गुणा फ्लोटिंग पॉइंट नंबर (तिरछा)
एक अन्य सामान्य तकनीक PRNG का उपयोग है जो इन अंकों के बाद के वांछित अंतराल में रूपांतरण के साथ अंतराल में फ्लोटिंग पॉइंट नंबर उत्पन्न करता है। इस दृष्टिकोण का उपयोग पर्ल में किया जाता है, यह अंतर
int(rand(10)) का उपयोग करने के लिए अंतराल में एक पूर्णांक उत्पन्न करने के लिए [0..10) का उपयोग करके एक अस्थायी-बिंदु संख्या उत्पन्न करता है, जिसके बाद गोल होता है।
C ++ में, यह दृष्टिकोण इस तरह लिखा गया है:
static uint32_t bounded_rand(rng_t& rng, uint32_t range) { double zeroone = 0x1.0p-32 * rng(); return range * zeroone; }
(ध्यान दें कि
0x1.0p-32 2
-32 के लिए एक द्विआधारी फ्लोटिंग-पॉइंट स्थिरांक है, जिसका उपयोग हम अंतराल में एक यादृच्छिक पूर्णांक को बदलने के लिए करते हैं [0..2
32 ) इकाई अंतराल में दोगुना करने के लिए; इसके बजाय, हम
ldexp(rng(), -32) का उपयोग करके
ldexp(rng(), -32) रूपांतरण कर सकते हैं, लेकिन जब मैंने इस दृष्टिकोण को
ldexp(rng(), -32) किया, तो यह बहुत धीमा हो गया।)
यह दृष्टिकोण विभाजन के क्लासिक शेष के रूप में तिरछा है, लेकिन तिरछा अलग तरह से दिखाई देता है। उदाहरण के लिए, यदि हम अंतराल [0..52) में संख्याओं का चयन करते हैं, तो संख्या 0, 13, 26 और 39 एक बार दूसरों की तुलना में कम होती है।
यह संस्करण, जब 64 बिट्स का सामान्यीकरण, और भी अधिक अप्रिय है, क्योंकि इसके लिए एक अस्थायी बिंदु प्रकार की आवश्यकता होती है, जिसका मंटिसा कम से कम 64 बिट्स होता है। लिनक्स और macOS के साथ x86 मशीनों पर, हम बढ़े हुए सटीक x86 फ्लोटिंग-पॉइंट नंबरों का लाभ उठाने के लिए
long double का उपयोग कर सकते हैं, जिसमें 64-बिट मंटिसा है, लेकिन
long double सभी प्रणालियों में सार्वभौमिक रूप से पोर्ट नहीं की जाती है - कुछ प्रणालियों में,
long double बराबर है।
एक अच्छा पक्ष है - यह दृष्टिकोण कमजोर कम बिट के साथ PRNGs के लिए अवशिष्ट समाधानों की तुलना में तेज है।
पूर्णांक गुणा (तिरछा)
गुणन विधि को फ़्लोटिंग पॉइंट अंकगणित के बजाय नियत किया जा सकता है। वास्तव में, हम लगातार 2
32 से गुणा करते हैं,
uint32_t bounded_rand(rng_t& rng, uint32_t range) { uint32_t x = rng(); uint64_t m = uint64_t(x) * uint64_t(range); return m >> 32; }
ऐसा लग सकता है कि इस संस्करण में 64-बिट अंकगणित की आवश्यकता है, x86 प्रोसेसर पर एक अच्छा संकलक इस कोड को 32-बिट
mult इंस्ट्रक्शन में संकलित करेगा (जो हमें दो 32-बिट आउटपुट मान देता है, जिसमें से एक रिटर्न वैल्यू है)। इस संस्करण के तेज होने की उम्मीद की जा सकती है, लेकिन यह ठीक उसी तरह तिरछा है जैसे फ्लोटिंग पॉइंट संख्याओं को गुणा करने की विधि।
ड्रॉप डिवीजन (कोई तिरछा नहीं)
हम फ्लोटिंग पॉइंट गुणा स्कीम को एक डिवीजन आधारित स्कीम में बदल सकते हैं।
x * range / 2**32 को गुणा करने के बजाय
x * range / 2**32 हम
x / (2**32 / range) गणना करते हैं। चूँकि हम पूर्णांक अंकगणित के साथ काम कर रहे हैं, इसलिए इस संस्करण में गोलाई को अलग तरह से प्रदर्शित किया जाएगा, और कभी-कभी वांछित अंतराल के बाहर मान उत्पन्न करते हैं। यदि हम इन मूल्यों को छोड़ देते हैं (उदाहरण के लिए, उनसे छुटकारा पाएं और नए मूल्य उत्पन्न करें), तो परिणामस्वरूप हमें विकृतियों के बिना एक तकनीक मिलती है।
उदाहरण के लिए, 32-बिट PRNG का उपयोग करके कार्ड को बाहर निकालने के मामले में, हम एक 32-बिट संख्या उत्पन्न कर सकते हैं और इसे एक कार्ड का चयन करने के लिए 2 32/52 = 82 595 524 से विभाजित कर सकते हैं। यह तकनीक काम करती है यदि 32-बिट PRNG से यादृच्छिक मान 52 × 82595524 = 2 32/32 - 48 से कम है। यदि PRNR से यादृच्छिक मान जनरेटर अंतराल के ऊपरी भाग के अंतिम 48 मूल्यों में से एक है, तो आपको इसे त्यागने और किसी अन्य की तलाश करने की आवश्यकता है।
इस संस्करण के लिए हमारा कोड 64-बिट गणित का उपयोग किए बिना 2
32 को
range विभाजित करने के साथ एक चाल का उपयोग करता है।
2**32 / range की प्रत्यक्ष गणना के लिए
2**32 / range हमें नंबर 2
32 का प्रतिनिधित्व करना होगा, जो कि बहुत बड़ा है (एक से!) 32-बिट पूर्णांक के रूप में प्रतिनिधित्व करने के लिए। इसके बजाय, हम इस बात पर ध्यान देते हैं कि अहस्ताक्षरित पूर्णांकों के लिए, एकतरफा नकार ऑपरेशन
range 2
32 -
range सकारात्मक मान की गणना करता है; इस मान को
range विभाजित करने पर, हमें
2**32 / range से कम की प्रतिक्रिया मिलती है।
इसलिए, विभाजन और ड्रॉप का उपयोग करके संख्या उत्पन्न करने के लिए C ++ कोड इस तरह दिखता है:
uint32_t bounded_rand(rng_t& rng, uint32_t range) {
बेशक, इस दृष्टिकोण को विभाजन के आधार पर दो धीमी गति से संचालन की आवश्यकता होती है, जो आमतौर पर अन्य अंकगणितीय कार्यों की तुलना में धीमी होती हैं, इसलिए आपको इसके तेज होने की उम्मीद नहीं करनी चाहिए।
विभाजन के शेष (डबल) विकृतियों के बिना - ओपनबीएसडी तकनीक
क्लासिक डिवीजन शेष विधि में तिरछा खत्म करने के लिए हम ड्रॉप अप्रोच भी ले सकते हैं। प्लेइंग कार्ड्स के साथ उदाहरण में, हमें फिर से 48 मानों को छोड़ने की आवश्यकता है। इस संस्करण में,
पिछले 48 मानों को छोड़ने के बजाय, हम (समकक्ष)
पहले 48 मूल्यों को छोड़ देते हैं।
यहाँ C ++ में इस दृष्टिकोण का कार्यान्वयन है:
uint32_t bounded_rand(rng_t& rng, uint32_t range) {
यह तकनीक तिरछा हटाती है, लेकिन इसके लिए प्रत्येक आउटपुट मान के शेष के साथ दो समय लेने वाली डिवाइडिंग ऑपरेशन की आवश्यकता होती है (और आपको कई नंबर बनाने के लिए आंतरिक जनरेटर की आवश्यकता हो सकती है)। इसलिए, यह उम्मीद की जानी चाहिए कि विधि शास्त्रीय तिरछा दृष्टिकोण की तुलना में लगभग दो गुना धीमी होगी।
arc4random_uniform OpenBSD arc4random_uniform (जिसका उपयोग OS X और iOS पर भी किया जाता है) इस रणनीति का उपयोग करता है।
तिरछा के बिना विभाजन (एकल) का अवशेष - जावा पद्धति
जावा अंतराल में एक संख्या उत्पन्न करने के लिए एक अलग दृष्टिकोण का उपयोग करता है जो केवल एक शेष विभाजन ऑपरेशन का उपयोग करता है, परिणाम को छोड़ने के काफी दुर्लभ मामलों के अपवाद के साथ। कोड:
static uint32_t bounded_rand(rng_t& rng, uint32_t range) { uint32_t x, r; do { x = rng(); r = x % range; } while (x - r > (-range)); return r; }
यह समझने के लिए कि यह विकल्प क्यों काम करता है, आपको थोड़ा सोचने की जरूरत है। अवशिष्ट पर आधारित पिछले संस्करण के विपरीत, जो आंतरिक पीढ़ी के इंजन से सबसे कम मूल्यों के हिस्से को हटाकर पूर्वाग्रह को समाप्त करता है, यह संस्करण इंजन अंतराल के ऊपरी भाग से मूल्यों को फ़िल्टर करता है।
तिरछा पूर्णांक गुणा - लेमिरा विधि
उसी तरह से कि हमने पूर्वाग्रह को शेष विभाजन विधि से हटा दिया, हम पूर्णांक गुणन तकनीक से पूर्वाग्रह को समाप्त कर सकते हैं। इस तकनीक का आविष्कार लेमर ने किया था।
uint32_t bounded_rand(rng_t& rng, uint32_t range) { uint32_t t = (-range) % range; do { uint32_t x = rng(); uint64_t m = uint64_t(x) * uint64_t(range); uint32_t l = uint32_t(m); } while (l < t); return m >> 32; }
ड्रॉप बिटमास्क (कोई तिरछा नहीं) - ऐप्पल तकनीक
हमारे अंतिम दृष्टिकोण में, विभाजन और शेष संचालन पूरी तरह से समाप्त हो गए हैं। इसके बजाय, यह अंतराल में एक यादृच्छिक संख्या प्राप्त करने के लिए एक सरल मास्किंग ऑपरेशन का उपयोग करता है [0..2
k ), जहां
k सबसे छोटा मान है, जैसे कि 2
k अंतराल से अधिक है। यदि हमारे अंतराल के लिए मूल्य बहुत बड़ा है, तो हम इसे त्याग देते हैं और दूसरे को प्राप्त करने का प्रयास करते हैं। कोड नीचे दिखाया गया है:
uint32_t bounded_rand(rng_t& rng, uint32_t range) { uint32_t mask = ~uint32_t(0); --range; mask >>= __builtin_clz(range|1); uint32_t x; do { x = rng() & mask; } while (x > range); return x; }
इस दृष्टिकोण को Apple ने तब अपनाया जब (
arc4random_uniform सिएरा रिलीज़ में) ने
arc4random_uniform कोड का
अपना संशोधन किया।
बुनियादी तकनीकों को बेंचमार्क करना
अब हमारे पास कई दृष्टिकोण हैं जिनका मूल्यांकन किया जा सकता है। दुर्भाग्य से, जब हम एक एकल डिवीजन ऑपरेशन की लागतों के बारे में चिंतित होते हैं, तो बेंचमार्किंग एक गैर-तुच्छ चीज बन जाती है। कोई भी बेंचमार्क आवेदन के क्षेत्र को प्रभावित करने वाले सभी कारकों को ध्यान में नहीं रख सकता है, और इसमें कोई गारंटी नहीं है कि आपके आवेदन के लिए सबसे अच्छा विकल्प निश्चित रूप से मेरा सबसे अच्छा होगा।
हम तीन बेंचमार्क का उपयोग करते हैं और कई अलग-अलग PRNGs के साथ तकनीकों का परीक्षण करते हैं।
बेंचमार्क लार्ज-शफल
संभवतः सबसे स्पष्ट बेंचमार्क मिश्रण है। इस बेंचमार्क में, हम बड़े पैमाने पर मिश्रण का प्रदर्शन करते हैं। आकार
N की एक सरणी को सॉर्ट करने के लिए
, हमें अंतराल [0 ..
N ), [0 .. (
N -1)), ..., [0..1) में नंबर जेनरेट करने होंगे। इस मानदंड में, हम मान लेंगे कि
एन अधिकतम संभव संख्या है (
uint32_t यह 2
32 -1 है)। कोड:
for (uint32_t i = 0xffffffff; i > 0; --i) { uint32_t bval = bounded_rand(rng, i); assert(bval < i); sum += bval; }
ध्यान दें कि हम प्रत्येक संख्या को जोड़कर उसका उपयोग करते हैं (ताकि इसे अनुकूलन द्वारा नहीं फेंका जाएगा), लेकिन हम संख्याओं की पीढ़ी पर ध्यान केंद्रित करने के लिए कोई मिश्रण नहीं करते हैं।
64-बिट पीढ़ी का परीक्षण करने के लिए, हमारे पास एक समान परीक्षण है, लेकिन आकार में 2
64 - 1 की सरणी को मिलाकर एक परीक्षण करना अव्यावहारिक होगा (क्योंकि इस बड़े बेंचमार्क को पूरा करने में कई हजारों साल लगेंगे)। इसके बजाय, हम पूरे 64-बिट अंतराल को पार करते हैं, लेकिन 32-बिट परीक्षण में उतने ही आउटपुट मान उत्पन्न करते हैं। कोड:
for (uint32_t i = 0xffffffff; i > 0; --i) { uint64_t bound = (uint64_t(i)<<32) | i; uint64_t bval = bounded_rand(rng, bound ); assert(bval < bound); sum += bval; }
Mersenne भंवर परिणाम
नीचे दिखाए गए परिणाम इस बेंचमार्क के प्रदर्शन को प्रदर्शित करते हैं, जिनमें से प्रत्येक के लिए हमने जांच की, जब मेर्सन भंवर का उपयोग कर रहे थे और 32-बिट कोड पर परीक्षण कर रहे थे (
libstdc++ से
std::mt19937 का उपयोग करके) और समान 64-बिट कोड (
std:mt19937_64 का उपयोग कर
std:mt19937_64 libstdc++ )। परिणाम विभिन्न बीज मूल्यों के साथ 15 रन के ज्यामितीय माध्य हैं, जो तब सामान्यीकृत होता है ताकि शास्त्रीय विभाजन शेष विधि का एक ही रन समय हो।
ऐसा लग सकता है कि प्रदर्शन के बारे में हमारे पास स्पष्ट उत्तर हैं - ऐसा लगता है कि आप उनकी पूर्णता के लिए तकनीकों का निर्माण कर सकते हैं, और अपने आप से पूछ सकते हैं कि 32-बिट संख्याओं के लिए इस तरह के भयानक कार्यान्वयन को लिखने के बारे में
libstdc++ डेवलपर्स क्या सोच रहे थे। लेकिन, जैसा कि अक्सर बेंचमार्किंग के मामले में होता है, इन परिणामों से लगता है कि स्थिति अधिक जटिल है। सबसे पहले, एक जोखिम है कि परिणाम Mersenne भंवर के लिए विशिष्ट हो सकते हैं, इसलिए हम कई परीक्षण किए गए PRNNs का विस्तार करेंगे। दूसरे, बेंचमार्क के साथ एक सूक्ष्म समस्या हो सकती है। आइए पहले प्रश्न से पहले निपटें।
विभिन्न PRNG के परिणाम
हम 32-बिट
arc4_rand32 को
arc4_rand32 ,
chacha8r ,
gjrand32 ,
jsf32 ,
mt19937 ,
pcg32 ,
pcg32_fast ,
sfc32 ,
splitmix32 ,
xoroshiro64+ ,
xorshift*64/32 xoshiro128+ ,
xoshiro128+ और
xoshiro128** /
xoshiro128+ jsf64 ,
mcg128 ,
mcg128_fast ,
mt19937_64 ,
pcg64 ,
pcg64_fast ,
sfc64 ,
splitmix64 ,
xoroshiro128+ ,
xorshift*128/64 xoshiro256+ ,
xoshiro256+ और
xoshiro256* । ये किट हमें कुछ धीमी गति से PRN और बहुत तेज गति प्रदान करेंगे।
यहाँ परिणाम हैं:
हम Mersenne भंवर के साथ परिणामों से महत्वपूर्ण अंतर देख सकते हैं। तेज़ PRNGs बाउंडिंग कोड की ओर संतुलन को स्थानांतरित करते हैं, और इसलिए विभिन्न दृष्टिकोणों के बीच का अंतर अधिक स्पष्ट हो जाता है, खासकर 64-बिट PRNRs के मामले में।
libstc++ व्यापक सेट के
libstc++ कार्यान्वयन इतना भयानक प्रतीत होता है।
निष्कर्ष
एक महत्वपूर्ण मार्जिन द्वारा इस बेंचमार्क में, पूर्वाग्रह के साथ गुणा पर आधारित दृष्टिकोण गति में जीतता है। ऐसी कई परिस्थितियां हैं जिनमें सीमाएं PRNG के आकार के सापेक्ष छोटी होंगी, और प्रदर्शन बिल्कुल महत्वपूर्ण है। ऐसी स्थितियों में, एक मामूली पूर्वाग्रह को ध्यान देने योग्य प्रभाव होने की संभावना नहीं है, लेकिन PRNG की गति होगी। इस तरह का एक उदाहरण यादृच्छिक संदर्भ बिंदु के साथ क्विकॉर्ट है। तिरछी विधियों में से, बिटमस्क तकनीक आशाजनक दिखती है।
लेकिन गंभीर निष्कर्ष निकालने से पहले, हमें इस बेंचमार्क की भारी समस्या को इंगित करने की आवश्यकता है - ज्यादातर समय बहुत उच्च सीमाओं पर बिताया जाता है, जो कि बड़े अंतराल के लिए सबसे अधिक संभावना देता है। इसलिए, हमें दूसरे बेंचमार्क पर जाने की जरूरत है।
बेंचमार्क स्मॉल-शफल
यह बेंचमार्क पिछले वाले के समान है, लेकिन बहुत कम "एरे मिक्सिंग" (मल्टीपल) करता है। कोड: for (uint32_t j = 0; j < 0xffff; ++j) { for (uint32_t i = 0xffff; i > 0; --i) { uint32_t bval = bounded_rand(rng, i); assert(bval < i); sum += bval; } }
Mersenne भंवर परिणाम
विभिन्न PRNG के परिणाम
निष्कर्ष
यह बेंचमार्क बड़ी सीमाओं पर बहुत अधिक जोर देने से बचता है और अधिक सटीक रूप से वास्तविक दुनिया के उपयोग के मामलों को दर्शाता है, लेकिन अब पूरी तरह से बड़ी सीमाओं का खुलासा करता है।सभी अंतराल के लिए बेंचमार्क
इस बेंचमार्क का उद्देश्य पिछले दो के नुकसान से बचना है; वह दो के शक्ति के प्रत्येक आकार पर परीक्षण करता है ताकि प्रत्येक आकार मौजूद हो, लेकिन उसके प्रभाव को कम करके आंका नहीं जाता है। for (uint32_t bit = 1; bit != 0; bit <<= 1) { for (uint32_t i = 0; i < 0x1000000; ++i) { uint32_t bound = bit | (i & (bit - 1)); uint32_t bval = bounded_rand(rng, bound); assert(bval < bound); sum += bval; } }
Mersenne भंवर परिणाम
विभिन्न PRNG के परिणाम
निष्कर्ष
हमारे कई निष्कर्ष अपरिवर्तित रहे हैं। तिरछा तरीका त्वरित है यदि हम त्रुटि के साथ रख सकते हैं, और बिटमास्क योजना एक अच्छा औसत विकल्प लगता है।हम इसे समाप्त कर सकते हैं यदि हम वापस नहीं जाना चाहते हैं, हमारे कोड पर एक महत्वपूर्ण नज़र डालें और इसमें बदलाव करें।सुधार करें
इस बिंदु तक, सभी तिरछा उन्मूलन विधियों को एक अतिरिक्त विभाजन शेष संचालन के उपयोग की आवश्यकता होती है, यही कारण है कि उन्हें तिरछी विधियों की तुलना में बहुत अधिक धीरे-धीरे प्रदर्शन किया जाता है। यह उपयोगी होगा यदि हम इस लाभ को कम कर सकते हैं।तेज़ थ्रेशोल्ड आधारित ड्रॉप
हमारे कुछ एल्गोरिदम में एक सीमा मूल्य का उपयोग करके कोड है, उदाहरण के लिए: uint32_t bounded_rand(rng_t& rng, uint32_t range) {
जब rangePRNG आउटपुट अंतराल की तुलना में छोटा होता है, तो अक्सर संख्या थ्रेशोल्ड की तुलना में बहुत बड़ी होगी । यही है, अगर हम दहलीज का प्रारंभिक अनुमान जोड़ सकते हैं, जो थोड़ा अधिक हो सकता है, तो हम शेष विभाजन को लेने के महंगे संचालन पर बचत करेंगे।निम्नलिखित कोड इस कार्य को संभालता है: uint32_t bounded_rand(rng_t& rng, uint32_t range) { uint32_t r = rng(); if (r < range) { uint32_t t = (-range) % range; while (r < t) r = rng(); } return r % range; }
यह परिवर्तन "विकृतियों के बिना डबल मॉड" (ऊपर देखें), और "विकृतियों के बिना पूर्णांक गुणन" दोनों पर लागू किया जा सकता है। इस विचार का आविष्कार लेमिर ने किया था, जिसने इसे दूसरी विधि (लेकिन पहली नहीं) पर लागू किया था।लार्ज-शफल बेंचमार्क परिणाम
यह अनुकूलन 64-बिट बेंचमार्क (जिसमें मॉड धीमा है) के परिणामों में एक महत्वपूर्ण सुधार की ओर जाता है, लेकिन वास्तव में 32-बिट बेंचमार्क में प्रदर्शन को थोड़ा कम करता है। सुधारों के बावजूद, बिटमास्क विधि अभी भी जीतती है।लघु-शफल बेंचमार्क परिणाम
दूसरी ओर, यह परिवर्तन पूर्णांक गुणन की विधि और विभाजन विधि के दोहरे शेष दोनों के लिए छोटे फेरबदल बेंचमार्क को काफी तेज करता है। दोनों मामलों में, उनका प्रदर्शन विकृतियों के बिना विकल्पों के परिणामों के करीब हो जाता है। डबल अवशेष विधि (ओपनबीएसडी) का प्रदर्शन अब एकल अवशेष विधि (जावा) के प्रदर्शन के लगभग बराबर है।बेंचमार्क सभी अंतराल के लिए परिणाम है
हम सभी अंतरालों के लिए बेंचमार्क में एक समान सुधार देखते हैं।ऐसा लगता है कि हम एक नए सार्वभौमिक विजेता की घोषणा कर सकते हैं: तिरछा किए बिना लेमायर पूर्णांक को गुणा करने के लिए एक अनुकूलित तरीका।विभाजन शेष अनुकूलन
आमतौर पर, एक गणना में a % bविभाजन की आवश्यकता होती है, लेकिन उन स्थितियों में जहां a < bपरिणाम सरल होता है aऔर विभाजन की आवश्यकता नहीं होती है। और जब a/2 < b, परिणाम सरल है a - b। इसलिए, कंप्यूटिंग के बजाय a %= b;
हम पूरा कर सकते हैं if (a >= b) { a -= b; if (a >= b) a %= b; }
विभाजन की लागत इतनी महत्वपूर्ण है कि इस अधिक जटिल कोड की लागत में वृद्धि विभाजन की कमी के कारण समय की बचत करके खुद को सही ठहरा सकती है।लार्ज-शफल बेंचमार्क परिणाम
इस अनुकूलन को जोड़ने से बड़े-फेरबदल बेंचमार्क के परिणामों में सुधार होता है। यह 64-बिट कोड में फिर से अधिक ध्यान देने योग्य है, जहां शेष लेने का संचालन अधिक महंगा है। डबल-शेष विधि (ओपनबीएसडी-शैली) केवल एक शेष संचालन और दोनों के लिए अनुकूलन के साथ संस्करण दिखाती है।इस बेंचमार्क में, बिट मास्क अभी भी विजेता है, लेकिन इसके और लमीरा के दृष्टिकोण के बीच की सीमा काफी कम हो गई है।लघु-शफल बेंचमार्क परिणाम
इस अनुकूलन को जोड़ने से छोटे-फेरबदल बेंचमार्क के प्रदर्शन में वृद्धि नहीं होती है, इसलिए सवाल केवल यह रहता है कि क्या यह महत्वपूर्ण लागत जोड़ता है। कुछ मामलों में, नहीं, दूसरों में, लागत थोड़ी बढ़ जाती है।बेंचमार्क सभी अंतराल के लिए परिणाम है
सभी अंतरालों के लिए बेंचमार्क में, परिवर्तन भी छोटे हैं।बोनस: PRSP तुलना परिणाम
अंतराल में संख्या योजनाओं के परीक्षण के लिए बहुत सारे PRNG का उपयोग करने का मुख्य कारण व्यक्तिगत PRNG योजनाओं के संचालन की ख़ासियत के कारण परिणामों की अनजाने विकृति से बचना था। लेकिन हम आंतरिक परीक्षणों के समान परिणामों का उपयोग खुद पीढ़ी की योजनाओं की तुलना करने के लिए कर सकते हैं।32-बिट आउटपुट के साथ PRNG
नीचे दिया गया ग्राफ़ विभिन्न 32-बिट पीढ़ी की योजनाओं के प्रदर्शन को दिखाता है, सभी तरीकों और पंद्रह रनों के लिए औसतन, 32-बिट मेर्सेन भंवर के प्रदर्शन के लिए सामान्यीकृत:एक तरफ, मुझे यह देखकर खुशी हुई कि यह pcg32_fastवास्तव में तेज़ है - यह केवल जोसेरो के एक छोटे संस्करण (जो सांख्यिकीय परीक्षण पास नहीं करता है) से पराजित हुआ था। लेकिन इससे यह भी पता चलता है कि आधुनिक उच्च-प्रदर्शन सामान्य-उद्देश्य PRSPs के प्रदर्शन के कारण मैं शायद ही कभी परेशान हो जाता हूं - विभिन्न तरीकों के बीच अंतर बहुत ही महत्वहीन है। विशेष रूप से, सबसे तेज़ चार सर्किट 5% से कम प्रदर्शन में भिन्न होते हैं, और मेरा मानना है कि यह केवल "शोर" के कारण होता है।64-बिट नंबरों के आउटपुट के साथ PRNG
ग्राफ सभी तकनीकों के बीच औसतन 64-बिट पीढ़ी की योजनाओं के प्रदर्शन को दिखाता है और पंद्रह रन 32-बिट मेरसेन भंवर के प्रदर्शन को सामान्यीकृत करता है। यह अजीब लग सकता है कि 32-बिट मेरसेन भंवर का उपयोग करके सामान्यीकरण किया जाता है, लेकिन यह हमें 64-बिट पीढ़ी का उपयोग करने की अतिरिक्त लागत को उन मामलों में देखने की अनुमति देता है जहां 32-बिट पीढ़ी पर्याप्त है।ये परिणाम इस बात की पुष्टि करते हैं कि यह mcg128_fastअविश्वसनीय रूप से तेज़ है, लेकिन अंतिम चार तकनीकों में फिर से लगभग 5% ही अंतर है, इसलिए सबसे तेज़ तरीकों से चुनना मुश्किल है। pcg64और pcg64_fastधीमा होना चाहिए mcg128_fastक्योंकि उनके मूल जनरेटर 128-बिट रैखिक संयुग्मक जनरेटर (LCG) और 128-बिट गुणक अनुरूप जनरेटर (MCG, MCG) हैं। इस तथ्य के बावजूद कि वे इस सेट में सबसे तेज तकनीक नहीं हैं, वे pcg64अभी भी 64-बिट मेर्सेन भंवर की तुलना में 20% तेज हैं।लेकिन शायद अधिक महत्वपूर्ण बात, ये परिणाम यह भी बताते हैं कि यदि आपको 64-बिट आउटपुट की आवश्यकता नहीं है, तो 64-बिट PRNG आमतौर पर 32-बिट वाले की तुलना में धीमा है।निष्कर्ष
हमारे बेंचमार्क से, हम देख सकते हैं कि PRNG के लिए मानक रूप से इस्तेमाल किए जाने वाले PRNGs (उदाहरण के लिए, 32-बिट Mersenne भंवर) से संक्रमण ने तेजी से बेंचमार्क के निष्पादन समय को 45% कम कर दिया है। लेकिन हमारी सबसे तेज़ विधि के अंतराल में संख्या खोजने की मानक विधि से संक्रमण ने हमें बेंचमार्क समय को लगभग 66% कम करने की अनुमति दी; दूसरे शब्दों में, मूल समय के एक तिहाई तक।सबसे तेज़ विधि (विकृतियों के बिना) लेमिरा विधि (मेरे अतिरिक्त अनुकूलन के साथ) है। यहाँ यह है: uint32_t bounded_rand(rng_t& rng, uint32_t range) { uint32_t x = rng(); uint64_t m = uint64_t(x) * uint64_t(range); uint32_t l = uint32_t(m); if (l < range) { uint32_t t = -range; if (t >= range) { t -= range; if (t >= range) t %= range; } while (l < t) { x = rng(); m = uint64_t(x) * uint64_t(range); l = uint32_t(m); } } return m >> 32; }
Lemira विधि का उपयोग करने से सबसे यादृच्छिक एल्गोरिदम के प्रदर्शन में सुधार होगा जो एक तेज पीढ़ी के इंजन से तेजी से एक तक बढ़ रहा है।परिशिष्ट: परीक्षण नोट्स
सभी परीक्षणों का कोड GitHub पर पोस्ट किया गया है । कुल मिलाकर, मैंने दो bounded_randअलग-अलग कंपाइलरों (जीसीसी 8 और एलएलवीएम 6) में 26 अलग-अलग पीआरएन (13 32-बिट पीआरएन और 13 64-बिट) का उपयोग करने के लिए 23 तरीकों का परीक्षण किया , जिससे मुझे 26 * 23 * 2 = 1196 निष्पादन फाइलें मिलीं, प्रत्येक जिनमें से यह उसी 15 बीज के साथ किया गया था, जो 1196 * 15 = 17,940 अद्वितीय परीक्षण रन देता है, जिनमें से प्रत्येक में तीन बेंचमार्क संयुक्त हैं। मूल रूप से, मैंने चार-2.1 गीगाहर्ट्ज़ एक्सॉन E7-4830v3 प्रोसेसर के साथ 48-कोर मशीन पर परीक्षण चलाया। परीक्षणों के एक पूरे सेट को निष्पादित करने में प्रोसेसर समय के एक महीने से थोड़ा कम समय लगा।अंत में, हम लेख की शुरूआत से स्थिति पर लौटते हैं। कल्पना कीजिए कि साशा ने इस्तेमाल किया jsf32.STD-libc++, और जुआन -mt19937.BIASED_FP_MULT_SCALE। बेंचमार्क 3 में, बाद में 69.6% कम समय लगता है। यही है, इस काल्पनिक स्थिति से समय वास्तविकता से डेटा पर आधारित है।