باستخدام Boost :: Random للاختيار من std :: قائمة حيث تتم إزالة العناصر

Question

انظر الى هذا السؤال ذي الصلة على استخدام أكثر عامة للمكتبة العشوائية التعزيز.

تتضمن أسئلتي اختيار عنصر عشوائي من std::list, ، القيام ببعض العمليات ، والتي يمكن أن تشمل بشكل فعلي إزالة العنصر من القائمة ، ثم اختيار عنصر عشوائي آخر ، حتى يتم استيفاء بعض الحالة.

رمز التعزيز وللحلقة تبدو مثل هذا:

// create and insert elements into list
std::list<MyClass> myList;
//[...]

// select uniformly from list indices
boost::uniform_int<> indices( 0, myList.size()-1 );    
boost::variate_generator< boost::mt19937, boost::uniform_int<> > 
  selectIndex(boost::mt19937(), indices);

for( int i = 0; i <= maxOperations; ++i ) {
    int index = selectIndex();
    MyClass & mc = myList.begin() + index;

    // do operations with mc, potentially removing it from myList
    //[...]
}

مشكلتي هي بمجرد أن تؤدي العمليات التي يتم تنفيذها على عنصر إلى إزالة عنصر ما ، فإن Variate_Generator لديه القدرة على تحديد فهرس غير صالح في القائمة. لا أعتقد أنه من المنطقي إعادة إنشاء variate_generator تمامًا في كل مرة ، خاصةً إذا قمت ببذخه مع الوقت (0).

Answer 1

أفترض ذلك MyClass & mc = myList.begin() + index; هو مجرد رمز زائف ، حيث يعيد Begin ايتراتور ولا أعتقد أن قائمة المتكررين (غير عشوائيين) دعم operator+.

بقدر ما أستطيع أن أقول ، مع المولد المتغير الخيارات الأساسية الثلاثة في هذه الحالة هي:

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

بالتناوب ، يمكنك وضع خوارزمية مختلفة لتوليد الفهرس قادرة على التكيف مع حجم تغيير الحاوية.

Answer 2

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

Answer 3

أعتقد أن لديك المزيد للقلق بشأن الأداء. خاصة هذا:

std::list<MyClass> myList;
myList.begin() + index;

ليست طريقة سريعة للاستمتاع index-عنصر.

أود تحويله إلى شيء كهذا (والذي يجب أن يعمل على بعد عشوائي للقائمة):

X_i ~ U(0, 1) for all i
left <- max_ops
N <- list size
for each element
  if X_i < left/N
    process element
    left--
  N--

شريطة ألا تحتاج إلى التقليب العشوائي للعناصر.