प्रक्रियात्मक सामग्री के लिए फास्ट छद्म यादृच्छिक संख्या जनरेटर

Question

मैं एक छद्म यादृच्छिक संख्या जनरेटर की तलाश में हूं जो प्रत्येक नंबर उत्पन्न करने से पहले बीज देने पर तेज़ी से काम करने के लिए विशिष्ट होगा। अधिकांश जेनरेटर मैंने अब तक देखा है कि आप एक बार बीज सेट करते हैं और फिर संख्याओं का एक लंबा अनुक्रम उत्पन्न करते हैं। एकमात्र चीज जो कुछ हद तक दिखती है, मैंने अब तक देखा है पर्लिन शोर है, लेकिन यह बहुत "चिकनी" डेटा उत्पन्न करता है - इसी तरह के इनपुट के लिए यह समान परिणाम उत्पन्न करता है।

जनरेटर की घोषणा की तरह कुछ दिखना चाहिए:

int RandomNumber1(int seed); 

या:

int RandomNumber3(int seedX, int seedY, int seedZ); 

मैं अच्छा RandomNumber1, पर्याप्त होना चाहिए के रूप में यह अपनी आदानों hashing द्वारा RandomNumber3 लागू करने के लिए संभव है होने लगता है और परिणाम को RandomNumber1 में पास कर दिया, लेकिन कुछ कार्यान्वयन स्वतंत्र इनपुट का उपयोग करने के मामले में मैंने दूसरा प्रोटोटाइप लिखा था।

इस जनरेटर के लिए इच्छित उपयोग प्रक्रियात्मक सामग्री जेनरेटर के लिए इसका उपयोग करना है, जैसे कि एक ग्रिड में पेड़ लगाकर और एक यादृच्छिक वृक्ष प्रजातियों और प्रत्येक स्थान के लिए यादृच्छिक स्थानिक ऑफसेट निर्धारित करके जंगल पैदा करना।

जनरेटर को बहुत ही कुशल (500 सीपीयू चक्र से नीचे) होना आवश्यक है, क्योंकि प्रक्रियात्मक सामग्री प्रतिपादन के दौरान वास्तविक समय में बड़ी मात्रा में बनाई जाती है।

Answer 1

ऐसा लगता है कि आप पीआरएनजी की बजाय हैश-फ़ंक्शन मांग रहे हैं। गुगलिंग 'फास्ट हैश फ़ंक्शन' कई आशाजनक दिखने वाले परिणाम उत्पन्न करता है।

For example:

uint32_t hash(uint32_t a) 
    a = (a^61)^(a >> 16); 
    a = a + (a << 3); 
    a = a^(a >> 4); 
    a = a * 0x27d4eb2d; 
    a = a^(a >> 15); 
    return a; 
} 

संपादित करें: हां, कुछ हैश फंक्शन निश्चित रूप से दूसरों की तुलना में अधिक उपयुक्त लग रहे हो।

अपने उद्देश्यों के लिए, यह निष्पादन को नजरअंदाज करने के लिए पर्याप्त होना चाहिए और जांचें कि इनपुट में एक-बिट परिवर्तन आउटपुट बिट्स के प्रचार के लिए प्रचारित होगा।

Answer 2

हाँ, आप पीआरएनजी की बजाय एक तेज पूर्णांक हैश एल्गोरिदम की तलाश में हैं।

यह page में कुछ एल्गोरिदम हैं, मुझे यकीन है कि अब आपको बहुत कुछ मिल जाएगा, अब आप सही खोज शब्द जानते हैं।

संपादित करें: मूल पृष्ठ हटा दिया गया है, एक लाइव संस्करण found on GitHub हो सकता है।

Answer 3

std::tr1::ranlux3, या अन्य यादृच्छिक संख्या जनरेटर जो मानक C++ लाइब्रेरी में TR1 जोड़ों का हिस्सा हैं, देखें। मैंने शुरुआत में mt19937 का सुझाव दिया, लेकिन फिर आपके नोट को देखा कि इसे बहुत तेज होना चाहिए। टीआर 1 Microsoft VC++ और जीसीसी पर उपलब्ध होना चाहिए, और बूस्ट लाइब्रेरी में भी पाया जा सकता है जो और भी कंपाइलर्स का समर्थन करता है।

उदाहरण boost documentation से अनुकूलित:

#include <random> 
#include <iostream> 
#include <iterator> 
#include <functional> 
#include <algorithm> 
#include <ctime> 
using namespace std; 
using namespace std::tr1; 
int main(){ 
    random_device trueRand; 
    ranlux3 rng(trueRand); // produces randomness out of thin air 
          // see pseudo-random number generators 
    uniform_int<> six(1,6); // distribution that maps to 1..6 
          // see random number distributions 
    variate_generator<ranlux3&, uniform_int<> > 
      die(rng, six); // glues randomness with mapping 

    // simulate rolling a die 
    generate_n(ostream_iterator<int>(cout, " "), 10, ref(die)); 
} 

उदाहरण उत्पादन:

2 4 4 2 4 5 4 3 6 2 

किसी भी TR1 यादृच्छिक संख्या जनरेटर किसी भी अन्य यादृच्छिक संख्या जनरेटर बीज कर सकते हैं। यदि आपको उच्च गुणवत्ता वाले परिणामों की आवश्यकता है, तो mt19937 (जो धीमी है, लेकिन उच्च गुणवत्ता वाली) के आउटपुट को एक minstd_rand या randlux3 में फ़ीड करने पर विचार करें, जो तेज जेनरेटर हैं।

Answer 4

यदि स्मृति वास्तव में कोई समस्या नहीं है और गति अत्यंत महत्वपूर्ण है तो आप यादृच्छिक संख्याओं की एक बड़ी श्रृंखला को पूर्वनिर्धारित कर सकते हैं और रनटाइम पर इसके माध्यम से फिर से शुरू कर सकते हैं। उदाहरण के लिए एक अलग कार्यक्रम 100,000 यादृच्छिक संख्या पैदा करते हैं और इसे सहेजें के रूप में यह की तरह खुद फ़ाइल है है

अहस्ताक्षरित int randarray [] = {1,2,3, ....}

तो में है कि फ़ाइल को शामिल अपने संकलित करें और रनटाइम पर आपके यादृच्छिक संख्या फ़ंक्शन को केवल उस सरणी से संख्याएं खींचने की आवश्यकता होती है और जब अंत में हिट होती है तो लूप को प्रारंभ में वापस लेना पड़ता है।

Answer 5

जॉर्ज मार्सग्लिया द्वारा विकसित एक छोटा यादृच्छिक संख्या जनरेटर यहां दिया गया है। वह क्षेत्र में एक विशेषज्ञ है, इसलिए आप आश्वस्त रह सकते हैं कि जनरेटर के पास सांख्यिकीय सांख्यिकीय गुण हैं।

v = 36969*(v & 65535) + (v >> 16); 
u = 18000*(u & 65535) + (u >> 16); 
return (v << 16) + u; 

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

Answer 6

मैं अपने जावा यादृच्छिक संख्या लाइब्रेरी में निम्न कोड का उपयोग करता हूं - यह मेरे लिए बहुत अच्छा काम करता है। मैं प्रक्रियात्मक सामग्री उत्पन्न करने के लिए इसका भी उपयोग करता हूं।

/** 
* State for random number generation 
*/ 
private static volatile long state=xorShift64(System.nanoTime()|0xCAFEBABE); 

/** 
* Gets a long random value 
* @return Random long value based on static state 
*/ 
public static long nextLong() { 
    long a=state; 
    state = xorShift64(a); 
    return a; 
} 

/** 
* XORShift algorithm - credit to George Marsaglia! 
* @param a initial state 
* @return new state 
*/ 
public static final long xorShift64(long a) { 
    a ^= (a << 21); 
    a ^= (a >>> 35); 
    a ^= (a << 4); 
    return a; 
}