تنفيذ المصدر المفتوح لطريقة الاسم المستعار [مغلق]

Question

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

أي أن هناك ثلاثة أشخاص (أ، ب ج)، ولكل منهم احتمال P{i} للحصول على عنصر ما، حيث تشير p{a} إلى احتمال a.يتم حساب هذه الاحتمالات في وقت التشغيل، ولا يمكن ترميزها ضمنيًا.

ما أردت فعله هو إنشاء رقم عشوائي واحد (لعنصر ما)، وحساب من يحصل على هذا العنصر بناءً على احتمالية حصوله عليه.طريقة الاسم المستعار (http://books.google.com/books?pg=PA133&dq=alias+method+walker&ei=D4ORR8ncFYuWtgOslpVE&sig=TjEThBUa4odbGJmjyF4daF1AKF4&id=ERSSDBDcYOIC&output=html) الموضح هنا أوضح كيف، ولكني أردت معرفة ما إذا كان هناك تطبيق جاهز لذلك لن أضطر إلى كتابته.

Answer 1

هل سيفعل شيء مثل هذا؟ضع كل العناصر p{i} في المصفوفة، وستعيد الدالة فهرسًا إلى الشخص الذي حصل على العنصر.ينفذ في O(ن).

public int selectPerson(float[] probabilies, Random r) {
    float t = r.nextFloat();
    float p = 0.0f;

    for (int i = 0; i < probabilies.length; i++) {
        p += probabilies[i];
        if (t < p) {
            return i;
        }
    }

    // We should not end up here if probabilities are normalized properly (sum up to one)
    return probabilies.length - 1;      
}

يحرر:لم أختبر هذا حقًا.كانت وجهة نظري هي أن الوظيفة التي وصفتها ليست معقدة للغاية (إذا فهمت ما تقصده بشكل صحيح)، ولن تحتاج إلى تنزيل مكتبة لحل هذه المشكلة.

Answer 2

إليك تطبيق روبي: https://github.com/cantino/walker_method

Answer 3

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

    void test() {
        for (int i = 0; i < 10; i++) {
            once()
        }
    }
    private def once() {
        def double[] probs = [1 / 11, 2 / 11, 3 / 11, 1 / 11, 2 / 11, 2 / 11]
        def int[] whoCounts = new int[probs.length]
        def Random r = new Random()
        def int who
        int TIMES = 1000000
        for (int i = 0; i < TIMES; i++) {
            who = selectPerson(probs, r.nextDouble())
            whoCounts[who]++
        }
        for (int j = 0; j < probs.length; j++) {
            System.out.printf(" %10f ", (probs[j] - (whoCounts[j] / TIMES)))
        }
        println ""
    }
    public int selectPerson(double[] probabilies, double r) {
        double t = r
        double p = 0.0f;
        for (int i = 0; i < probabilies.length; i++) {
            p += probabilies[i];
            if (t < p) {
                return i;
            }
        }
        return probabilies.length - 1;
    }

outputs: the difference betweenn the probability, and the actual count/total 
obtained over ten 1,000,000 runs:
  -0.000009    0.000027    0.000149   -0.000125    0.000371   -0.000414 
  -0.000212   -0.000346   -0.000396    0.000013    0.000808    0.000132 
   0.000326    0.000231   -0.000113    0.000040   -0.000071   -0.000414 
   0.000236    0.000390   -0.000733   -0.000368    0.000086    0.000388 
  -0.000202   -0.000473   -0.000250    0.000101   -0.000140    0.000963 
   0.000076    0.000487   -0.000106   -0.000044    0.000095   -0.000509 
   0.000295    0.000117   -0.000545   -0.000112   -0.000062    0.000306 
  -0.000584    0.000651    0.000191    0.000280   -0.000358   -0.000181 
  -0.000334   -0.000043    0.000484   -0.000156    0.000420   -0.000372