Czesc

Jest liniowa tablica malych liczb staloprzecinkowych
int tablica[1..N];
N jest dosc duze, rzedu 100tys do 10mln.

Jest tablica indeksow
int index[1..M]

Kazdy index[i] dzieli tablice na pare tablic:
tablica_a[1..index[i]]
tablice_b[index[i]+1..N]

Czyli tablica_a ma index[i] pierwszych elementow z tablicy
a tablica_b ma elementy pozostale.

Zadanie jest takie, aby szybko oszacowac odchylenie standardowe dla kazdej
pary tablic ( dla kazdej tablicy w kazdej parze, razem 2*M odchylen ).
M niestety moze przyjmowac duze wartosci, a wiec par moze byc duzo,
np. M ~= N / log(N).

Mozna to policzyc jakims algorytmem online, albo np. algorytmem ktory
przebiega cala tablice nie wiecej niz 10 razy?

Pozdrawiam


--
Wysłano z serwisu Usenet w portalu Gazeta.pl -> http://www.gazeta.pl/usenet/

do góry

Dnia 30-01-2012 o 02:47:21 M.M. <m...@n...gazeta.pl> napisał(a):

> Czesc
>
> Jest liniowa tablica malych liczb staloprzecinkowych
> int tablica[1..N];
> N jest dosc duze, rzedu 100tys do 10mln.
>
> Jest tablica indeksow
> int index[1..M]
>
> Kazdy index[i] dzieli tablice na pare tablic:
> tablica_a[1..index[i]]
> tablice_b[index[i]+1..N]
>
> Czyli tablica_a ma index[i] pierwszych elementow z tablicy
> a tablica_b ma elementy pozostale.
>
> Zadanie jest takie, aby szybko oszacowac odchylenie standardowe dla
> kazdej
> pary tablic ( dla kazdej tablicy w kazdej parze, razem 2*M odchylen ).
> M niestety moze przyjmowac duze wartosci, a wiec par moze byc duzo,
> np. M ~= N / log(N).
>
> Mozna to policzyc jakims algorytmem online, albo np. algorytmem ktory
> przebiega cala tablice nie wiecej niz 10 razy?

moze cos takiego zadziala:

//input:
int tablica[1..N];
int indeksy[1..M];
//output:
int sigma_lower[1..M];
int sigma_upper[1..M];
//temp:
int tmp_sx[1..N];
int tmp_sxx[1..N];

int sx=0;
int sxx=0;
//prepare
for(int i=1;i<=N;i++){
sx=tmp_sx[i]=sx+tablica[i];
sxx=tmp_sxx[i]=sxx+tablica[i]*tablica[i];
}
//use
for(int j=1;j<=M;j++){
sigma_lower[j]=sqrt(tmp_sxx[indeksy[j]]/indeksy[j]-(
tmp_sx[indeksy[j]]/indeksy[j])*(tmp_sx[indeksy[j]]/i
ndeksy[j]);
sigma_upper[j]=sqrt((sxx-tmp_sxx[indeksy[j]])/(N-ind
eksy[j])-((sx-tmp_sx[indeksy[j]])/(N-indeksy[j]))*((
sx-tmp_sx[indeksy[j]])/(N-indeksy[j])));
}

czas bedzie rzedu N+M, dodatkowa pamiec rzedu N
w sumie to od razu moglbys policzyc se odchylenia dla wszystkich podzialow
tablicy


--
Jordan Szubert

do góry

W dniu 2012-01-30 02:47, M.M. pisze:
> Czesc
>
> Jest liniowa tablica malych liczb staloprzecinkowych
> int tablica[1..N];
> N jest dosc duze, rzedu 100tys do 10mln.
>
> Jest tablica indeksow
> int index[1..M]
>
> Kazdy index[i] dzieli tablice na pare tablic:
> tablica_a[1..index[i]]
> tablice_b[index[i]+1..N]
>
> Czyli tablica_a ma index[i] pierwszych elementow z tablicy
> a tablica_b ma elementy pozostale.
>
> Zadanie jest takie, aby szybko oszacowac odchylenie standardowe dla kazdej
> pary tablic ( dla kazdej tablicy w kazdej parze, razem 2*M odchylen ).
> M niestety moze przyjmowac duze wartosci, a wiec par moze byc duzo,
> np. M ~= N / log(N).
>
> Mozna to policzyc jakims algorytmem online, albo np. algorytmem ktory
> przebiega cala tablice nie wiecej niz 10 razy?


http://www.youtube.com/watch?v=gENVB6tjq_M



Odchylenie standardowe to pierwiastek wariancji.

Var(X) = E[ (X-E(X))^2 ] =...= E(X^2) - E(X)^2

Korzystamy z drugiej wersji.

Pisząc po ludzku sum_{i=1}^k (x_i^2/k)/k - ( sum_{i=1}^k x_i )^2/k


Ponieważ masz inty, nie musisz sie przejmować stratą dokładności
(np licząc odchylenie z dużęj próbki X ~ N(1,10^-12) lepiej użyć
pierwszego wzoru;) uważaj jedynie na zakres, bo prawie na pewno
przekroczysz int32, a dla odpowiednich danych i int64)

Liczysz więc na bieżąco sumę i sumę kwadratów, zapisujesz
je dla każdego k z tablicy index.
Potem za ich pomocą (oraz sumy i sumy kwadratów wszystkich)
obliczasz odchylenie w odpowiednich podtablicach.

Podsumowując masz jeden przejazd po 'tablica' z zapisywaniem
do tablic długości M (suma i suma kwadratów) a następnie
przelecenie tych tablic i wpisanie wyników (uważaj na związek
indeksu i długości przedziału==liczności próbki i pamiętaj
o pierwiastku:) IMHO najpierw odejmowanie, potem zrzut
na double i dzielenie.


pzdr
bartekltg

do góry

bartekltg <b...@g...com> napisał(a):

> W dniu 2012-01-30 02:47, M.M. pisze:
> > Czesc
> >
> > Jest liniowa tablica malych liczb staloprzecinkowych
> > int tablica[1..N];
> > N jest dosc duze, rzedu 100tys do 10mln.
> >
> > Jest tablica indeksow
> > int index[1..M]
> >
> > Kazdy index[i] dzieli tablice na pare tablic:
> > tablica_a[1..index[i]]
> > tablice_b[index[i]+1..N]
> >
> > Czyli tablica_a ma index[i] pierwszych elementow z tablicy
> > a tablica_b ma elementy pozostale.
> >
> > Zadanie jest takie, aby szybko oszacowac odchylenie standardowe dla kazdej
> > pary tablic ( dla kazdej tablicy w kazdej parze, razem 2*M odchylen ).
> > M niestety moze przyjmowac duze wartosci, a wiec par moze byc duzo,
> > np. M ~= N / log(N).
> >
> > Mozna to policzyc jakims algorytmem online, albo np. algorytmem ktory
> > przebiega cala tablice nie wiecej niz 10 razy?
>
>
> http://www.youtube.com/watch?v=gENVB6tjq_M
>
>
>
> Odchylenie standardowe to pierwiastek wariancji.
>
> Var(X) = E[ (X-E(X))^2 ] =...= E(X^2) - E(X)^2
>
> Korzystamy z drugiej wersji.
>
> Pisząc po ludzku sum_{i=1}^k (x_i^2/k)/k - ( sum_{i=1}^k x_i )^2/k

Dzieki serdeczne, zapomnialem o drugim wzorze
Pozdrawiam!



--
Wysłano z serwisu Usenet w portalu Gazeta.pl -> http://www.gazeta.pl/usenet/

do góry

Jordan Szubert <u...@j...us.to> napisał(a):

> czas bedzie rzedu N+M, dodatkowa pamiec rzedu N
> w sumie to od razu moglbys policzyc se odchylenia dla wszystkich podzialow

Po tym jak Bartek przypomnial drugi wzor nie widze potrzeby uzycia
dodatkowej pamieci. Wystarczy zapamietac sume i sume kwadratow w
pierwszym przebiegu. W drugim przebiegu druga sume i druga sume kwadratow
trzeba naliczac, a od pierwszych sum odejmowac.
Dzieki i pozdrawiam!


--
Wysłano z serwisu Usenet w portalu Gazeta.pl -> http://www.gazeta.pl/usenet/

do góry

W dniu 2012-01-30 05:42, M.M. pisze:
> Jordan Szubert<u...@j...us.to> napisał(a):
>
>> czas bedzie rzedu N+M, dodatkowa pamiec rzedu N
>> w sumie to od razu moglbys policzyc se odchylenia dla wszystkich podzialow
>
> Po tym jak Bartek przypomnial drugi wzor nie widze potrzeby uzycia
> dodatkowej pamieci. Wystarczy zapamietac sume i sume kwadratow w
> pierwszym przebiegu. W drugim przebiegu druga sume i druga sume kwadratow
> trzeba naliczac, a od pierwszych sum odejmowac.

Przeczytaj do końca, jeden przebieg wystarcza.

pzdr
bartekltg

do góry

bartekltg <b...@g...com> napisał(a):

> W dniu 2012-01-30 05:42, M.M. pisze:
> > Jordan Szubert<u...@j...us.to> napisał(a):
> >
> >> czas bedzie rzedu N+M, dodatkowa pamiec rzedu N
> >> w sumie to od razu moglbys policzyc se odchylenia dla wszystkich podzialow
> >
> > Po tym jak Bartek przypomnial drugi wzor nie widze potrzeby uzycia
> > dodatkowej pamieci. Wystarczy zapamietac sume i sume kwadratow w
> > pierwszym przebiegu. W drugim przebiegu druga sume i druga sume kwadratow
> > trzeba naliczac, a od pierwszych sum odejmowac.
>
> Przeczytaj do końca, jeden przebieg wystarcza.
Racja, mozna sumy czesciowe przechowywac w M komorkach i potem
odejmowac sumy czesciowe zamiast po jednej. Czyli czas N+M i
dodatkowa pamiec 2*M na sumy czesciowe.
Pozdrawiam


--
Wysłano z serwisu Usenet w portalu Gazeta.pl -> http://www.gazeta.pl/usenet/

do góry

Użytkownik "bartekltg" <b...@g...com> napisał w wiadomości grup
dyskusyjnych:jg57nu$6bg$...@n...news.atman.pl...
> Przeczytaj do końca, jeden przebieg wystarcza.

Brednie wypisują ci, którzy naiwnie sądzą "jeden przebieg wystarcza".

Owszem, jest więcej niż parę tuzinów podręczników, których jest podany
wzorek na odchylenie standardowe liczone przez średni kwadrat i kwadrat ze
średniej. Owszem, każdy (?) kalkulatorek tak liczy "sigmę". I nawet nie
trzeba się specjalnie starać, aby udowodnić ponad wszelką wątpliwość, że
wzorek jest "matematycznie poprawny".

Więc osocochodzi? Ano o to, że "wzorek jednoprzebiegowy" jest numerycznie
niepoprawny, tj. wystarczy podać mu spreparowane dane i wtedy zaczyna
produkować bzdury.

Weźmy ciąg (a, a+1, a+2, a+1) . Ile wynosi odchylenie standardowe poprawnie
obliczone? Najpierw liczymy średnią arytmetyczną: a+1 . Teraz tworzymy
wektor odchyleń od średniej (-1, 0, 1, 0) . Następnie liczymy ile wynosi
średnie kwadratowe odchylenie - to nietrudne, widzimy że 0.5, ale na stopień
swobody... to dzielimy nie przez 4 lecz przez 3 i wychodzi odrobinę więcej,
bo około 0.6666 . Teraz kwestia definicji - czy to ma być odchylenie w
próbie czy też odchylenie średniej? Zakładam, że to drugie - trzeba
podzielić jeszcze przez liczebność próby, tj. 4. Wychodzi około 0.1666 .
Wreszcie wyciągamy pierwiastek - tak "na oko" to jest 0.4 . Mamy wynik.

Jaki z tego morał? Bo jest w tym morał: wynik nie zależy od tego, ile
wynosiło a . Czy było równe zero, 1E+38, czy może 1.5E308 ...

Natomiast przy liczeniu od razu sumy kwadratów - błędy zaokrągleń zjedzą wam
dokładność. Sprawdźcie sami dla jakiej konkretnej wartości a wasz algorytm
polegnie.

(Zawsze opłaca się najpierw przeskalować dane - a potem dopiero robić
obliczenia statystyczne.)

do góry

> Ano o to, że "wzorek jednoprzebiegowy" jest
> numerycznie niepoprawny,

Owszem, ale nietrudno wyprowadzic jednoprzebiegowy wzor dajacy poprawny
numerycznie algorytm. A jeszcze prosciej skopiowac:
http://en.wikipedia.org/wiki/Algorithms_for_calculat
ing_variance#On-line_algorithm

> Natomiast przy liczeniu od razu sumy kwadratów - błędy zaokrągleń zjedzą
> wam dokładność. Sprawdźcie sami dla jakiej konkretnej wartości a wasz
> algorytm polegnie.

Przedzial wartosci i ich liczba byla podana. Wydaje mi sie ze dla takich
danych nawet algorytm z odejmowaniem na koncu nie powinien sie potknac.

do góry

slawek <s...@h...pl> napisał(a):

> Więc osocochodzi? Ano o to, że "wzorek jednoprzebiegowy" jest numerycznie
> niepoprawny, tj. wystarczy podać mu spreparowane dane i wtedy zaczyna
> produkować bzdury.

Wyglada na to ze na losowych danych zachowuje sie stabilnie:
http://pastebin.com/jnwSW720

Mozna zrobic troche lepiej, mozna liczyc dwie sumy. Dane powyzej biezacej
sredniej w jednej zmiennej i dane ponizej sredniej w drugiej. Jesli dane sa
tak spreparowane ze jedna liczba bedzie duza, a pozostaly milion liczby tak
maly, ze zadna nie wplynie na wynik sumy, to w drugiej zmiennej nazbiera sie
suma tych malych. Moze nazbierac sie tyle ze juz wplyna na wynik.

Pozdrawiam i dzieki za cenna uwage!


--
Wysłano z serwisu Usenet w portalu Gazeta.pl -> http://www.gazeta.pl/usenet/

do góry