Ας υποθέσουμε ότι το σύνολό μας αποτελείται από τα στοιχεία {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
);
Η γεννήτρια τυχαίων αριθμών (σε ομοιόμορφη κατανομή) περιέχεται στην καθιερωμένη βιβλιοθήκη της php και ορίζεται ως εξής:
Κώδικας: Επιλογή όλων
int mt_rand( int $min , int $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, κοκ..
Κώδικας: Επιλογή όλων
// 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" κερδίζει.
Κώδικας: Επιλογή όλων
// "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;
}
Κατόπιν φτιάχνουμε μια ρουτίνα ελέγχου των δυο αλγορίθμων. Το κριτήριο της επιτυχίας ή μη ενός από τους παραπάνω αλγορίθμου είναι προφανής: Αν τρέξουμε πολλές φορές κάθε αλγόριθμο, τότε η επί τοις εκατό συχνότητα επιλογής (ή "νίκης") κάθε στοιχείου θα πρέπει να τείνει προς την αριθμητική τιμή του συντελεστή βάρους (γι'αυτό και επιλέξαμε άθροισμα συντελεστών το 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 />");
}
}
Κώδικας: Επιλογή όλων
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)
Στην δεύτερη περίπτωση το αποτέλεσμα είναι μάλλον αξιοπερίεργο: Το πρώτο στοιχείο (δηλ. αυτό με το μεγαλύτερο βάρος) εμφανίζεται σημαντικά συχνότερα (το "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)
Κώδικας: Επιλογή όλων
$arr_items = array(
'big_75' =>75,
'medium_12' =>12,
'small_08' =>8,
'tiny_04' =>4,
'trivial_01'=>1
);
Κώδικας: Επιλογή όλων
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)