الغالبية العظمى من مشاركاتي على توليد الأرقام العشوائية تتعامل بشكل أساسي مع خصائص مخططات التوليد المختلفة. قد يكون هذا غير متوقع ، لكن أداء خوارزمية التوزيع العشوائي قد لا يعتمد على مخطط التوليد المختار ، ولكن يعتمد على عوامل أخرى. في هذا
المنشور (الذي استلهمته
مقال ممتاز
من إعداد دانيال لومير ) ،
سنبحث الأسباب الرئيسية للانخفاض في أداء توليد الأرقام العشوائية ، والتي غالباً ما تفوق أداء محرك PRN.
تخيل هذا الموقف:
كواجب منزلي ، يقوم كل من Juan و Sasha بتنفيذ نفس الخوارزمية العشوائية في C ++ ، والتي سيتم تشغيلها على الكمبيوتر الجامعي نفسه ومع مجموعة بيانات واحدة. رمزهم متطابق تقريبًا ويختلف فقط في توليد أرقام عشوائية. خوان في عجلة من أمره لدروسه الموسيقية ، لذلك اختار ببساطة زوبعة مرسين. ساشا ، من ناحية أخرى ، أمضى بضع ساعات إضافية في البحث. أجرى ساشا مقاييس للعديد من أسرع PRNGs ، والتي تعلمها مؤخرًا من الشبكات الاجتماعية ، واختار الأسرع. في الاجتماع ، كان ساشا غير متلهف للتفاخر ، وسأل خوان: "ما هو نظام PRNG الذي استخدمته؟"
"شخصياً ، أخذت دوامة مرسين - فهي مبنية على اللغة ويبدو أنها تعمل بشكل جيد."
"ها!" أجاب ساشا. "لقد استخدمت
jsf32 . إنه أسرع بكثير من زوبعة مرسين القديمة والبطيئة! يعمل برنامجي في 3 دقائق و 15 ثانية! "
يقول خوان ويستهزئ بقوله: "حسنًا ، ليس سيئًا ، لكن يمكن لي أن أفعل ذلك في أقل من دقيقة". "حسنًا ، يجب علي الذهاب إلى الحفلة الموسيقية. هل ستأتي معي؟ "
"لا" ، يجيب ساشا. "أنا ... أه ... بحاجة إلى إلقاء نظرة على الكود مرة أخرى."
هذا الموقف الخيالي المحرج
ليس خياليًا بشكل خاص. يعتمد على نتائج حقيقية. إذا لم تكن الخوارزمية العشوائية تعمل بالسرعة التي نرغب فيها ، ويبدو أن عنق الزجاجة هو توليد الأرقام العشوائية ، فمن الغريب أن المشكلة قد لا تكون في مولد الأرقام العشوائية!
مقدمة: أرقام عشوائية في الممارسة
تقوم معظم مولدات الأرقام العشوائية عالية الجودة الحديثة بإنشاء كلمات آلية مملوءة بتات عشوائية ، أي أنها عادةً ما تولد أرقامًا في الفاصل الزمني [0..2
32 ) أو [0..2
64 ). ولكن في العديد من حالات الاستخدام ، يحتاج المستخدمون إلى أرقام في فاصل زمني معين - على سبيل المثال ، لفافة يموت أو اختيار بطاقة لعب عشوائية ، هناك حاجة إلى أرقام في فواصل زمنية صغيرة ثابتة. ومع ذلك ، فإن العديد من الخوارزميات ، من
المزج وأخذ عينات الخزان إلى
أشجار البحث الثنائية العشوائية ، تتطلب أرقامًا مأخوذة من فواصل زمنية أخرى.
طرق
سوف ننظر في العديد من الطرق المختلفة. لتبسيط المناقشة ، بدلاً من إنشاء أرقام في الفاصل الزمني [
i ..
j ) أو [
i ..
j ] ، سنقوم بإنشاء أرقام في الفاصل الزمني [0 ..
k ). امتلاك مثل هذا المخطط ، يمكننا ، على سبيل المثال ، إنشاء أرقام في الفاصل الزمني [
i ..
j ) عن طريق تعيين
k =
j -
i ، وإنشاء رقم في الفاصل الزمني [0 ..
k ) ، ثم إضافة
i إليه.
المدمج في أدوات C ++
تحتوي العديد من اللغات على أدوات مضمّنة للحصول على رقم عشوائي في فاصل زمني محدد. على سبيل المثال ، لإزالة بطاقة من مجموعة أوراق بها 52 ورقة في لغات البرمجة النصية مثل Perl و Python ، يمكننا كتابة
int(rand(52)) و
random.randint(0,52) . [ملاحظة. مستخدم
CryptoPirate :
يبدو لي خطأ هنا ، في بيثون راندنت (أ ، ب) يولد أرقام من أ إلى ب بما في ذلك ب. ونظرًا لوجود 52 بطاقة في المجموعة والأول هو "0" ، فيجب أن يكون هناك random.randint (0،51) .] في C ++ ، يمكننا استخدام
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 لإنشاء أرقام في أي فاصل زمني ، على سبيل المثال [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 ، فسنحصل على 82 595 525 طريقة لاختيار أول 48 بطاقة من مجموعة الورق و 82 595 524 فقط من طرق اختيار البطاقات الأربع الأخيرة. بمعنى آخر ، هناك انحراف قدره 0.00000121٪ مقابل هذه البطاقات الأربع الأخيرة (ربما هؤلاء ملوك!). عندما كنت طالباً وكتبت واجبات منزلية حول إلقاء الزهر أو رسم البطاقات ، لم يزعج أحد عادة بمثل هذه التشوهات الصغيرة ، لكن مع زيادة الفاصل الزمني ، يزداد التشوه خطيًا. بالنسبة لـ PRNG ذي 32 بت ، فإن الفاصل الزمني المحدود الذي يقل عن 2
24 يكون به انحراف أقل من 0.5٪ ، ولكن فوق 2
31 انحراف بنسبة 50٪ - ستعود بعض الأرقام إلى ضعفي عدد مرات ظهور الأرقام الأخرى.
في هذه المقالة ، سننظر بشكل أساسي في التقنيات التي تستخدم الاستراتيجيات للتخلص من خطأ منتظم ، ولكن ربما يجدر بنا القول أنه بالنسبة إلى PRNG 64 بت ، من المرجح أن تكون قيمة الانحراف في التطبيقات العادية ضئيلة.
مشكلة أخرى قد تكون أن بعض المولدات الكهربائية لديها بتات منخفضة ضعيفة. على سبيل المثال ، تمتلك عائلة GPRS Xoroshiro + و Xoshiro + وحدات بت منخفضة لا تجتاز الاختبارات الإحصائية. عندما ننفذ
% 52 (لأن 52 متساوية) ، فنحن نمر بت الرتبة المنخفضة مباشرة إلى المخرجات.
ضرب أرقام الفاصلة العائمة (منحرفة)
أسلوب شائع آخر هو استخدام PRNG الذي يولد أرقام الفاصلة العائمة في الفاصل الزمني [0..1) مع التحويل اللاحق لهذه الأرقام إلى الفاصل الزمني المطلوب. يستخدم هذا الأسلوب في Perl ،
يوصى باستخدام
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) ، لكن عندما حددت هذا النهج ، اتضح أنه أبطأ كثيرًا.)
هذا النهج منحرف مثل بقية التقسيم الكلاسيكية ، لكن الانحراف يظهر بشكل مختلف. على سبيل المثال ، إذا كنا نختار الأرقام في الفاصل الزمني [0..52) ، فإن الأرقام 0 و 13 و 26 و 39 ستحدث مرة واحدة أقل من غيرها.
هذا الإصدار ، عند تعميمه إلى 64 بت ، هو أكثر غير سارة ، لأنه يتطلب نوع نقطة عائمة يكون سرعته 64 بت على الأقل. على أجهزة x86 التي تعمل بنظام Linux و macOS ، يمكننا استخدام
long double للاستفادة من أرقام الفاصلة العائمة بدقة x86 التي تحتوي على سرعتي 64 بت ، لكن
long double لا
long double نقله عالميًا إلى جميع الأنظمة - في بعض الأنظمة ،
long double تعادل
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 بت ، وفي x 86 معالجات ، سيقوم المترجم الجيد بترجمة هذا الرمز إلى تعليمة متعددة 32 بت (والتي تعطينا قيمتي إخراج 32 بت ، إحداهما هي قيمة الإرجاع). من المتوقع أن يكون هذا الإصدار سريعًا ، لكنه منحرف تمامًا مثل طريقة ضرب أرقام الفاصلة العائمة.
تقسيم الانقسام (بدون انحراف)
يمكننا تعديل مخطط ضرب النقطة العائمة في مخطط قائم على التقسيم. بدلاً من ضرب
x * range / 2**32 نحسب
x / (2**32 / range) . نظرًا لأننا نعمل باستخدام عدد صحيح من الحسابات ، سيتم إجراء التقريب في هذا الإصدار بشكل مختلف ، وأحيانًا يتم إنشاء قيم خارج الفاصل الزمني المطلوب. إذا تجاهلنا هذه القيم (على سبيل المثال ، تخلص منها وولدنا قيمًا جديدة) ، فنتيجة لذلك نحصل على تقنية بدون تشوهات.
على سبيل المثال ، في حالة سحب البطاقة باستخدام PRNG 32 بت ، يمكننا إنشاء رقم 32 بت وتقسيمه على 2 32/52 = 82 595 524 لتحديد البطاقة. تعمل هذه التقنية إذا كانت القيمة العشوائية من PRNG 32 بت أقل من 52 × 82595524 = 2 32/32 - 48. إذا كانت القيمة العشوائية من PRNR هي واحدة من آخر 48 قيمًا للجزء العلوي من الفاصل الزمني للمولد ، فأنت بحاجة إلى التخلص منها والبحث عن قيمة أخرى.
يستخدم الرمز الخاص بنا لهذا الإصدار خدعة مع تقسيم 2
32 حسب
range دون استخدام الرياضيات 64 بت. من أجل الحساب المباشر لـ
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) {
بالطبع ، يتطلب هذا النهج عمليتين بطيئتين على أساس القسمة ، والتي عادة ما تكون أبطأ من العمليات الحسابية الأخرى ، لذلك يجب ألا تتوقع أن تكون سريعة.
ما تبقى من التقسيم (مزدوج) دون تشوهات - تقنية OpenBSD
يمكننا أيضًا اتباع نهج الإسقاط لإزالة الانحراف في الطريقة الباقية للتقسيم الكلاسيكي. في المثال مع أوراق اللعب ، نحتاج مرة أخرى إلى إسقاط 48 قيمة. في هذا الإصدار ، بدلاً من تجاهل
آخر 48 قيمة ، فإننا (معادلًا) نتجاهل
أول 48 قيمة.
هنا هو تنفيذ هذا النهج في C ++:
uint32_t bounded_rand(rng_t& rng, uint32_t range) {
تزيل هذه التقنية الانحراف ، ولكنها تتطلب عمليتين منفصلتين لتقسيم الوقت مع باقي قيمة كل ناتج (وقد تحتاج إلى مولد داخلي لإنشاء عدة أرقام). لذلك ، ينبغي توقع أن تكون الطريقة أبطأ مرتين تقريبًا من طريقة الانحراف الكلاسيكية.
arc4random_uniform OpenBSD (والذي يستخدم أيضًا على OS X و iOS) هذه الاستراتيجية.
بقايا الانقسام (فردي) بدون انحراف - منهجية جافا
تستخدم Java طريقة مختلفة لإنشاء رقم في فاصل زمني يستخدم عملية تقسيم الباقي واحدة فقط ، باستثناء حالات نادرة إلى حد ما من تجاهل النتيجة. كود:
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; }
لفهم لماذا يعمل هذا الخيار ، تحتاج إلى التفكير قليلاً. بخلاف الإصدار السابق استنادًا إلى المخلفات المتبقية ، والذي يلغي التحيز عن طريق إزالة جزء من أقل القيم من محرك التوليد الداخلي ، يقوم هذا الإصدار بتصفية القيم من الجزء العلوي من الفاصل الزمني للمحرك.
عدد صحيح الانحراف - طريقة Lemira
بنفس الطريقة التي أزلنا بها التحيز من بقية طريقة القسمة ، يمكننا القضاء على التحيز من تقنية الضرب الصحيح. اخترع هذا Lemyr هذه التقنية.
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; }
إسقاط قناع نقطي (بدون انحراف) - تقنية Apple
في نهجنا الأخير ، يتم القضاء على التقسيم والعمليات المتبقية بالكامل. بدلاً من ذلك ، يستخدم عملية إخفاء بسيطة للحصول على رقم عشوائي في الفاصل الزمني [0..2
ك ) ، حيث
k هي أصغر قيمة ، بحيث يكون 2
ك أكبر من الفاصل. إذا كانت القيمة كبيرة جدًا بالنسبة للفاصل الزمني لدينا ، فإننا نتجاهلها ونحاول الحصول على أخرى. الكود هو مبين أدناه:
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 عندما قامت (في إصدار macOS Sierra) بإجراء
تنقيحها الخاص arc4random_uniform .
مقارنة التقنيات الأساسية
الآن لدينا العديد من الأساليب التي يمكن تقييمها. لسوء الحظ ، عندما نشعر بالقلق إزاء تكاليف عملية تقسيم واحدة ، يصبح التقييم أمرًا غير تافه. لا يوجد معيار يمكن أن يأخذ في الاعتبار جميع العوامل التي تؤثر على مجال التطبيق ، وليس هناك ما يضمن أن الخيار الأفضل للتطبيق الخاص بك سيكون بالتأكيد الأفضل بالنسبة لي.
نحن نستخدم ثلاثة معايير واختبار التقنيات مع العديد من PRNGs المختلفة.
المعيار الكبير خلط ورق اللعب
ربما كان المؤشر الأكثر وضوحا هو الاختلاط. في هذا المعيار ، نحاكي أداء الخلط على نطاق واسع. لفرز صفيف من الحجم
N ، يجب علينا إنشاء أرقام في الفواصل الزمنية [0 ..
N ) ، [0 .. (
N -1)) ، ... ، [0..1). في هذا المعيار ، سوف نفترض أن
N هو أقصى عدد ممكن (لأن
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; }
لاحظ أننا "نستخدم" كل رقم عن طريق إضافته إلى
sum (بحيث لن يتم التخلص منه عن طريق التحسين) ، لكننا لا نقوم بأي مزج للتركيز على توليد الأرقام.
لاختبار الجيل 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 بت (باستخدام
std::mt19937 من
std::mt19937 libstdc++ ) ورمز 64 بت مشابه (باستخدام
std:mt19937_64 من
std:mt19937_64 libstdc++ ). النتائج هي المتوسط الهندسي لـ 15 أشواط مع قيم أولية مختلفة ، والتي يتم بعد ذلك تطبيعها بحيث يكون لطريقة التقسيم الكلاسيكية فترة تشغيل واحدة.
قد يبدو أن لدينا إجابات واضحة حول الأداء - يبدو أنه يمكنك إنشاء تقنيات لتحقيق الكمال ، واسأل نفسك عن مطوري
libstdc++ كانوا يفكرون عندما كتبوا مثل هذا التطبيق الرهيب للأرقام 32 بت. ولكن ، كما هو الحال غالبًا مع القياس ، فإن الموقف أكثر تعقيدًا مما يبدو من هذه النتائج. أولاً ، هناك احتمال أن تكون النتائج خاصة بدورة مرسين ، لذلك سنقوم بتوسيع PRNGs المختبرة. ثانيا ، قد تكون هناك مشكلة خفية مع المؤشر نفسه. دعنا أولاً نتعامل مع السؤال الأول.
نتائج PRNGs مختلفة
arc4_rand32 32 بت باستخدام
arc4_rand32 و
chacha8r و
gjrand32 و
jsf32 و
mt19937 و
pcg32 و
pcg32_fast و
sfc32 و
splitmix32 و
xoroshiro64+ و
xorshift*64/32 xoshiro128+ و
xoshiro128+ و
xoshiro128** و
jsf64 و
xoshiro256* و
xoshiro256* و
xoshiro256* و
xoshiro256* و
xoshiro256* و
xoshiro256* و
xoshiro256* و
xoshiro256* xoshiro256+ و
xoshiro256* و
xoshiro256* و
xoshiro256* . هذه المجموعات سوف تعطينا بعض PRNs بطيئة والكثير من تلك سريع جدا.
وهنا النتائج:
يمكننا أن نرى الاختلافات الرئيسية من النتائج مع دوامة مرسين. أسرع PRNGs بتحويل التوازن نحو الكود المحيط ، وبالتالي يصبح الفرق بين الطرق المختلفة أكثر وضوحًا ، خاصة في حالة PRNRs 64 بت. مع مجموعة أوسع من
libstc++ توقف تطبيق
libstc++ عن أن يبدو فظيعًا جدًا.
النتائج
في هذا المعيار بهامش كبير ، فإن النهج القائم على الضرب مع التحيز يفوز في السرعة. هناك العديد من المواقف التي تكون فيها الحدود صغيرة بالنسبة لحجم PRNG ، والأداء مهم للغاية. في مثل هذه الحالات ، من غير المرجح أن يكون للانحياز الطفيف تأثير ملحوظ ، ولكن سيكون لسرعة PRNG. مثال على ذلك هو Quicksort بنقطة مرجعية عشوائية. من الأساليب المنحرفة ، تبدو تقنية bitmask واعدة.
ولكن قبل التوصل إلى استنتاجات جادة ، نحتاج إلى الإشارة إلى المشكلة الضخمة لهذا المعيار - حيث يتم قضاء معظم الوقت على حدود عالية جدًا ، والتي على الأرجح تعطي أهمية مفرطة لفترات كبيرة. لذلك ، نحن بحاجة للذهاب إلى المؤشر الثاني.
المعيار صغير خلط ورق اللعب
يشبه هذا المعيار المعيار السابق ، ولكنه يؤدي "اختلاط الصفيف" أقل من ذلك بكثير. كود:
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; } }
نتائج دوامة مرسين
نتائج PRNGs مختلفة
النتائج
يتجنب هذا المعيار التركيز الزائد على الحدود الكبيرة ويعكس بشكل أكثر دقة حالات الاستخدام في العالم الحقيقي ، لكنه يتجاهل الآن الحدود الكبيرة تمامًا.المعيار لجميع الفترات
يهدف هذا المؤشر إلى تجنب عيوب الاثنين السابقتين ؛ يقوم بإجراء اختبار في كل حجم من قوة اثنين بحيث كل حجم موجود ، ولكن تأثيره لا يبالغ. 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; } }
نتائج دوامة مرسين
نتائج PRNGs مختلفة
النتائج
. , , , , .
, , .
, - , . , .
, :
uint32_t bounded_rand(rng_t& rng, uint32_t range) {
range ,
. , , .
:
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; }
« Mod » (. ), « ». , ( ).
Large-Shuffle
64- ( mod ), 32- . , .
Small-Shuffle
, small-shuffle , . . (OpenBSD) (Java).
.
, : .
عادةً ما a % bيتطلب الحساب قسمة ، ولكن في المواقف التي تكون فيها a < bالنتيجة بسيطة aولا تكون القسمة مطلوبة. وعندما a/2 < bتكون النتيجة بسيطة a - b. لذلك ، بدلا من الحوسبة a %= b;
يمكننا الوفاء if (a >= b) { a -= b; if (a >= b) a %= b; }
تعد تكلفة القسمة كبيرة جدًا ، حيث إن زيادة تكلفة هذا الرمز الأكثر تعقيدًا يمكن أن يبرر نفسه عن طريق توفير الوقت بسبب نقص التقسيم.نتائج اختبار خلط ورق اللعب الكبيرة
تؤدي إضافة هذا التحسين إلى تحسن كبير في نتائج اختبار القياس الكبير. هذا هو مرة أخرى أكثر وضوحا في رمز 64 بت ، حيث تكون عملية أخذ الباقي أكثر تكلفة. تُظهر طريقة الباقي المزدوج (أسلوب OpenBSD) الإصدارات ذات التحسينات لعملية الباقي واحدة فقط ولكليهما.- , .
Small-Shuffle
small-shuffle, , . , .
.
:
, . .
32-
32- , , 32- :
, ,
pcg32_fast — Xoroshiro ( ). , - — . , 5%, , «».
64-
64- , , 32- . , 32- , 64- , 32- .
,
mcg128_fast , 5%, .
pcg64 pcg64_fast mcg128_fast , 128- (, LCG) 128- (, MCG). , ,
pcg64 20% 64- .
, , 64- , 64- , 32-.
النتائج
, (, 32- ) 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; }
, .
:
GitHub . 23
bounded_rand 26 (13 32- 13 64-), (GCC 8 LLVM 6), 26 * 23 * 2 = 1196 , 15 seed, 1196 * 15 = 17 940 , . 48- Xeon E7-4830v3 2,1 . .
. ,
jsf32.STD-libc++ , —
mt19937.BIASED_FP_MULT_SCALE. في المعيار 3 ، يأخذ الأخير 69.6٪ وقتًا أقل. وهذا هو ، الوقت من هذا الموقف الخيالي يستند إلى بيانات من الواقع.