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.

[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