c++ - للاندرويد - أرقام عشوائية لعدة خيوط




خوارزمية توليد ارقام عشوائية (6)

ألقِ نظرة على الورقة التالية: إنشاء ديناميكي لمولدات الأرقام العشوائية والتنفيذ المصاحب لها: الخالق الديناميكي . إنه يعالج هذه المشكلة بالتحديد.

مشكلة

أنوي كتابة تطبيق C ++ 11 لنظام لينكس الذي يقوم ببعض المحاكاة الرقمية (وليس التشفير) على أساس ما يقرب من مليون رقم عشوائي 32 بت. لتسريع الأمور ، أرغب في إجراء المحاكاة في سلاسل متوازية باستخدام جميع النوى لوحدة المعالجة المركزية لسطح المكتب. أرغب في استخدام mt19937 Twister mt19937 تقديمه عن طريق تعزيز كـ PRNG ، وأعتقد أنه لأسباب تتعلق بالأداء يجب أن يكون لدي PRNG واحد لكل مؤشر ترابط. الآن أنا غير متأكد من كيفية زرعها من أجل تجنب توليد نفس الأعداد العشوائية في خيوط متعددة.

البدائل

فيما يلي البدائل التي فكرت بها حتى الآن:

  1. بذور PRNG لكل الخيط بشكل مستقل من /dev/urandom .

    أنا قلق بعض الشيء حول الحالة عند نفاد تجمع النظام الداخلي ، حيث لا أعرف كيف يعمل PRNG الداخلي للنظام. هل يمكن أن يحدث أنني حصلت بشكل متسلسل على البذور المتتالية التي تحدد بالضبط حالات متتالية من Mersenne Twister ، وذلك بسبب حقيقة أن /dev/urandom تستخدم /dev/urandom Twister نفسها؟ ربما تتعلق بقوة اهتماماتي للنقطة التالية.

  2. بذور PRNG واحد من /dev/urandom والآخرين من هذا واحد أول.

    في الأساس نفس القلق أيضا: هل هو جيد أو سيئ لاستخدام واحدة PRNG لبذر آخر يستخدم نفس الخوارزمية؟ أو بعبارة أخرى ، هل تتطابق قراءة 625 32bit صحيحة من mt19937 مباشرة مع الحالة الداخلية لمولد mt19937 في أي نقطة خلال هذا الجيل؟

  3. ابذر الآخرين من البداية مع معلومات غير ميرسين.

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

  4. مشاركة PRNG واحد بين المواضيع.

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

  5. قبل إنشاء جميع الأرقام العشوائية.

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

الأسئلة

أي من الطرق التالية تقترحها ، ولماذا؟ أو هل لديك اقتراح مختلف؟

هل تعرف أي من شواغلي لها ما يبررها والتي هي ببساطة بسبب افتقارها إلى نظرة ثاقبة عن كيفية عمل الأشياء في الواقع؟


أود أن أقول # 3 هو الفائز. زرع كل موضوع مع شيء مثل processID أو threadID ؛ في حين أنه من الممكن تقنيا يمكن أن يكون لديك تداخل ، فمن المستبعد للغاية. حتى الأرقام المتتالية لا ينبغي أن تكون ذات صلة من حيث البذور بمجرد الخروج من الأرقام الفردية (لا أعرف خوارزمية Twister ، ولكن أسوأ PRNG التي رأيتها كانت جيدة فوق 7). واحد مليون PRNG ليس هذا كثير مقارنة بنطاق معظم معادلات PRNG.

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


خيوط البذور 1 مع 1 ، والبذور موضوع 2 مع 2 ، الخ

إذا كنت بحاجة إلى مونت كارلو فهذا سيعطيك نتائج قابلة لإعادة الإنتاج ، فمن السهل تتبعها وتنفيذها.


سأستخدم حادثة واحدة لزرع الآخرين. أنا متأكد من أنك تستطيع القيام بذلك بأمان بسهولة.

  • حتى التغييرات الصغيرة في مساحة الولاية تسبب تغيرات كبيرة إلى حد كبير في اتجاه مجرى النهر - إذا كنت تستطيع التأكد من عدم وجود نفس مساحة البداية نفسها (وليس هناك بادئة مماثلة) ، لا داعي للقلق بشأن إنتاج أرقام متطابقة. على سبيل المثال ، استخدام القيمتين 1 و 2 و 3 للبذور الثلاث من شأنه أن يعمل بشكل جيد - حتى أنك لا تحتاج إلى زرع المساحة بأكملها. ميزة أخرى: من خلال استخدام بذور يمكن التنبؤ بها بوضوح ، يمكنك بسهولة تشويه الفكرة القائلة بأنك تقوم باختيار أي شىء (بافتراض أنك تحاول عرض شيء ما).
  • من البسيط أن نزرع بطريقة تعني أن "الأطفال" الناتجون لا يرتبطون ارتباطًا كبيرًا. فقط قم بالتكرار بطريقة متقنة. على سبيل المثال ، إذا كنت ترغب في الحصول على قيم int N 623 int ، فلا تقم بزراعة 623 قيمًا بالتسلسل ، ولكن اختر أول N ثم قم بتوزيع N ، ثم N التالي. حتى إذا كان هناك بعض الارتباط بين البذرة والأطفال ، فإن العلاقة بين يجب أن يكون الأطفال غير متوفرين - وهذا كل ما يهمك.
  • أفضّل خوارزمية تسمح بالتنفيذ الحتمي كلما أمكن ذلك ، لذا فإن الاعتماد على urandom ليس جذابًا. هذا يجعل التصحيح أسهل.
  • أخيرا ، وبشكل واضح - اختبار. هذه PRNG قوية إلى حد ما ، ولكن بكل المقاييس ، قم بتقييم النتائج وقم ببعض اختبارات الارتباط المستوحاة من ما تقوم بمحاكاته. يجب أن تكون معظم المشاكل واضحة - إما أنك قمت بالبذور بشكل سيئ وأن هناك تكرارًا واضحًا للواجبات ، فأنت قمت ببذر جيد ، ثم تم تحديد الجودة من خلال قيود PRNG.
  • بالنسبة لعمليات الإعدام النهائية ، بعد الانتهاء من الاختبار ، يمكنك إنشاء أول قيمة من قيم الحالة 623 باستخدام urome لراحة البال و / أو معرف سلسلة المحادثات.

وأود أن أذهب مع رقم 1 ، والبذور كل prng من urandom. وهذا يضمن أن الدول مستقلة تمامًا (بقدر ما تكون بيانات البذور مستقلة). عادة سيكون هناك الكثير من الإنتروبيا المتاحة إلا إذا كان لديك العديد من المواضيع. أيضا ، اعتمادا على الخوارزمية المستخدمة / dev / urandom ، من شبه المؤكد أنك لا داعي للقلق بشأنها.

لذلك قد تستخدم شيئًا كالتالي لإنشاء كل prng:

#include <random>

std::mt19937 get_prng() {
    std::random_device r;
    std::seed_seq seed{r(), r(), r(), r(), r(), r(), r(), r()};
    return std::mt19937(seed);
}

يجب التحقق من أن تنفيذ std::random_device يسحب من /dev/urandom ضمن التهيئة الخاصة بك. وإذا كان يستخدم / dev / urandom بشكل افتراضي ، فيمكنك عادة قول std::random_device("/dev/random") إذا كنت تريد استخدام / dev / random بدلاً من ذلك.


يمكنك استخدام PRNG مع بنية جبرية مختلفة لبذر PrNGs مختلفة. على سبيل المثال بعض تسلسل MD5 التجزئة.

ومع ذلك ، سأختار رقم 5. إذا كان يعمل فهو بخير. إذا لم تتمكن من ذلك ، فلا يزال بإمكانك تحسينها.

النقطة هي إنشاء PRNG جيدة أصعب بكثير مما قد يتوقعه المرء. من الأفضل أن تكون PRNG جيدة للتطبيقات الملولبة موضوعًا ما زال خاضعًا للبحث.

إذا كان عدد وحدات المعالجة المركزية (CPUs) منخفضًا بما فيه الكفاية ، فيمكن أن تفلت بسرعة. على سبيل المثال ، إذا كان لديك 4 نوى ، فعليك تهيئة كل القيم نفسها ، لكن احرص على تقدم 1 PRNG الأساسية بمقدار 1 ، # 2 في 3 ، ثم قم بالتقدم 4 خطوات دائمًا عندما تحتاج إلى رقم جديد.





mersenne-twister