W dniu 2012-04-01 13:58, M.M. pisze:

> double x[1000];
> for( i=0 ; i<1000000 ; i++ )
> x[rand()%size] ++;

M=1000;
N=1000000;

Załóżmy, że naprawdę chcemy zrobić coś takiego.

do x[i] dodajemy liczbę z rozkładu dwumianowego
B(N,M/N); tyle, że nie są one niezależne.

Mając dobry generator liczb z rozkładu dwumianowego
można napisać:

n = N; //ile kulek jeszcze zostało.
for( i=0 ; i<M ; i++ )
{
int k = generuj_liczbę_losową_B ( n, 1.0/(M-i) );
x[i]+=k;
n-=k;
}

W każdym obrocie pętli kulki mogą wpaść (każda z prawdopodobieństwem
1/długość tablicy) w pierwszy element. Liczymy, ile wpadło,
pozostałe idą dalej, sytuację powtarzamy dla krótszej tablicy.
W ostatnim ruchu prawdopodobieństwo =1, wszystkie pozostałe kulki
lądują w ostatniej szufladce.


Równoważność z kodem MM zapewnia nam ta własność
http://en.wikipedia.org/wiki/Binomial_distribution#C
onditional_binomials


Napisanie... wygoglanie generatora rozkąłdu dwumianowego moze okazać
się męczące. Ale B(n,p) -> N(n*p,m*p*(1-p)) a generator rozkładu
normlanego każdy umie. Ważne jest aby spełnione były warunki
zbieżności rozkładów, poprzedni kod jest do tego celu zły.

n jest duże, rzędu 1000 na szufladkę. Wypadałoby urzymać
p w okolicach 0.5.

Dzielmy więc tablicę na dwie równe części, przydzielając im
wynikającą z rozkładu liczbe kulek.


krok(int tab[], int first;int last, int n )
{
if (first==last)
{
tab[first]+=n;
}else
{
podział = (first + last)/2;
int k = generuj_liczbę_losową_B ( n, ((double)
(podzial-first+1))/(last - first+1) );
// ile kulek w pierwszy podział
krok(tab,first,podzial,k);
krok(tab,podzial+1,last ,n-k);
}
}

Tutaj wyniki będą 'w miarę' nawet jeśli generator będzie
generatorem rozkładu normlanego z zaokrągleniem i obcięciem
brzegów.
powinno się tez w miare przyzwoicie równoległość (na drugim
poziomie podziału puścić w nowych wątkach).

pzdr
bartekltg