ΣΕΜΦΕ forum

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

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

Στην php μπορείτε να περιγράψετε το παραπάνω παράδειγμα ως εξής: Φυσικά μπορείτε να κάνετε τις δοκιμές σε οποιαδήποτε γλώσσα και να δώσετε άλλα ονόματα στα στοιχεία, ή να χρησιμοποιήσετε αντί για ονόματα αριθμούς (σε γλώσσες όπως η C όπου οι παραπάνω καταστάσεις δεν υλοποιούνται εξίσου εύκολα όπως στην php).

Η γεννήτρια τυχαίων αριθμών (σε ομοιόμορφη κατανομή) περιέχεται στην καθιερωμένη βιβλιοθήκη της php και ορίζεται ως εξής: Προφανώς η 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 είναι η παρακάτω: Μια δεύτερη ιδέα (και εν τέλει λανθασμένη) είναι η εξής:

• Σαρώνετε όλα τα στοιχεία του συνόλου Α και υπολογίζετε ένα "score", το οποίο ισούται με έναν τυχαίο αριθμό (διαφορετικό για κάθε στοιχείο) επί το βάρος του στοιχείου.
• Το στοιχείο με το μεγαλύτερο "score" κερδίζει.

Μια υλοποίηση σε php ακολουθεί: Η επιλογή του διαστήματος [2, 2000] είναι τελείως αυθαίρετη. Όπως φαίνεται, πάντως, αρκετά έντονες διαφοροποιήσεις του διαστήματος επηρεάζουν τα αποτελέσματα γύρω από τα οποία τίθεται το τελικό ερώτημα.

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

Η ρουτίνα ελέγχου που ακολουθεί σε php, παίρνει ως παραμέτρους το σύνολο των στοιχείων, την μέθοδο που θέλουμε να δοκιμάσουμε και τον αριθμό των δοκιμών που θέλουμε να κάνουμε: Εν τέλει τρέχουμε εκτελούμε τον έλεγχο για κάθε αλγόριθμο ξεχωριστά για 10.000 φορές: Για τον πρώτο αλγόριθμο παίρνουμε το παρακάτω ενώ για τον δεύτερο Στην πρώτη περίπτωση βλέπουμε ότι τα ποσοστά εκλογής κάθε στοιχείου πράγματι είναι πολύ κοντά στις "κανονικοποιημένες" (στο 100) βαρύτητες. Φυσικά υπάρχει πάντα μια διακύμανση η οποία για κάθε εκτέλεση της δοκιμής είναι διαφορετική αλλά πρακτικά αμελητέα.

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

Το ποσοστό "κέρδους", μάλιστα της πρώτης επιλογής είναι πρακτικά αμετάβλητο για κάθε τρέξιμο (με πολύ μικρές διακυμάνσεις). Για του λόγου το αληθές, να τι δίνει ένα δεύτερο τρέξιμο: Το πόσο κερδίζει κάθε φορά το μεγαλύτερο στοιχείο φαίνεται να εξαρτάται από το μέγεθος του βάρους του. Ενώ, λοιπόν, για τα παραπάνω το πρώτο στοιχείο "κέρδιζε" 18.5 μονάδες περίπου, η παρακάτω τροποποίηση των στοιχείων και των βαρών δείχνει μετατόπιση του κέρδους (το οποίο πάλι παραμένει σταθερό ανάμεσα στα τρεξίματα): Σύμφωνα με τα παρακάτω αποτελέσματα, οι 18.5 μονάδες έπεσαν στις περίπου 15.8. Το ερώτημα, λοιπόν, που τίθεται μετά από την παραπάνω εισαγωγή, είναι αρκετά απλό: Γνωρίζει κανείς που μπορεί να οφείλεται αυτή η (σταθερή!!!) "εύνοια" του "βαρύτερου" στοιχείου έναντι των υπολοίπων που προκύπτει στον δεύτερο αλγόριθμο; Κάτι μου λέει ότι δεν είναι καθόλου τυχαίο το πόσο προβάδισμα θα παίρνει το πρώτο στοιχείο και θα ήμουν ευγνώμων σε όποιον μπορούσε να μου το δικαιολογήσει/εξηγήσει. Εξαρτάται με κάποιον γνωστό/υπολογίσιμο τρόπο από το διάστημα της mt_rand? Εξαρτάται από τις απόλυτες ή τις σχετικές βαρύτητες; Από το πλήθος των στοιχείων;