ضبط عناصر فرصة التي سيتم اختيارها من قائمة
https://stackoverflow.com/questions/1589321
-
22-09-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russianسؤال
لدي قائمة من البنود.عند إنشاء قائمة كل بند المساواة في فرصة لتكون مختارة.ولكن باعتبارها العنصر المحدد لها فرصة يذهب إلى أسفل في حين أن الآخرين فرصة ترتفع.إذا كان عنصر جديد يضاف أثناء العملية ، ينبغي أن يكون أعلى فرصة لتكون مختارة مع فرص السقوط كما هو المختار.أنا أبحث عن خوارزمية جيدة التي يمكن أن إنجاز هذا هو C#.
Generalizaed فكرة:لدي 5 مواد ، مع مرور الوقت كل 5 بنود سيتم اختيار 20% من الوقت الوقت.أنا أحاول الحفاظ على تشكيلة قريبة إلى أن 20% ممكن ، خفض outlyers.إذا وجد أنه سيتم اختيار أكثر/أقل لإعادته في خط.
المحلول
هنا سوف مهندس مولد رقم عشوائي له توزيع الحسنات القيم المنخفضة.يمكنك استخدامه تفضل الأصناف في بداية القائمة.لتقليل احتمالات شيء اختياره نقل هذا البند إلى أسفل القائمة.لديك عدد قليل من الخيارات كيف تريد نقل العنصر إلى أسفل القائمة.يتيح مراجعة متغير عشوائي التحول الأولى.
من خلال تطبيق الدالة التالية موحد متغير عشوائي بين 0 و 1:
index = Int(l*(1-r^(0.5)) # l=length, r=uniform random var between 0 and 1
يمكنك الحصول على رائع التوزيع أن يقلل بشكل كبير من احتمالات أكبر مؤشر
p(0)=0.09751
p(1)=0.09246
p(2)=0.08769
p(3)=0.08211
p(4)=0.07636
p(5)=0.07325
p(6)=0.06772
p(7)=0.06309
p(8)=0.05813
p(9)=0.05274
p(10)=0.04808
p(11)=0.04205
p(12)=0.03691
p(13)=0.03268
p(14)=0.02708
p(15)=0.02292
p(16)=0.01727
p(17)=0.01211
p(18)=0.00736
p(19)=0.00249
هنا هو توزيع قائمة من حجم 2
0.75139
0.24862
حجم 3
0.55699
0.33306
0.10996
حجم 4
0.43916
0.31018
0.18836
0.06231
الآن دعونا نناقش خيارين لنقل العناصر إلى أسفل القائمة.أنا اختبرت اثنين:
ToEnd - نقل مؤخرا العنصر المحدد إلى نهاية القائمة
نوع - الاحتفاظ بها مجموعة من عدد مرات كل بند تم اختيار وفرز قائمة من الأقل إلى الأكثر المختارة.
أنا خلقت محاكاة لاختيار من قائمة ودراسة الانحراف المعياري عد أن كل عنصر تم تحديده.وانخفاض الانحراف المعياري أفضل.على سبيل المثال, 1 المحاكاة للحصول على قائمة من 10 عناصر من أين 50 تشكيلة حيث جعل خلق انتشار:
{"a"=>5, "b"=>5, "c"=>6, "d"=>5, "e"=>4, "f"=>4, "g"=>5, "h"=>5, "i"=>6, "j"=>5}
معيار Devation لهذه المحاكاة كان
0.63
مع القدرة على تشغيل المحاكاة ، ثم احتساب بعض الفوقية الإحصاءات عن طريق تشغيل المحاكاة 500 مرة و توفير المتوسط الانحراف المعياري لكل طريقة:ToEnd و نوعا.ومن الواضح أن الانحراف المعياري أن يكون ارتفاع منخفض # من يختار ، ولكن في الواقع عن ToEnd خوارزمية الانحراف المعياري مع زيادة عدد اللقطات.نوع الأسلوب ثابت هذا.
Testing ["a", "b", "c", "d", "e"]
-------------------------
Picks ToEnd (StdDev) Sort (StdDev)
5 0.59 0.57
10 0.76 0.68
15 0.93 0.74
20 1.04 0.74
25 1.20 0.73
30 1.28 0.73
35 1.34 0.74
40 1.50 0.75
45 1.53 0.75
45 1.56 0.77
80 2.04 0.79
125 2.52 0.74
180 3.11 0.77
245 3.53 0.79
320 4.05 0.75
405 4.52 0.76
500 5.00 0.78
وهنا بعض نتائج الاختبار على مجموعة أكبر.
Testing ["a", "b", "c", "d", "e", "f", "g", "h", "i", "j"]
-------------------------
Picks ToEnd (StdDev) Sort (StdDev)
10 0.68 0.65
20 0.87 0.77
30 1.04 0.80
40 1.18 0.82
50 1.30 0.85
60 1.43 0.84
70 1.57 0.87
80 1.65 0.88
90 1.73 0.87
90 1.71 0.87
160 2.30 0.89
250 2.83 0.88
360 3.44 0.88
490 3.89 0.88
640 4.54 0.87
810 5.12 0.88
1000 5.66 0.85
مع اختبار جيد الإطار, لم أستطع مقاومة محاولة رقم عشوائي التحول.كان الافتراض لي إذا كنت تأخذ الجذر المكعب بدلا من الجذر التربيعي لـ x بلدي الانحراف المعياري سينخفض.في الواقع, ولكن كنت قلقا من أن هذا من شأنه أن يقلل العشوائية.هنا يمكنك أن نلاحظ بعض المحاكاة عندما يتم تغيير الصيغة
index = Int(l*(1-r^(0.33)) # l=length, r=uniform random var between 0 and 1
الآن فحص الفعلي يختار.كما اعتقدت ، المرجحة إلى بداية القائمة في البداية.إذا كنت ترغب في الوزن هذا بشكل كبير, ربما يجب عليك بطريقة عشوائية القائمة الخاصة بك قبل أن تبدأ.
StdDev = 0.632455532033676
{"a"=>10, "b"=>10, "c"=>11, "d"=>9, "e"=>10}
a d e c b c e b a d b e c a d d e b a e e c c b d a d c b c e b a a d d b e a e a b c b d c a c e c
StdDev = 0.0
{"a"=>10, "b"=>10, "c"=>10, "d"=>10, "e"=>10}
b c d a a d b c b a d e c d e c b e b a e e d c c a b a d a e e b d b a e c c e b a c c d d d a b e
StdDev = 0.632455532033676
{"a"=>9, "b"=>10, "c"=>10, "d"=>10, "e"=>11}
b d a e b c a d c e e b a c a d d c b c e d a e b b a c d c d a e a e e b d c b e a b c b c d d e e
StdDev = 0.0
{"a"=>10, "b"=>10, "c"=>10, "d"=>10, "e"=>10}
a b e d c e a b d c b c c a d b e e b e a d d c e a d b b c c a a a b e d d e c c a b b e a c d e d
StdDev = 0.632455532033676
{"a"=>11, "b"=>10, "c"=>9, "d"=>10, "e"=>10}
b a d c d c a e b e a e b c d b c a a d e e d c d e c b a b b e d c d b c e a a a d b c e b e a d a
نصائح أخرى
استخدم قائمة انتظار مرجحة: بدلاً من استخدام قائمة ، قسّم مجموعتك إلى دلاء - كل دلو له تردد مرتبط بالاسترجاع. تنتقل العناصر من دلاء التردد الأعلى إلى تلك الترددات المنخفضة عند اختيارها.
تتمثل إحدى الطرق السهلة لتنفيذ ذلك في تعيين كل دلو مجموعة من القيم ، وإنشاء رقم عشوائي داخل النطاق المدمج لاختيار دلو للاختيار من بينها. من المحتمل أن ترغب في تجريد هذه المجموعة في نوع من الفصل حتى لا تعرض المستهلكين للتفاصيل.
الخوارزمية:
في البداية ، تبدأ جميع العناصر في نفس دلو (المستوى الأعلى).
عند تحديد عنصر ما ، انقله من الدلو ، إلى الدلو السفلي التالي. إذا لزم الأمر ، قم بإنشاء دلو المستوى التالي.
عند إضافة عنصر جديد ، أضفه إلى الجزء العلوي (الأكثر استخدامًا).
لتحديد عنصر عشوائيًا ، اختر أولاً دلوًا ، ثم اختر عنصرًا داخل الدلو. انقل العنصر المحدد لأسفل إلى دلو المستوى التالي. لاحظ أن نقل العنصر لأسفل إلى دلو التردد المنخفض أمر اختياري - يمكنك تعيين بعض نقطة القطع.
عند إنشاء دلو جديد ، قم بتحديث نطاق الاسترجاع المرتبط بجميع الدلاء لإعطاء مجموعة جديدة من خاصية توزيع التردد التي تريدها.
C# تنفيذ (القطع الأولى) لقائمة انتظار مرجحة مرجعية عامة:
using System;
using System.Collections.Generic;
using System.Linq;
namespace Utility
{
public class BucketWeightedQueue<T>
{
private int m_MaxFallOff;
private readonly double m_FallOffRate;
private readonly List<List<T>> m_Buckets;
private readonly List<int> m_FallOffFactors;
private readonly Random m_Rand = new Random();
public BucketWeightedQueue(IEnumerable<T> items, double fallOffRate )
{
if( fallOffRate < 0 )
throw new ArgumentOutOfRangeException("fallOffRate");
m_MaxFallOff = 1;
m_FallOffRate = fallOffRate;
m_Buckets = new List<List<T>> { items.ToList() };
m_FallOffFactors = new List<int> { m_MaxFallOff };
}
public T GetRandomItem()
{
var bucketIndex = GetRandomBucketIndex();
var bucket = m_Buckets[bucketIndex];
var itemIndex = m_Rand.Next( bucket.Count );
var selectedItem = bucket[itemIndex];
ReduceItemProbability( bucketIndex, itemIndex );
return selectedItem;
}
private int GetRandomBucketIndex()
{
var randFallOffValue = m_Rand.Next( m_MaxFallOff );
for (int i = 0; i < m_FallOffFactors.Count; i++ )
if( m_FallOffFactors[i] <= randFallOffValue )
return i;
return m_FallOffFactors[0];
}
private void ReduceItemProbability( int bucketIndex, int itemIndex )
{
if( m_FallOffRate <= 0 )
return; // do nothing if there is no fall off rate...
var item = m_Buckets[bucketIndex][itemIndex];
m_Buckets[bucketIndex].RemoveAt( itemIndex );
if( bucketIndex <= m_Buckets.Count )
{
// create a new bucket...
m_Buckets.Add( new List<T>() );
m_MaxFallOff = (int)(m_FallOffFactors[bucketIndex] / m_FallOffRate);
m_FallOffFactors.Add( m_MaxFallOff );
}
var nextBucket = m_Buckets[bucketIndex + 1];
nextBucket.Add( item );
if (m_Buckets[bucketIndex].Count == 0) // drop empty buckets
m_Buckets.RemoveAt( bucketIndex );
}
}
}
كل هذا يتوقف على كيفية تختلف احتمالية اختيارها عند تحديد عنصر معين.
هناك طريقة بسيطة لتحقيق ذلك مع رسم مزدوج ، حيث تبدأ بقائمة الإدخال (التي لا تتغير أبدًا) وقائمة فارغة تضيف إليها العناصر المحددة بشكل عشوائي. بعد كل رسم عادي ، (من القائمة الأولى) ، يمكنك رسم عنصر واحد من القائمة الثانية. إذا ظهر العنصر نفسه (أو بالأحرى قيمة العنصر) مرة أخرى ، فلا يتم تحديده (أي رسم غير صالح ، ابدأ من جديد) ، وإلا يتم إضافة تعداد السحب والقيمة المقابلة إلى القائمة الثانية.
المفهوم العام يبدو يتعلق بمصادر ergodic.
DigitalJoe علق على عيب واضح لهذا النهج. باختصار ، أشار جو إلى أن احتمال منع التكرار (وليس بالضرورة التكرارات المتتالية ، فقط "التكرار") لقيمة عنصر مرسومة مسبقًا (قيمة موجودة في القائمة الثانية من الخوارزمية) تتقلب بشكل كبير في المئات من الرسومات الأولى . كان هناك تعليق ضمني آخر أنه بعد أن تحتوي القائمة الثانية على بضع عشرات من القيم ، يكون احتمال منع مثل هذا الازدواج منخفضًا للغاية. هذه نقاط صالحة ، وتتطلب التأهيل.
يطابق هذا المنطق فهمنا البديهي للطريقة التي تعمل بها القائمة الثانية: كلما زادت قيم العناصر هناك ، أقل فرص التي لدينا "رسم مزدوج" ، وبالتالي لمنع التكرار. هذا صحيح ولكنه يركز فقط على القائمة الثانية. احتمال رسم [من القائمة الأولى] يجب أن يأخذ العنصر الذي سبق رؤيته في الاعتبار. يمكننا استخدام مثالين لتنسيق هذه الفكرة ، ولكن هذا بالطبع تدرج:
- الحالة "A": يكون احتمال رسم قيمة عنصر معين منخفضًا نسبيًا مقارنة باحتمال رسم شيء آخر. وبالتالي ، فإن الاحتمال المشترك لرسم هذا العنصر عدة مرات خلال الرسومات القليلة الأولى منخفض ، واحتمال القيام بذلك ثم التخلص منه بسبب الرسم (الرسم) في القائمة الثانية (على الرغم من أن الاحتمال الأخير قد يكون عالية ، بسبب عدد قليل من العناصر في القائمة الثانية).
- الحالة "B": احتمال رسم عنصر معين نسبيًا إلى احتمال رسم عناصر أخرى. في هذه الحالة ، يكون احتمال وجود تكرار في السحب القليلة الأولى عالية ، وبما أن احتمال منع التكرار الفعلي (مع الرسم في القائمة الثانية) يكون مرتفعًا أيضًا (اليقين للرسم الثاني ، فرصة بنسبة 50 ٪ في الرسم الثاني ... فرصة بنسبة 10 ٪ على الرسم الحادي عشر) ، فإن الاحتمال الكلي لـ "معاقبة" عنصر محتمل للغاية مرتفع. ومع ذلك ، فهذه ليست مشكلة ، لأن الاحتمال النسبي لرسم العنصر من القائمة الأولى سيضمن أنه سيكون هناك ، إحصائيًا ، العديد من الفرص الأخرى لإنتاج التكرارات التي لن يتم قمعها "بقوة" مع تقدم عدد الرسومات .
في كلتا الحالتين ، ما يهم هو أن التوزيع الكلي للرسومات الفعلية يتطابق مع التوزيع في قائمة الإدخال. هذا صحيح بشكل خاص لأن عدد الرسومات يصبح أكثر ذات دلالة إحصائية.
فيما يتعلق بمسألة إمكانية وجود مرشح تكرار ضعيف للغاية ، يصبح ذلك أقل أهمية لأن القائمة الثانية تعكس المزيد والمزيد من توزيع القائمة الأولى. ربما تكون هناك طريقة للتعرف على كل هذا هو النظر في طرق بديلة لتحقيق الأهداف الموضحة في سؤال البروتوكول الاختياري.
خوارزميات بديلة:
Algo 1: الرسم دون استبدال من القائمة الأولى. أن نستخدم نسخة من القائمة الأصلية للبدء ، وفي كل مرة يتم رسم عنصر معين ، سنقوم بإزالته من تلك القائمة ، وبالتالي جعلها أقل بشكل عام على الأرجح أن نفس القيمة ستظهر مرة أخرى. بحلول الوقت الذي نرسم فيه جميع العناصر ، كنا نستنسخ بالضبط توزيع القائمة الأصلية.
Algo 2:الرسم دون استبدال, ، من قائمة حيث تم تكرار القائمة الأصلية عددًا معينًا من المرات. هذا مشابه لما ورد أعلاه ، لكنه يقدم المزيد من العشوائية قليلاً ، أي من خلال طلب عدد أكبر من الرسومات لجعل الرسومات تعارض النهج ومطابقة القائمة الأصلية.
بطريقة ما ، فإن خوارزمية القائمة التي اقترحتها في الأصل (ارسم مع الاستبدال من القائمة الأصلية وإدارة القائمة الثانية لمنع التكرار في بعض الأحيان) تشبه Algo 2 ، بالطريقة التي يجعل توزيع الرسم يتقارب نحو القائمة الأصلية. ومع ذلك ، فإن ميزة الخوارزمية الأصلية هي أنها تجعل إدارة القوائم أسهل (على الرغم من أنه في الإنصاف ، فإن طريقة بسيطة للقيام بذلك هي استبدال العناصر المرسومة بقيمة "خالية" من نوع "الخلية الفارغة" ، والتي هي نفس الشيء ، في الاتجاه المعاكس ، فيما يتعلق بإعادة رسمها عندما ينتج الرسم في القائمة الثانية نفس قيمة العنصر ..)
يمكنك القيام بشيء مثل إنشاء فئة مخصصة (لقائمتك) ، والتي تخزن العنصر بالإضافة إلى الترجيح.
افتراضي الترجيح إلى 1 عند إضافة عنصر ، وتخزين (في "القائمة") إجمالي جميع أوزان جميع العناصر.
يمكنك بعد ذلك ، عند تحديد عنصر عشوائيًا ، ما عليك سوى اختيار رقم بين 0 -> إجمالي الأثقال لجميع العناصر في القائمة ، والمشي عبر القائمة للعثور على العنصر في هذا الموضع (عن طريق الترجيح). تقليل ترجيح هذا العنصر (يمكن أن يكون هذا بعض السقوط ، أي: اضرب الترجيح بمقدار 0.8 ، أو 0.5 - سيكون لديك الكثير من السيطرة على مدى سرعة احتمال انخفاضه) ، وإعادته.
الجانب السلبي هنا ، إذا كان لديك الكثير من العناصر ، هو أن اختيارك هو o (n) (حيث يجب عليك السير في القائمة). ولهذا السبب ، ربما أستخدم قائمة مرتبطة بالتخزين (سيتعين عليك المشي للاسترجاع على أي حال ، لذلك يمنحك هذا الإدراج/الإزالة بشكل أسرع).
إذا كنت لا تخزن عددًا كبيرًا من الخيارات ، فسيكون ذلك سهل التنفيذ ، ويمنحك الكثير من التحكم في الاحتمالات بالإضافة إلى الحد من الاحتمالات في وقت الاختيار.
استخدم الوقت المنقضي منذ إدراج العنصر أو تحديد آخر مرة كأولوية mofifier ... قم بتعيين كل عناصر الأولوية = مقدار الوقت لأنه تم إدراجه أو تحديده آخر مرة ، ثم ضبط فرصة اختياره عن طريق الضرب من خلال هذه الأولوية.
بمجرد حصولك على جميع فرص العناصر ، قم بتطبيعها ، (adjsut كلها من خلال نفس النسبة المحسوبة لجعلها جميعًا على إضافة ما يصل إلى 1.000) ، ثم استخدم تلك القيم كاحتمال تحديدها.
الاستراتيجية العامة لاختيار عنصر عشوائي مرجح من القائمة هي: امنح كل عنصر وزنًا. تطبيع ، بحيث يكون الوزن الإجمالي هو 1. (حتى تبدأ ، كل عنصر له وزن 1/N). فرز قائمتك بالوزن. اختر الآن رقمًا عشوائيًا بين 0 و 1 ، وانزل إلى القائمة المتراكمة حتى تعبر رقمك. على سبيل المثال ، إذا كانت أوزانك هي [0.4 ، 0.3 ، 0.2 ، 0.1] ورميتك العشوائية هو 0.63215 ، فإن أول خطوتين لديك إجمالي = 0.4 ، إجمالي = 0.7 ، ثم لاحظ أن 0.7 أكبر من 0.63215 لذا يمكنك إرجاع العنصر الثاني.
بمجرد اختيار عنصر ما ، تقوم بضبط ترجيحه لأسفل (ستحتاج إلى تجربة الصيغ التقليدية حتى تجد عنصرًا يناسبك ، وأبسطه هو ضربه فقط ببعض الكسر الثابت في كل مرة) ، ثم إعادة التكرار وكررها وكررها .
لاحظ أن هذا غير فعال إلى حد ما إذا كان لديك كثيرا من العناصر نظرًا لأنها o (n) في طول القائمة ، ولكن لا ينبغي أن يكون مهمًا في الممارسة العملية ما لم تكن تفعل ذلك في حلقة داخلية يجب تحسينها بشكل كبير أو ما شابه. إذا اتضح أنه مشكلة ، فيمكنك النظر في هياكل البيانات الهندسية مثل أشجار النطاق لتحسين البحث.
