-
Data: 2012-01-30 02:35:00
Temat: Re: odchylenie standardowe online
Od: bartekltg <b...@g...com> szukaj wiadomości tego autora
[ pokaż wszystkie nagłówki ]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
Następne wpisy z tego wątku
- 30.01.12 02:30 Jordan Szubert
- 30.01.12 04:27 M.M.
- 30.01.12 04:42 M.M.
- 30.01.12 04:53 bartekltg
- 30.01.12 05:25 M.M.
- 01.02.12 16:49 slawek
- 01.02.12 20:50 jolz
- 01.02.12 22:02 M.M.
- 01.02.12 23:54 bartekltg
- 02.02.12 18:17 slawek
- 02.02.12 18:23 slawek
- 02.02.12 22:00 M.M.
- 03.02.12 09:43 bartekltg
- 03.02.12 09:54 M.M.
- 03.02.12 10:19 bartekltg
Najnowsze wątki z tej grupy
- TCL - problem z escape ostatniego \ w nawiasach {}
- Nauka i Praca Programisty C++ w III Rzeczy (pospolitej)
- testy-wyd-sort - Podsumowanie
- Tworzenie Programów Nieuprzywilejowanych Opartych Na Wtyczkach
- Do czego nadaje się QDockWidget z bibl. Qt?
- Bibl. Qt jest sztucznie ograniczona - jest nieprzydatna do celów komercyjnych
- Co sciaga kretynow
- AEiC 2024 - Ada-Europe conference - Deadlines Approaching
- Jakie są dobre zasady programowania programów opartych na wtyczkach?
- sprawdzanie słów kluczowych dot. zła
- Re: W czym sie teraz pisze programy??
- Re: (PDF) Surgical Pathology of Non-neoplastic Gastrointestinal Diseases by Lizhi Zhang
- CfC 28th Ada-Europe Int. Conf. Reliable Software Technologies
- Młodzi programiści i tajna policja
- Ada 2022 Language Reference Manual to be Published by Springer
Najnowsze wątki
- 2024-10-22 za tik-toka
- 2024-10-22 Wciskania elektryków na siłę ciąg dalszy :(
- 2024-10-22 Wymarzony świat ev hejterów
- 2024-10-21 Autobus,, skuter czy Twizy
- 2024-10-21 Problem elektryków rozwiązany.
- 2024-10-21 Drukowanie bezprzewodowe - jaki interface ?
- 2024-10-22 Środa Wielkopolska => Konsultant SAP <=
- 2024-10-22 Poznań => International freight forwarder <=
- 2024-10-21 Kraków => Spedytor międzynarodowy <=
- 2024-10-21 Błonie => Sales Specialist <=
- 2024-10-21 Gdańsk => Full Stack web developer (obszar .Net Core, Angular6+) <=
- 2024-10-21 Kraków => Programista Full Stack (.Net Core) <=
- 2024-10-21 Zielona Góra => Power Electronics R&D Engineer <=
- 2024-10-21 Warszawa => Junior New Business Development Manager <=
- 2024-10-21 Gdynia => Spedytor Międzynarodowy Morski/Intermodalny <=