-
Path: news-archive.icm.edu.pl!news.icm.edu.pl!wsisiz.edu.pl!newsfeed2.atman.pl!newsfe
ed.atman.pl!.POSTED!not-for-mail
From: bartekltg <b...@g...com>
Newsgroups: pl.comp.programming
Subject: Re: dalsza optymalizacja
Date: Sun, 01 Apr 2012 19:51:38 +0200
Organization: ATMAN - ATM S.A.
Lines: 73
Message-ID: <jla4jc$79r$1@node2.news.atman.pl>
References: <jl73ie$b6f$1@inews.gazeta.pl> <jl9aaf$326$1@inews.gazeta.pl>
<jl9al3$ee7$1@inews.gazeta.pl> <jl9dfl$a80$1@inews.gazeta.pl>
<jl9e7f$epj$1@node2.news.atman.pl> <jl9ftm$j00$1@inews.gazeta.pl>
NNTP-Posting-Host: 144-mi3-6.acn.waw.pl
Mime-Version: 1.0
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 8bit
X-Trace: node2.news.atman.pl 1333302700 7483 85.222.69.144 (1 Apr 2012 17:51:40 GMT)
X-Complaints-To: u...@a...pl
NNTP-Posting-Date: Sun, 1 Apr 2012 17:51:40 +0000 (UTC)
User-Agent: Mozilla/5.0 (Windows NT 6.1; WOW64; rv:11.0) Gecko/20120327
Thunderbird/11.0.1
In-Reply-To: <jl9ftm$j00$1@inews.gazeta.pl>
Xref: news-archive.icm.edu.pl pl.comp.programming:196515
[ ukryj 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-12 Warszawa => PC Hardware Expert / Specjalista PC <=
- 2025-07-12 Warszawa => Account Manager - Usługi rekrutacyjne <=
- 2025-07-12 Warszawa => Administrator IT <=
- 2025-07-12 Warszawa => IT Administrator <=
- 2025-07-12 Warszawa => Asystent/tka ds. Administracji <=
- 2025-07-12 Warszawa => Specjalista/stka ds. Organizacji <=
- 2025-07-12 Warszawa => MENA New Business Manager <=
- 2025-07-12 Gdynia => Controlling systems Consultant <=
- 2025-07-12 Warszawa => Developer Microsoft Dynamics 365 Finance & Operations (D36
- 2025-07-12 Warszawa => Programista Microsoft Dynamics 365 Finance & Operations (D
- 2025-07-12 Warszawa => Dyrektor IT <=
- 2025-07-12 Warszawa => IT Director <=
- 2025-07-12 Czy wypowiedź Kaczyńskiego o Braunie jest skarżalna? ["działa z OBCEJ inspiracji"]
- 2025-07-11 Rejestrator temperatur - termopara, siec
- 2025-07-11 DPD, przeniesienie numerów z a2mobile i z Orange