-
Data: 2012-04-01 19:51:38
Temat: Re: dalsza optymalizacja
Od: bartekltg <b...@g...com> szukaj wiadomości tego autora
[ pokaż wszystkie nagłówki ]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
Następne wpisy z tego wątku
- 01.04.12 20:12 bartekltg
- 01.04.12 20:50
- 01.04.12 20:53 M.M.
- 01.04.12 21:57 bartekltg
- 01.04.12 22:09 M.M.
- 01.04.12 22:29 M.M.
- 01.04.12 22:44 bartekltg
- 01.04.12 22:49 bartekltg
- 01.04.12 22:50
- 01.04.12 23:56 M.M.
- 01.04.12 23:59 bartekltg
- 02.04.12 00:11 M.M.
- 02.04.12 00:13 M.M.
- 02.04.12 01:20 bartekltg
- 02.04.12 02:58 M.M.
Najnowsze wątki z tej grupy
- Can you activate BMW 48V 10Ah Li-Ion battery, connecting to CAN-USB laptop interface ?
- We Wrocławiu ruszyła Odra 5, pierwszy w Polsce komputer kwantowy z nadprzewodzącymi kubitami
- Ada-Europe - AEiC 2025 early registration deadline imminent
- John Carmack twierdzi, że gdyby gry były optymalizowane, to wystarczyły by stare kompy
- Ada-Europe Int.Conf. Reliable Software Technologies, AEiC 2025
- Linuks od wer. 6.15 przestanie wspierać procesory 486 i będzie wymagać min. Pentium
- ,,Polski przemysł jest w stanie agonalnym" - podkreślił dobitnie, wskazując na brak zamówień.
- Rewolucja w debugowaniu!!! SI analizuje zrzuty pamięci systemu M$ Windows!!!
- Brednie w wiki - hasło Dehomag
- Perfidne ataki krakerów z KRLD na skrypciarzy JS i Pajton
- Instytut IDEAS może zacząć działać: "Ma to być unikalny w europejskiej skali ośrodek badań nad sztuczną inteligencją."
- Instytut IDEAS może zacząć działać: "Ma to być unikalny w europejskiej skali ośrodek badań nad sztuczną inteligencją."
- Instytut IDEAS może zacząć działać: "Ma to być unikalny w europejskiej skali ośrodek badań nad sztuczną inteligencją."
- U nas propagują modę na SI, a w Chinach naukowcy SI po kolei umierają w wieku 40-50lat
- C++. Podróż Po Języku - komentarz
Najnowsze wątki
- 2025-07-03 ROG
- 2025-07-03 OZE dały Polsce więcej prądu niż elektrownie węglowe
- 2025-07-03 Dlaczego nikt nie powiadamia służb!
- 2025-07-02 Jaka ładowarka sieciowa do Iphona?
- 2025-07-02 ,,The Plot to Get RFK" (,,Spisek, by pozbyć się RFK")
- 2025-07-02 Rozkaz 17-2025: O Zaprzestaniu Zaciągania Kredytów
- 2025-07-02 Rozkaz 16-2025: 2025-06-19 Apelacja Do Wyroku Sądu Rej. w Sprawie IVRNs 295-23
- 2025-07-02 Rozkaz 17-2025: O Zaprzestaniu Zaciągania Kredytów
- 2025-07-02 Inżynierowie... inżynierzy...
- 2025-07-02 Can you activate BMW 48V 10Ah Li-Ion battery, connecting to CAN-USB laptop interface ?
- 2025-07-02 Kto potrafi sprawdzić aku BMW 48V 10Ah Li-Ion do mini hybrydy, czy sprawny ?
- 2025-07-02 Warszawa => Senior IT Recruitment Consultant <=
- 2025-07-02 Gdańsk => Konsultant wdrożeniowy (systemy controlingowe) <=
- 2025-07-02 Warszawa => IT Hardware Specialist - Wsparcie i Konfiguracja <=
- 2025-07-02 Warszawa => Inżynier oprogramowania .Net <=