مولد أرقام عشوائية زائفة سريع للمحتوى الإجرائي

Question

أنا أبحث عن مولد أرقام عشوائية زائفة يكون متخصصًا في العمل بسرعة عندما يتم إعطاؤه بذرة قبل إنشاء كل رقم.تفترض معظم المولدات التي رأيتها حتى الآن أنك تقوم بتعيين البذرة مرة واحدة ثم تقوم بإنشاء سلسلة طويلة من الأرقام.الشيء الوحيد الذي يبدو مشابهًا إلى حد ما لما رأيته حتى الآن هو Perlin Noise، ولكنه يولد بيانات "سلسة" للغاية - بالنسبة للمدخلات المماثلة فإنها تميل إلى إنتاج نتائج مماثلة.

يجب أن يبدو إعلان المولد كما يلي:

int RandomNumber1(int seed);

أو:

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

أعتقد أن الحصول على RandomNumber1 الجيد يجب أن يكون كافيًا، حيث من الممكن تنفيذ RandomNumber3 عن طريق تجزئة مدخلاته وتمرير النتيجة إلى RandomNumber1، لكنني كتبت النموذج الأولي الثاني في حالة إمكانية استخدام بعض التطبيقات للمدخلات المستقلة.

الاستخدام المقصود لهذا المولد هو استخدامه لمولد المحتوى الإجرائي، مثل إنشاء غابة عن طريق وضع الأشجار في شبكة وتحديد أنواع الأشجار العشوائية والإزاحات المكانية العشوائية لكل موقع.

يجب أن يكون المولد فعالاً للغاية (أقل من 500 دورة لوحدة المعالجة المركزية)، لأنه يتم إنشاء المحتوى الإجرائي بكميات هائلة في الوقت الفعلي أثناء العرض.

Answer 1

يبدو أنك تطلب وظيفة التجزئة بدلاً من PRNG.يؤدي البحث عن "وظيفة التجزئة السريعة" على Google إلى العديد من النتائج الواعدة.

على سبيل المثال:

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

نعم، كنت تبحث عن خوارزمية البعثرة صحيح سريع بدلا من PRNG.

لديه بعض الخوارزميات، وأنا متأكد من أنك 'ليرة لبنانية العثور على الكثير أكثر الآن أنت تعرف مصطلحات البحث الصحيحة.

تعديل : في وقد الصفحة الأصلية إزالتها، يمكن أن يكون نسخة حية وجدت على جيثب .

Answer 3

وهنا رقم عشوائي صغير مولد وضعتها جيورج مارساغليا. انه خبير في هذا المجال، لذلك يمكنك أن تكون على ثقة المولد له خصائص إحصائية جيدة.

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

وهنا u و v هم [إينتس] غير موقعة. تهيئة لهم أي القيم غير الصفرية. في كل مرة كنت توليد رقم عشوائي، مخزن u و v في مكان ما. هل يمكن الانتهاء من هذه في وظيفة لتتناسب مع توقيعك فوق (باستثناء [إينتس] هي غير موقعة.)

Answer 4

ونرى std::tr1::ranlux3، أو غيرها من المولدات رقم عشوائي التي هي جزء من الإضافات TR1 إلى المكتبة القياسية C ++. اقترحت mt19937 initialially، ولكن بعد ذلك رأى ملاحظتك أنه يجب أن يكون سريع جدا. TR1 هو أن تكون متاحة على مايكروسوفت VC ++ ودول مجلس التعاون الخليجي، ويمكن أيضا يمكن العثور عليها في المكتبات دفعة التي تدعم المزيد من المجمعين.

والمثال مقتبس من الوثائق دفعة :

#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 5

إذا الذاكرة ليست في الحقيقة قضية والسرعة هي ذات أهمية قصوى بعد ذلك يمكنك prebuild مجموعة كبيرة من الأرقام العشوائية ومجرد تكرار من خلال ذلك في وقت التشغيل. على سبيل المثال لديها برنامج منفصل توليد 100،000 أرقام عشوائية وحفظه كما انها الملف الخاص مثل

وغير موقعة كثافة العمليات randarray [] = {1،2،3، ....}

وثم تضمين هذا الملف في الترجمة وفي وقت التشغيل العشوائي وظيفة رقم يحتاج فقط إلى سحب الأرقام من أن مجموعة وحلقة العودة الى بداية عندما يضرب النهاية.

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;
}