Medianę da się w ogóle mierzyć w taki uproszczony sposób (albo w przybliżeniu jakimś), że mam tylko z 3-6 liczb do niej?
#programowanie #matematyka #statystyka
What you are looking for is an "online" algorithm to compute the median in constant space, and I don't think an exact one exists. There are approximate algorithms, and if you know the kind of values you are expecting (for instance if the inputs are a finite set of integers) you could get a good answer by counting occurrences. As for your histogram idea, you could always use a cheap solution (like keeping a short list of values, and using an O(n) median-finding algorithm when required) and then switch to a histogram once there is enough data.
If you can't hold all the items in memory at once, this problem becomes much harder. The heap solution requires you to hold all the elements in memory at once. This is not possible in most real world applications of this problem.
Instead, as you see numbers, keep track of the count of the number of times you see each integer. Assuming 4 byte integers, that's 2^32 buckets, or at most 2^33 integers (key and count for each int), which is 2^35 bytes or 32GB. It will likely be much less than this because you don't need to store the key or count for those entries that are 0 (ie. like a defaultdict in python). This takes constant time to insert each new integer.
Then at any point, to find the median, just use the counts to determine which integer is the middle element. This takes constant time (albeit a large constant, but constant nonetheless).
To w sumie jest manageable jak są trzymane w ryzach inty tylko.
jaką masz skalę ocen? może wystarczy zliczać liczbę ocen danej wartości?
@Deykun No, to teraz podaj średnią dobową temperaturę powietrza.
@UncleFester
Nadal możesz to zrobić z 2 liczbami jeśli aktualizacje masz co stały określony czas. Imho to nie jest problem, akurat to jest coś co na starcie ma błąd pomiarowy więc próbkowanie i strategię tylko pozwalają go minimalizować.
@Deykun
Mój poprzedni wpis był trochę prowokacyjny.
Z problemem zetknąłem się przy obliczaniu SAT (sumy średnich dziennych temperatur).
Używa się tu średniej (T max + T min) / 2
Przykładowe inne średnie stosowane w meteorologii (IMGW):
- M1 = (t00 + t01 + t02 + … + t23) / 24;
- M2 = (Tmax + Tmin) / 2;
- M3 = (t00 + t03 + t06 + t09 + t12 + t15 + t18 + t21) / 8;
- M4 = (t00 + t06 + t12 + t18) / 4;
- M5 = (T06 + T12 + 2·T20) / 4;
- M6 = (Tmax + Tmin + T06 + T18) / 4;
I bądź tu mądry.
Odpowiedź od @5tgbnhy6 chyba najprostsza, chociaż chyba lepiej znana jako counting sort - https://en.m.wikipedia.org/wiki/Counting_sort pozwala sortować inty liniowo
Alternatywnie możesz próbować jakichś cudów z BST - https://en.m.wikipedia.org/wiki/Self-balancing_binary_search_tree intuicyjnie wydaje mi się, że trzymając wysokość poddrzewa mógłbyś wyliczyć medianę w czasie logarytmicznym, ale to tylko moja intuicja i może być z dupy. Dodatkowo dużo trudniejsza w implementacji więc zależy od usecase - jeśli to nie zadanie na studia a życiowe, to pewnie nie warto.
Zaloguj się aby komentować