Generator liczb losowych, ... rozłożonych równomiernie Opcje

[bobens_83]

Witam PHP'owcy (IMG:style_emoticons/default/smile.gif)

Mam napisac w PHP generator liczb losowych. Ma on losowac liczby z danego zakresu. Kazda kolejna wylosowana liczba ma zapisywac sie do bazy danych.

Moje pytanie dotyczy tego w jaki sposob w moim generatorze moglbym zaimplementowac kontrole rownomiernosci wynikow?
Chodzi mi o to, zeby zapewnic, ze dana nowo wylosowana liczba (powiedzmy liczba x), wraz z liczbami juz wczesniej wylosowanymi (powiedzmy liczby juz wylosowane tworza zbior Y) bedzie tworzyc zbior rozlozony rownomiernie w zakresie z ktorego losujemy liczby?

Przykladowo, jesli moj zbior z ktorego losuje liczby to 1-100, mam niedopuscic do sytuacji, ze kolejno przydzielane liczby (czyli moj zbior Y) beda np. 1, 2 i 3 no bo juz na pierwszy rzut oka widac, ze moj 3 elementowy zbior Y nie rozklada sie rownomiernie w przedziale 1-100. Co innego jakby byly to liczby 1, 100, 50 - wyglada to juz bardziej sensownie i ... 'rownomiernie'.

Bede wdzieczny za wszelkie wskazowki. Z gory dziekuje i pozdrawiam. P.

[kipero]

Możesz podzielić sobie zbiór, z którego losujesz liczby, na tyle podzbiorów, ile liczb chcesz wylosować.
Przykładowo, chcesz uzyskać 5 liczb z przedziału 1-100, to dzielisz go sobie na 5 i losujesz po jednej liczbie z przedziałów: 1-19, 20-39, 40-59, 60-79, 80-100. W ten sposób uzyskasz liczby rozłożone w miarę równomiernie.

[MySQL]

Wtrącę może tylko dwa zdania.

Po co miałbyś implementować w algorytmie kontrolę równomierności wyników? Prawdopodobieństwo wylosowania w pierwszych trzech losowaniach liczb 1, 2, 3 jest takie samo jak prawdopodobieństwo wylosowania liczb 1, 100, 50.

Pamiętaj, że każdy dodatkowy warunek nałożony na funkcję randomizującą tylko osłabia efektywność algorytmu a tym samym bezpieczeństwo. Przypuśćmy, że haker nie zna algorytmu ale dowiedział się, że tak skonstruowałeś algorytm aby wyniki losowania były równomiernie (przypuśćmy, że tak jak w przykładzie jaki podał kipero). Wówczas wie on, że nigdy Twój algorytm nie wylosuje liczb 1, 2, 3, 4, 5.

W ujęciu matematycznym: jeżeli losujesz 5 liczb ze zbioru 100 elementowego (rozwiązanie wg kipero) to moc zbioru wszystkich wyników wynosi:
19*19*19*19*20 czyli nie więcej niż 20⁵
Gdy losujesz zupełnie losowo: 96*97*98*99*100 czyli nie mniej niż 96⁵
A gdy dodasz jeszcze możliwość że liczby mogą się powtarzać zanim zostaną wylosowane wszystkie po jednej z tego zbioru to otrzymasz aż
100⁵ = (5 * 20)⁵ = 3125 * 20⁵

Czujesz różnicę?

Jak chcesz się na poważnie zajmować kryptografią to pamiętaj aby nie osłabiać algorytmów randomizujących jakimikolwiek warunkami. Ten, kto Tobie nakazał abyś zrobił algorytm z tak bardzo osłabiającym warunkiem jest chyba irackim szpiegiem (albo po prostu nie zna się na rzeczy).


--- Edit: ----
A co samego Twojego pytania o algorytm. Podaj jakieś szczegóły na jakim poziomie matematyki (wiesz co to kongruencja?) jesteś to może uda się jakąś literaturę polecić.

Ten post edytował MySQL 13.09.2009, 17:17:20

[bobens_83]

Dziekuje za posty,

niestety nie wiem czym jest kongruencja (tzn juz wiem bo z ciekawosci zajrzalem na wiki (IMG:style_emoticons/default/smile.gif) ), a z ta maematyka w szkole to bywalo roznie (IMG:style_emoticons/default/wstydnis.gif) Irackim szpiegiem tez nie jestem (IMG:style_emoticons/default/guitar.gif)

Wiec sprostowalem nieco polecenie ktore mam wykonac. Poczatkowo czesciowo blednie je zinterpretowalem, chociaz zagadnienie "rownomiernosci" tak czy siak mnie interesowalo wiec MySQL dziekuje za odpowiedzi.


A wiec po sprostowaniu polecenie brzmi nastepujaco:


Mam napisac algorytm losujacy ze liczby ze zbioru 1 000 000 - 2 000 000. Bez powtorzen.
Wylosowane juz liczby zapisywac sie maja do bazy MySQL.
Funkcja losujaca ma przyjmowac parametry: wartosc dolna predzialu, wartosc gorna przedzialu, tablica z juz wylosowanymi liczbami.
Mam pamietac, ze rand_max jest "o wiele za maly" na potrzeby tego zadania.
Algorytm ma dzialac ... im szybciej tym lepiej

Znalazlem kilka algorytmow losowania bez powtorzen, np ten. Jednak wiekszosc z nich pracuje na malych zbiorach, a moj ma 1 000 000 elementow.

I tu mam dylemat, wyczytalem ze w php wielkosc tablicy jest determinowana ustawieniami na serwerze. Ale tak czy siak ladowanie miliona rekordow z MySQLa to array'a to chyba nie przejdzie. I wogole to mam troche watpliwosci co do pracy z taka duza iloscia danych.

Macie jakis pomysl jak poradzic sobie z losowaniem z takiego duzego zbioru?

[redeemer]

Tablica z wylosowanymi już liczbami jako parametr funkcji nie jest dobrym pomysłem.

Przykładowo:

[PHP] pobierz, plaintext 
function my_random($begin, $end, &$array) {
	$elements=$end-$begin;
	while($elements>=0) {
		while( (in_array( ($x=mt_rand($begin,$end)), $array))) 
		;
 
		$array[]=$x;
 
		$elements--;
	}
 
};
[PHP] pobierz, plaintext 

Kod wyżej przy 1000 elementów na duronie 900mhz wykonuje się w 4.6900 sekundy. Jest to spowodowane tym, że przy każdej iteracji musimy "przeszukać tablicę" (in_array()) w poszukiwaniu elementu czy już się w niej znajduje.

Lepszym pomysłem byłoby stworzenie tablicy gdzie numer indeksu byłby naszą liczbą, a wartość flagą (1 - "jest już", 0 - "jeszcze nie ma"). Kod ten mógłby wyglądać tak:

[PHP] pobierz, plaintext 
function my_random2($begin, $end, &$array) {
	$elements=$end-$begin;
	while($elements>=0) {
		while($array[$begin+($x=mt_rand($begin,$end))])
		;
 
		$array[$begin+$x]=1;
 
		$elements--;
	}
}
[PHP] pobierz, plaintext 

Jego parametry wykonania przy takich samych przedziałach: 0.0198 sekundy, 142984 pamięci.

(W obu przypadkach pominąłem zapisywanie rekordów do bazy)

Jeżeli nie masz napisać algorytmu losowania liczb pseudo-losowych od nowa (tak mi się wydaje) to mt_getrandmax() = 2147483647, więc 2 miliony na pewno obejmie.

Tablica $array w drugim rozwiązanie przy 1 000 000 elementów o wielkości każdego z nich 4 bajty będzie zajmowała coś koło 3.81 MB. Gdyby wykorzystać
jakąś tablicę bitową to zajmowała by ona mniej więcej 0.12 MB

Mam nadzieję, że pomogłem.

Pozdrawiam,

Ten post edytował redeemer 14.09.2009, 13:49:56