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

Question

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

1) كمية أقل من استعلامات قاعدة البيانات.2) كمية أقل من الزحف من خلال بنية البيانات في الذاكرة ؟

أساسا فكرة القيام بما يلي

1) إنشاء رقم عشوائي من 0 إلى 9999999
2) التحقق من قاعدة البيانات لمعرفة ما إذا كان الرقم موجود
أو
2) الاستعلام عن قاعدة بيانات لجميع الأرقام
3) ترى لو عاد نتيجة مباريات كل ما جاء من db
4) إذا كان يطابق ، كرر الخطوة 1 إذا لم يتم حل المشكلة.

شكرا

Answer 1

لا خوارزمية الخاص بك غير قابل للتطوير.ماذا فعلت قبل إصدار الأرقام بشكل متسلسل (+1 في كل مرة) ثم تمريرها من خلال عملية XOR على الخليط بت مما يعطي لي على ما يبدو أرقام عشوائية.بالطبع أنها ليست عشوائية ، ولكنها تبدو للمستخدمين العيون.

---

[عدل] معلومات إضافية

هذه الخوارزمية المنطق يذهب مثل هذا كنت تستخدم يعرف تسلسل توليد أرقام فريدة ثم deterministically التلاعب بها ، حتى لا تبدو المسلسل بعد الآن.الحل العام هو استخدام بعض أشكال التشفير التي في حالتي كان XOR قلاب, لأن لها بأسرع ما يمكن الحصول عليه ، وأنه يحقق ضمان أن الأرقام لن تتصادم.

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

[شكرا آدم هيك & CesarB بالنسبة exapanding على الحل]

Answer 2

لماذا لا مجرد استخدام GUID؟ يجب أن يكون معظم لغات وسيلة المدمج في القيام بذلك. انها مضمونة لتكون فريدة من نوعها (مع حدود معقولة جدا).

Answer 3

ونريد حل أكثر من أعلى؟

وأفترض ليس المقصود العشوائية لتكون ذات جودة التشفير، ولكن فقط ما يكفي للحد من التخمين طول العمر للمستخدم، من خلال USER_ID.

وخلال التنمية، إنشاء قائمة من جميع الأرقام 10 مليون دولار في شكل سلسلة.

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

وتمرير لهم إلى أداة الذي يولد ظائف تجزئة الكمال ، مثل <أ href = ل "http://www.gnu.org/software/gperf/" يختلط = "نوفولو noreferrer"> gperf .

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

Answer 4

وحاول البيان في الخلية CAST SELECT (RAND () * 1000000 AS INT)

Answer 5

على افتراض:

• العشوائية هناك حاجة إلى التفرد ، وليس الأمن
• الخاص بك user_id هو 32 بت
• الحد الخاص بك من 9999999 كان مجرد مثال

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

Answer 6

وأعتقد أنك سوف تجد أن كنت حقا لا تريد أن تفعل هذا. كما الأرقام في زيادة قاعدة بيانات، قد تنفق الكثير من الوقت في "تأكد من لا يؤخذ هذا الرقم" حلقة.

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

Answer 7

وتجربتي كانت مجرد استخدام RNG في PHP. لقد وجدت أن استخدام حجم معين من عدد (أنا باستخدام عدد صحيح، لذلك لدي أقصى 4G). جريت بعض التجارب وجدت أن في المتوسط، في 500،000 التكرار، وحصلت على 120 مكررة واحدة. أنا لم يحصل على ثلاث نسخ بعد تشغيل حلقة حفنة من الأوقات. وكان بلدي "حل" لثم تضاف فقط ومعرفة ما اذا كان يفشل، ثم إنشاء ID جديد والذهاب مرة أخرى.

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

وهذا ليس الأمثل، حتى إذا كان أي شخص لديه اقتراحات أنا أبحث جدا :)

وتحرير: أنا اقتصر على هوية 5 أرقام ([ل-ي0-9] {5،5})، ويعد معرف (المزيد الجمع، وعدد قليل من التصادمات). وMD5 من البريد الإلكتروني الصراع من شأنه أبدا تقريبا، على سبيل المثال.

Answer 8

والمشكلة هي أنه إذا كنت توليد الأرقام العشوائية هو أمر ممكن جدا لإنتاج مكررة infinatly.

ولكن:

<?php
//Lets assume we already have a connection to the db
$sql = "SELECT randField FROM tableName";
$result = mysql_query($sql);
$array = array();
while($row = mysql_fetch_assoc($result))
 {
   $array[] = $row['randField'];
 }
while(True)
 {
   $rand = rand(0, 999999);
   if(!in_array($rand))
     {
       //This number is not in the db so use it!
       break;
     }
 }
?>

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

Answer 9

من السهل أن تصميم مولد عدد المزيف مع فترة طويلة من nonrepetition. مثلا هذا واحد، والذي يتم استخدامه لنفسه الشيء الذي تريد من أجله.

وراجع للشغل، لماذا لا مجرد إصدار بالتسلسل حاليا ل؟

Answer 10

أنا أحب Oddthinking فكرة, ولكن بدلا من اختيار أقوى وظيفة تجزئة في العالم ، يمكنك ببساطة:

• توليد MD5 من أول 10 ملايين من الأرقام (كما أعرب عن سلاسل +بعض الملح)
• البحث عن التكرارات حاليا, أيقبل الذهاب في الإنتاج (أعتقد لن يكون هناك أي)
• تخزين التكرارات في مجموعة في مكان ما
• عند التطبيق الخاص بك يبدأ تحميل مجموعة
• عندما تريد إدراج معرف ، اختر التالي رقم حساب MD5, تحقق مما إذا كان في مجموعة ، و إذا لم يكن استخدامه بمثابة معرف في قاعدة البيانات.وإلا اختيار الرقم التالي

MD5 هي سريعة و فحص إذا كانت سلسلة ينتمي إلى مجموعة تجنب كنت مختارة.

Answer 11

إذا كنت تريد حقا أن الحصول على أرقام "عشوائية" شكل 0-9 999 999، ثم الحل هو أن تفعل "العشوائية" مرة واحدة، ومن ثم تخزين النتيجة إلى القرص.

وليس من الصعب للحصول على النتيجة التي تريدها، ولكن أعتقد أنه من أكثر مثل "تقديم قائمة طويلة مع أرقام"، من "الحصول على رقم عشوائي".

$array = range(0, 9999999);
$numbers = shuffle($array);

وتحتاج أيضا مؤشر إلى الوضع الحالي في أعداد $ (تخزينها في قاعدة بيانات)؛ بدء مع 0 و زيادة في كل مرة كنت في حاجة الى الرقم الجديد. (أو يمكنك استخدام array_shift () أو array_pop ()، إذا كنت لا ترغب في استخدام المؤشرات.)

Answer 12

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

بسيطة PRNG أن يفعل هذا يسمى 'الخطية Congruential'اللوائح التي تتكرر صيغة:

X(i) = AX(i-1)|M

باستخدام حق زوج من العوامل التي يمكنك الحصول على فترة من 2^30 (حوالي 1 مليار دولار) من اللوائح مع 32 بت المجمع.ملاحظة أنك سوف تحتاج إلى 64 بت طويل متغير مؤقت لعقد المتوسطة 'الفأس' جزء من الحساب.معظم إن لم يكن كل ج المجمعين سوف تدعم هذا النوع من البيانات.يجب عليك أيضا أن تكون قادرة على القيام بذلك مع نوع بيانات رقمية على معظم SQL اللهجات.

مع قيم A و M يمكننا الحصول على مولد رقم عشوائي مع إحصائية جيدة هندسية خصائص.هناك الشهيرة ورقة حول هذا مكتوب من قبل فيشمان و مور.

ل م = 2^31 - 1 نحصل يمكن استخدام قيم أدناه للحصول على PRNG مع لطيفة فترة طويلة (2^30 IIRC).

جيد القيم:

742,938,285  
950,706,376  
1,226,874,159  
62,089,911  
1,343,714,438   

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

لأسباب مشابهة نفس الشيء ينطبق على فترة طويلة مولدات مثل ميرسين الاعصار.

Answer 13

ولقد فعلا مكتوبة من قبل <وأ href = "http://blog.notdot.net/2007/9/Damn-Cool-Algorithms-Part-2-Secure-permutations-with-block-ciphers" يختلط = "noreferrer نوفولو"> مقال عن هذا . فإنه يأخذ نفس النهج الجواب روبرت غولد، ولكن بالإضافة إلى ذلك يبين كيفية تقصير والشفرات كتلة لطول مناسب باستخدام XOR للطي، ومن ثم كيفية توليد التباديل على نطاق وليست قوة 2، في حين لا يزال الحفاظ على خاصية التفرد.

Answer 14

وهناك عدة طرق للذهاب نحو بهذه الطريقة يمكن لأحد أن يكون لبناء مجموعة مع أرقام 0000000 9999999 من خلال وثم اختيار اختيار عشوائي من هذه الأرقام في هذه المجموعة وتبديل القيم أرقام اختار وفقا لأعلى قيمة ماكس ثم خفض الحد الأقصى بنسبة 1 واختيار عضو آخر عشوائي من هذه المجموعة يصل إلى الحد الأقصى الجديد

وفي كل مرة الحد الأقصى من جانب واحد

وعلى سبيل المثال (في الأساسية): (إلى اليمين هي التعليقات التي ينبغي إزالتها في البرنامج الفعلي) Rndfunc هي دعوة إلى أي وظيفة رقم عشوائي مولد كنت تستخدم

dim array(0 to 9999999) as integer
for x% = 1 to 9999999
array(x%)=x%
next x%
maxPlus = 10000000
max =9999999
pickedrandom =int(Rndfunc*maxPlus)  picks a random indext of the array based on    
                                   how many numbers are left
maxplus = maxplus-1
swap array(pickedrandom) , array(max) swap this array value to the current end of the
                                     array 
max = max -1                   decrement the pointer of the max array value so it 
                              points to the next lowest place..

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

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

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

Answer 15

وPHP لديها بالفعل وظيفة لهذا، uniqid . فإنه يولد UUID القياسية التي هي كبيرة إذا كان لديك للوصول إلى البيانات من أي مكان آخر. لا إعادة اختراع العجلة.

Answer 16

وأنا ربما لم يمسك وجهة نظرك، ولكن ماذا عن auto_increments؟

Answer 17

إذا كنت ترغب في التأكد من أن أرقام عشوائية، لا يعيد، كنت في حاجة الى غير مكرر عشوائي رقم مولد (كما هو موضح <لأ href = "http://preshing.com/20121224/how-to- توليد واحد في تسلسل من فريد عشوائية-الأعداد الصحيحة / "يختلط =" نوفولو "> هنا ).

والفكرة الأساسية هي أن الصيغة seed * seed & p التالية سوف تنتج غير تكرار أرقام عشوائية لأي x such that 2x < p المدخلات وp - x * x % p تنتج سائر العشوائي عدد aswell غير تكرار، ولكن فقط إذا p = 3 mod 4. وذلك أساسا كل ما تحتاجه هو primnumber واحدة أقرب إلى 9999999 وقت ممكن. بهذه الطريقة يمكن تخفيض الجهد إلى حقل للقراءة واحدة، ولكن مع الهابط الذي إما جدا يتم إنشاء معرفات كبيرة أو سيتم إنشاء عدد قليل جدا من معرفات.

وهذه الخوارزمية لا بدل ترتيب كذا بشكل جيد للغاية، لذلك أنصح الجمع بين ذلك مع أي XOR أو إضافة أو بعض النهج الآخر لتغيير القيمة الدقيقة دون تدمير 1 إلى 1-العلاقة بين البذور وقيمتها ولدت.