eGospodarka.pl
eGospodarka.pl poleca

eGospodarka.plGrupypl.comp.programmingodchylenie standardowe online
Ilość wypowiedzi w tym wątku: 40

  • 1. Data: 2012-01-30 01:47:21
    Temat: odchylenie standardowe online
    Od: " M.M." <m...@N...gazeta.pl>

    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/


  • 2. Data: 2012-01-30 02:30:31
    Temat: Re: odchylenie standardowe online
    Od: "Jordan Szubert" <u...@j...us.to>

    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


  • 3. Data: 2012-01-30 02:35:00
    Temat: Re: odchylenie standardowe online
    Od: bartekltg <b...@g...com>

    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


  • 4. Data: 2012-01-30 04:27:38
    Temat: Re: odchylenie standardowe online
    Od: " M.M." <m...@g...pl>

    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/


  • 5. Data: 2012-01-30 04:42:37
    Temat: Re: odchylenie standardowe online
    Od: " M.M." <m...@g...pl>

    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/


  • 6. Data: 2012-01-30 04:53:17
    Temat: Re: odchylenie standardowe online
    Od: bartekltg <b...@g...com>

    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


  • 7. Data: 2012-01-30 05:25:51
    Temat: Re: odchylenie standardowe online
    Od: " M.M." <m...@g...pl>

    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/


  • 8. Data: 2012-02-01 16:49:18
    Temat: Re: odchylenie standardowe online
    Od: "slawek" <s...@h...pl>


    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.)


  • 9. Data: 2012-02-01 20:50:00
    Temat: Re: odchylenie standardowe online
    Od: jolz <B...@i...pl>

    > 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.


  • 10. Data: 2012-02-01 22:02:23
    Temat: Re: odchylenie standardowe online
    Od: "M.M. " <m...@g...pl>

    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/

strony : [ 1 ] . 2 ... 4


Szukaj w grupach

Szukaj w grupach

Eksperci egospodarka.pl

1 1 1

Wpisz nazwę miasta, dla którego chcesz znaleźć jednostkę ZUS.

Wzory dokumentów

Bezpłatne wzory dokumentów i formularzy.
Wyszukaj i pobierz za darmo: