Επιλογή τυχαίου στοιχείου με συντελεστή βάρους

Βρήκες ή ψάχνεις κάτι ενδιαφέρον για τους τομείς των Μαθηματικών, της Φυσικής ή της Πληροφορικής; Για πέρνα να τα πούμε...

Συντονιστές: kostas213, markelos, Tulis

Απάντηση
Άβαταρ μέλους
drcypher
Portal Administrator
Portal Administrator
Δημοσιεύσεις: 2299
Εγγραφή: Τετ Νοέμ 01, 2006 7:33 am
Real Name: Κώτσος Φίλ
Gender: Male
Τοποθεσία: Μπροστά στην οθόνη

Επιλογή τυχαίου στοιχείου με συντελεστή βάρους

Δημοσίευση από drcypher »

Έστω ότι έχετε ένα σύνολο από στοιχεία, μια γεννήτρια τυχαίων αριθμών που ακολουθούν ομοιόμορφη κατανομή και θέλετε έναν αλγόριθμο που να επιλέγει κάθε φορά στην τύχη ένα από τα στοιχεία, καθένα με έναν συντελστή βάρους (για απλότητα ακέραιο) ώστε κάποια να είναι πιο πιθανόν να επιλεγούν από τα άλλα.

Ας υποθέσουμε ότι το σύνολό μας αποτελείται από τα στοιχεία {big_65, medium_20, small_10, tiny_04, trivial_01} με αντίστοιχους συντελεστές βάρους 65, 20, 10, 4 και 1 αντίστοιχα (το άθροισμά τους είναι επίτηδες 100 για ευκολία στην ανάγνωση των αποτελεσμάτων, αλλά αυτό εν γένει δεν είναι υποχρεωτικό.

Στην php μπορείτε να περιγράψετε το παραπάνω παράδειγμα ως εξής:

Κώδικας: Επιλογή όλων

$arr_items = array(
    'big_65'    =>65,
    'medium_20' =>20,
    'small_10'  =>10,
    'tiny_04'   =>4,
    'trivial_01'=>1
);    
Φυσικά μπορείτε να κάνετε τις δοκιμές σε οποιαδήποτε γλώσσα και να δώσετε άλλα ονόματα στα στοιχεία, ή να χρησιμοποιήσετε αντί για ονόματα αριθμούς (σε γλώσσες όπως η C όπου οι παραπάνω καταστάσεις δεν υλοποιούνται εξίσου εύκολα όπως στην php).

Η γεννήτρια τυχαίων αριθμών (σε ομοιόμορφη κατανομή) περιέχεται στην καθιερωμένη βιβλιοθήκη της php και ορίζεται ως εξής:

Κώδικας: Επιλογή όλων

int mt_rand( int $min , int $max )
Προφανώς η mt_rand επιστρέφει έναν ακέραιο αριθμό ανάμεσα στο $min και στο $max.

Η πρώτη ιδέα υλοποίησης (και εν τέλει σωστή) είναι η εξής:
  • Φανταζόμαστε κάθε στοιχείο σαν ένα σύνολο από συνεχόμενα κρικάκια ίδιου χρώματος πάνω σε έναν άβακα. Στο παράδειγμά μας θα είχαμε π.χ. 65 κόκκινα κρικάκια για το big_65, κατόπιν 20 πράσινα για το medium_20, 10 γαλάζια για το small_10, 4 κίτρινα για το tiny_04 και 1 λευκό για το trivial_01.
  • Υπολογίζουμε το σύνολο των συντελεστών βάρους (ή κρίκων) όλων των υποψήφιων στοιχείων μαζί, έστω S.
  • Επιλέγουμε με τη βοήθεια της τυχαίας γεννήτριας έναν ακέραιο n από το 1 έως το S.
  • Αν ο n βρίσκεται στο διάστημα [1, 65], τότε αντιστοιχεί σε κόκκινο κρίκο, οπότε "κερδίζει" το big_65. Αν βρίσκεται ανάμεσα στο (65, 85], τότε αντιστοιχεί σε πράσινο κρίκο και "κερδίζει" το medium_20, κοκ..
Μια υλοποίηση αυτής της ιδέας σε php είναι η παρακάτω:

Κώδικας: Επιλογή όλων

// Weighted rand()
function int_wrand(&$arr)
{
    $int_sum = 0;
    foreach ($arr as $int_weight) {
        $int_sum += $int_weight;
    }

    $int_rand = mt_rand(1, $int_sum);

    $int_sum = 0;
    foreach ($arr as $int_key=>$int_weight) {
        if (($int_rand > $int_sum) && ($int_rand <= $int_sum + $int_weight)) {
            break;
        } else {
            $int_sum += $int_weight;
        }
    }

    return $int_key;
}    
Μια δεύτερη ιδέα (και εν τέλει λανθασμένη) είναι η εξής:
  • Σαρώνετε όλα τα στοιχεία του συνόλου Α και υπολογίζετε ένα "score", το οποίο ισούται με έναν τυχαίο αριθμό (διαφορετικό για κάθε στοιχείο) επί το βάρος του στοιχείου.
  • Το στοιχείο με το μεγαλύτερο "score" κερδίζει.
Μια υλοποίηση σε php ακολουθεί:

Κώδικας: Επιλογή όλων

// "Scored" rand()
function int_wrand2(&$arr)
{
    $int_max_score = 0;
    $int_max_key = 0;

    foreach ($arr as $int_key=>$int_weight) {
        $int_score = mt_rand(2, 2000) * $int_weight;

        if ($int_score > $int_max_score) {
            $int_max_score = $int_score;
            $int_max_key = $int_key;
        }
    }
    return $int_max_key;
}    
Η επιλογή του διαστήματος [2, 2000] είναι τελείως αυθαίρετη. Όπως φαίνεται, πάντως, αρκετά έντονες διαφοροποιήσεις του διαστήματος επηρεάζουν τα αποτελέσματα γύρω από τα οποία τίθεται το τελικό ερώτημα.

Κατόπιν φτιάχνουμε μια ρουτίνα ελέγχου των δυο αλγορίθμων. Το κριτήριο της επιτυχίας ή μη ενός από τους παραπάνω αλγορίθμου είναι προφανής: Αν τρέξουμε πολλές φορές κάθε αλγόριθμο, τότε η επί τοις εκατό συχνότητα επιλογής (ή "νίκης") κάθε στοιχείου θα πρέπει να τείνει προς την αριθμητική τιμή του συντελεστή βάρους (γι'αυτό και επιλέξαμε άθροισμα συντελεστών το 100).

Η ρουτίνα ελέγχου που ακολουθεί σε php, παίρνει ως παραμέτρους το σύνολο των στοιχείων, την μέθοδο που θέλουμε να δοκιμάσουμε και τον αριθμό των δοκιμών που θέλουμε να κάνουμε:

Κώδικας: Επιλογή όλων

function int_microtime()
{
    list($usec, $sec) = explode(' ',microtime());
    return ((float)$usec + (float)$sec);
}

// Test a given algorithm
function test(&$arr_items, $fn, $int_tests = 100)
{
    print("<br />Testing RNG '$fn' ($int_tests cycles)... ");

    // Initialize array of wins
    $arr_won = array();
    foreach ($arr_items as $int_key=>$int_weight) {
        $arr_won[$int_key] = 0;
    }

    // Run the RNG
    $int_time = int_microtime();
    for ($i = 0; $i < $int_tests; $i++) {
        $int_won = $fn($arr_items);
        $arr_won[$int_won]++;
    }
    $int_time = int_microtime() - $int_time;
    print('finished in '.sprintf('%.2f', 1000 * $int_time).' milliseconds<br />');

    // Display final frequencies
    foreach ($arr_won as $int_key=>$int_won) {
        $flt_won = 100 * $int_won / $int_tests;
        $flt_gain = ($flt_won - $arr_items[$int_key]);
        print("<strong>$int_key</strong>: ".sprintf("%.2f", $flt_won)."% (gain: ".$flt_gain.")<br />");
    }
}    
Εν τέλει τρέχουμε εκτελούμε τον έλεγχο για κάθε αλγόριθμο ξεχωριστά για 10.000 φορές:

Κώδικας: Επιλογή όλων

test($arr_items, 'int_wrand', 100000);
test($arr_items, 'int_wrand2', 100000);    
Για τον πρώτο αλγόριθμο παίρνουμε το παρακάτω

Κώδικας: Επιλογή όλων

Testing RNG 'int_wrand' (100000 cycles)... finished in 797.87 milliseconds
big_65: 65.16% (gain: 0.16)
medium_20: 20.02% (gain: 0.025)
small_10: 9.85% (gain: -0.148)
tiny_04: 3.97% (gain: -0.028)
trivial_01: 0.99% (gain: -0.009)
ενώ για τον δεύτερο

Κώδικας: Επιλογή όλων

Testing RNG 'int_wrand2' (100000 cycles)... finished in 1311.84 milliseconds
big_65: 83.19% (gain: 18.19)
medium_20: 14.21% (gain: -5.795)
small_10: 2.48% (gain: -7.517)
tiny_04: 0.12% (gain: -3.878)
trivial_01: 0.00% (gain: -1)
Στην πρώτη περίπτωση βλέπουμε ότι τα ποσοστά εκλογής κάθε στοιχείου πράγματι είναι πολύ κοντά στις "κανονικοποιημένες" (στο 100) βαρύτητες. Φυσικά υπάρχει πάντα μια διακύμανση η οποία για κάθε εκτέλεση της δοκιμής είναι διαφορετική αλλά πρακτικά αμελητέα.

Στην δεύτερη περίπτωση το αποτέλεσμα είναι μάλλον αξιοπερίεργο: Το πρώτο στοιχείο (δηλ. αυτό με το μεγαλύτερο βάρος) εμφανίζεται σημαντικά συχνότερα (το "gain" δείχνει πόσες ποσοστιαίες μονάδες αποκλίνει η μετρούμενη εμφάνιση από τον συντελεστή βάρους) εις βάρος όλων των υπόλοιπων στοιχείων που "παραχωρούν" τις "νίκες" τους με τυχαίο τρόπο.

Το ποσοστό "κέρδους", μάλιστα της πρώτης επιλογής είναι πρακτικά αμετάβλητο για κάθε τρέξιμο (με πολύ μικρές διακυμάνσεις). Για του λόγου το αληθές, να τι δίνει ένα δεύτερο τρέξιμο:

Κώδικας: Επιλογή όλων

Testing RNG 'int_wrand' (100000 cycles)... finished in 734.84 milliseconds
big_65: 65.02% (gain: 0.018)
medium_20: 19.72% (gain: -0.277)
small_10: 10.18% (gain: 0.175)
tiny_04: 4.07% (gain: 0.066)
trivial_01: 1.02% (gain: 0.018)

Testing RNG 'int_wrand2' (100000 cycles)... finished in 1188.41 milliseconds
big_65: 83.58% (gain: 18.578)
medium_20: 13.81% (gain: -6.186)
small_10: 2.46% (gain: -7.535)
tiny_04: 0.14% (gain: -3.858)
trivial_01: 0.00% (gain: -0.999)
Το πόσο κερδίζει κάθε φορά το μεγαλύτερο στοιχείο φαίνεται να εξαρτάται από το μέγεθος του βάρους του. Ενώ, λοιπόν, για τα παραπάνω το πρώτο στοιχείο "κέρδιζε" 18.5 μονάδες περίπου, η παρακάτω τροποποίηση των στοιχείων και των βαρών δείχνει μετατόπιση του κέρδους (το οποίο πάλι παραμένει σταθερό ανάμεσα στα τρεξίματα):

Κώδικας: Επιλογή όλων

$arr_items = array(
    'big_75'    =>75,
    'medium_12' =>12,
    'small_08'  =>8,
    'tiny_04'   =>4,
    'trivial_01'=>1
);    
Σύμφωνα με τα παρακάτω αποτελέσματα, οι 18.5 μονάδες έπεσαν στις περίπου 15.8.

Κώδικας: Επιλογή όλων

Testing RNG 'int_wrand' (100000 cycles)... finished in 752.51 milliseconds
big_75: 75.08% (gain: 0.08)
medium_12: 11.92% (gain: -0.079)
small_08: 7.96% (gain: -0.045)
tiny_04: 4.09% (gain: 0.087)
trivial_01: 0.96% (gain: -0.043)

Testing RNG 'int_wrand2' (100000 cycles)... finished in 1107.47 milliseconds
big_75: 90.85% (gain: 15.847)
medium_12: 6.71% (gain: -5.289)
small_08: 2.22% (gain: -5.777)
tiny_04: 0.22% (gain: -3.781)
trivial_01: 0.00% (gain: -1)
Το ερώτημα, λοιπόν, που τίθεται μετά από την παραπάνω εισαγωγή, είναι αρκετά απλό: Γνωρίζει κανείς που μπορεί να οφείλεται αυτή η (σταθερή!!!) "εύνοια" του "βαρύτερου" στοιχείου έναντι των υπολοίπων που προκύπτει στον δεύτερο αλγόριθμο; Κάτι μου λέει ότι δεν είναι καθόλου τυχαίο το πόσο προβάδισμα θα παίρνει το πρώτο στοιχείο και θα ήμουν ευγνώμων σε όποιον μπορούσε να μου το δικαιολογήσει/εξηγήσει. Εξαρτάται με κάποιον γνωστό/υπολογίσιμο τρόπο από το διάστημα της mt_rand? Εξαρτάται από τις απόλυτες ή τις σχετικές βαρύτητες; Από το πλήθος των στοιχείων; :S
Από τούδε και στο εξής ως στρογγυλοί αριθμοί ορίζονται τα πολλαπλάσια του 5 και οι δυνάμεις του 2.
Απάντηση

Επιστροφή στο “Ζητήματα Μαθηματικών - Φυσικής - Πληροφορικής”