Losowanie ważone rekordu z tabeli MySQL, Losownie imion generowanych zawodników według częstości występowania Opcje

[Apocalyptiq]

Mam tabelę z nazwiskami oraz ilością ich wystąpień w Polsce. Chciałbym teraz dla każdego generowanego zawodnika (gra siatkarska via www) wylosować jedno z tych nazwisk, ale biorąc pod uwagę częstość jego wystąpienia - czyli najczęściej byłby losowany nowak, później kowalski itp. proporcjonalnie do ilości wystąpień.

Jedyny pomysł na jaki wpadłem jak to zrealizować, to stworzyć tabelę, w której każde imie wystepowałoby tyle razy, ile ma wystąpień, tylko że wtedy dostałbym byczą tabele (miałaby tyle wpisów, ile jest polaków, czyli ok. 40 milionów (IMG:http://forum.php.pl/style_emoticons/default/biggrin.gif) ).

Jakieś lepsze pomysły? :-)

[sowiq]

Twój pomysł jest bardzo dobry, ale ja bym to trochę usprawnił.

Chodzi mi o robienie czegoś w rodzaju cache'u. Tworzysz sobie tą tablicę zawierającą 40 mln elementów i losujesz np. tysiąc nazwisk. Zapisujesz je do bazy danych. Później zamiast losowania wybierasz tylko kolejne nazwiska z bazy i usuwasz użyte. Kiedy zostanie Ci np. tylko 100, robisz losowanie kolejnego tysiąca.

Dzięki temu masz zachowane prawdopodobieństwo wystąpienia nazwisk i nie katujesz serwera (IMG:http://forum.php.pl/style_emoticons/default/smile.gif)

Ten post edytował sowiq 7.05.2009, 17:21:02

[Apocalyptiq]

Dzięki, super pomysł, na to bym nie wpadł :-)

Ja wymyśliłem jeszcze takie zapytanie SQL:

[SQL] pobierz, plaintext 
SELECT surname FROM surnames WHERE amount > (220217 * RAND()) ORDER BY RAND() LIMIT 1
[SQL] pobierz, plaintext 

Gdzie 220217 to liczba występowania najczęstszego nazwiska (Nowak) - losuję liczbę od 0 do 1, następnie mnożę przez nią tą maksymalną liczbę i losuje z nazwisk, których występowanie jest większe niż liczba, która nam wyszła, jedno nazwisko. No i losowanie to powtarzam, aż się uda (w przypadku wylosowania 0 nic by mi nie zwróciło). Tylko nie wiem jeszcze jak ze skutecznością tego, porobie małe testy :-)

Zrobiłem test tego zapytania na 1000 losowaniach, tak wyglądają najczęściej losowne imiona

Nowak - 11 - 0.011% (220217 - 0.0057%)
Kowalski - 4 - 0.004% (131940 - 0.0035%)
Wiśniewski - 4 - 0.004% (104418 - 0.0027%)
Jaworski - 4 - 0.004% (44104 - 0.0012%)
Kołodziej - 4 - 0.004% (26054 - 0.0007%)
Kowalczyk - 3 - 0.003% (87690 - 0.0023%)
...

Procent ludności obliczałem zakładając, że jest 38mln polaków.

Za bardzo ten sposób faworyzuje częściej występujące imiona - wystarczy że RAND wylosuje cóś większego od 0.6, i już do selekcji zostaje tylko Nowak...Bardzo dziwne że tak mało Nowaków wylosowało. Spróbowałem więc zmniejszyć tą liczbę z zapytania - z 220 tys do 100 tys, oto testy:

Nowak - 8 - 0.008% (220217 - 0.0057%)
Kowalski - 6 - 0.006% (131940 - 0.0035%)
Kamiński - 5 - 0.005% (87935 - 0.0023%)
...

Już mi zbrzydły te testy, jednak ten mój sposób za często losuje często występujące imiona, popróbuje z Twoim sposobem sowiq :-)

Jeszcze mam tylko problem co do imion - nie mogę w necie nigdzie znaleźć statystyk co do liczebności poszczególnych, może ktoś się na takowe gdzieś natknął? :-)

Spróbowałem narazie tylko utworzyć tą tablicę z pomnożonymi imonami, których jest o wiele mniej niż nazwisk (imion mam ponad 300, nazwisk ok. 200 000), gdzie najczęściej spotykane imie ma 1000, czyli po zsumowaniu wszystkich byłoby pewnie z 100 000 tego. Próba utworzenia takiej tablicy zakończyła się komunikatem:

Fatal error: Allowed memory size of 524288000 bytes exhausted (tried to allocate 35 bytes) in /opt/lampp/htdocs/application/controllers/admin.php on line 39

A ten limit pamięci ustawiłem bodajże do 500 mb. Więc serwer pewnie nawet samego losowania tych cache nie da rady przeprowadzić (to robie na kompie swoim, a na serwerach zwykle sa mniejsze limity na pamięć itp.).

[EDIT]

Wymyśliłem oszczędniejszy sposób - zapisuje sobie w osobnej tabeli sumę wszystkich częstości, następnie do tabel z imionami i nazwiskami dodaje nową kolumnę - nazwałem ją sum_cache - przechowuje sumę wszystkich częstości od A do danego imienia nazwiska, może przykład lepiej to zobrazuje:

firstname frequency sum_cache
Abraham 4 4
Abram 5 9
Achim 3 12
Adalbert 1 13
Adam 775 788
Adamczyk 3 791

A oto zapytanie, które ma losować imię:

[SQL] pobierz, plaintext 
SELECT surname FROM surnames WHERE sum_cache >= FLOOR(RAND() * (SELECT `value` FROM `cache` WHERE `key` = "surnames_sum")) ORDER BY sum_cache LIMIT 1
[SQL] pobierz, plaintext 

Losuję tu liczbę z zakresu od 0 do sumy wszelkich częstości, a następnie pobieram pierwsze imie, które ma sum_cache większe/równe od wylosowanej liczby.
Dla przykładu, jeżeli wylosowaną liczbą będzie 790, wylosowanym imieniem będzie Adamczyk (jest takie imie w ogóle? (IMG:http://forum.php.pl/style_emoticons/default/biggrin.gif) ), bo ono ma sum_cache większe od 790 i jest pierwszym imieniem większym od tej liczby.

Takie były założenia, tylko że to zapytanie zawsze losuje mi kogoś na A (z początku tabeli) ;/ Muszę pokombinować, gdzie może być błąd. Sprawdzałem już wartość liczby wylosowanej - jest ok.

Już wiem gdzie jest błąd -

[SQL] pobierz, plaintext 
SELECT `value` FROM `cache` WHERE `key` = "surnames_sum"
[SQL] pobierz, plaintext 

Nie jest interpretowane jako pobrana wartość, tylko cały wynik zapytania (all -> row -> value) ;/ Pobiore po prostu w osobnym zapytaniu tą wartość i wbinduje w to zapytanie.

[END EDIT]

Dopiero rozbicie tego wszystkiego na 2 zapytania oraz wylosowanie liczby w PHP zadziałało:

[PHP] pobierz, plaintext 
<?php
public function get_rand() {
        $surnames_sum = $this->db->query('SELECT `value` FROM `cache` WHERE `key` = \"surnames_sum\"')->current()->value;
        $sum_rand = mt_rand(0, $surnames_sum);
        return $this->db->query('SELECT surname FROM surnames WHERE sum_cache >= ? ORDER BY sum_cache LIMIT 1', $sum_rand)->current()->surname;
    }
?>
[PHP] pobierz, plaintext 

Ale najważniejsze że działa :-)

Ten post edytował Apocalyptiq 8.05.2009, 17:51:19