Przyrostowe mediana obliczeń z maksymalną wydajnością pamięci

Question

Mam proces, który generuje wartości i które obserwuję. Kiedy proces się zakończy, chcę obliczyć medianę tych wartości.

Gdybym musiał obliczyć średnią, mógłbym po prostu zapisać sumę i liczbę wygenerowanych wartości, a tym samym mieć wymaganą pamięć O (1). A co z medianą? Czy istnieje sposób na zaoszczędzenie na oczywistym O (n) pochodzącym z przechowywania wszystkich wartości?

Edytuj: Interesują Cię 2 przypadki: 1) długość strumienia jest znana, 2) nie jest.

Answer 1

Będziesz trzeba przechowywać co najmniej ceil (n/2) punkty, ponieważ każdy jeden z pierwszych N/2 punktów może być mediana. Najprościej jest po prostu zapisać punkty i znaleźć medianę. Jeśli zapisywanie punktów ce (n/2) ma wartość, odczytywanie w pierwszych n/2 punktach na posortowaną listę (najlepiej binarne drzewo), a następnie dodawanie nowych punktów wyrzuca niskie lub wysokie punkty i zachowuje śledzenie liczby punktów na każdym z wyrzuconych końcówek.

Edit:

Jeśli długość strumień jest nieznany, to oczywiście, jak Stephen obserwowane w komentarzach, to nie mamy wyboru, ale wszystko pamiętam. Jeśli prawdopodobne jest zduplikowanie elementów, możemy ewentualnie zapisać trochę pamięci korzystając z pomysłu Dolphins na przechowywanie wartości i liczników.

Answer 2

Można

• Statystyki, jeśli jest to dopuszczalne - na przykład, można użyć próbkowanie.
• Wykorzystanie wiedzy o swoim strumieniu numer
  • stosując sortowanie przez zliczanie takiego podejścia: k odrębne wartości oznacza przechowywanie O(k) pamięci)
  • lub rzuca się znane odstających i prowadź (wysoki, niski) licznik.
  • Jeśli wiesz, że nie masz duplikatów, możesz użyć bitmapy ... ale to tylko mniejsza stała dla O(n).

Answer 3

Jeśli masz dyskretne wartości i wiele powtórzeń, możesz zapisać wartości i liczby, co zaoszczędziłoby trochę miejsca.

Ewentualnie na etapach poprzez obliczenia można wyrzucić top „n” i dolny „n” wartości, o ile jesteś pewny, że średnia nie jest w tym zakresie górze lub dole.
np. Załóżmy, że spodziewasz się 100 000 wartości. Za każdym razem, gdy twój zapisany numer trafi na (powiedzmy) 12 000, możesz odrzucić najwyższe 1000 i najniższe 1000, zmniejszając pamięć do 10.000.

Jeśli rozkład wartości jest dość spójny, to działałoby dobrze. Jednak jeśli istnieje możliwość, że pod koniec otrzymasz dużą liczbę bardzo wysokich lub bardzo niskich wartości, może to zniekształcić twoje obliczenia. Zasadniczo, jeśli odrzucisz "wysoką" wartość, która jest mniejsza niż (ewentualna) mediana lub "niska" wartość, która jest równa lub większa niż (ostateczna) mediana, twoje obliczenia są wyłączone.

Aktualizacja
Bit przykładu
Załóżmy, że zbiór danych numery 1,2,3,4,5,6,7,8,9.
Przez inspekcję mediana wynosi 5.

Załóżmy, że pierwsze 5 liczb otrzymasz 1,3,5,7,9.
Aby zaoszczędzić miejsce odrzucić najwyższy i najniższy, pozostawiając 3,5,7
teraz dostać dwa więcej, 2,6, tak nasza przechowywania jest 2,3,5,6,7
Odrzuć najwyższa i najniższa, pozostawiając 3,5,6
Zdobądź ostatnie dwa 4,8 i mamy 3,4,5,6,8
Median jest nadal 5, a świat jest dobrym miejscem.

Jednak powiedzmy, że pierwsze pięć numerów otrzymujemy są 1,2,3,4,5
Anuluj górna i dolna pozostawiając 2,3,4
Get dwa kolejne 6,7 i mamy 2, 3,4,6,7
Odrzuć górę i dół pozostawiając 3,4,6
Zdobądź ostatnie dwa 8,9, a my mamy 3,4,6,8,9
Przy medianie wynoszącej 6, która jest niepoprawna.

Jeśli nasze liczby są dobrze rozmieszczone, możemy zatrzymać przycinanie kończyn. Jeśli mogą być spakowane w dużą lub dużą liczbę małych liczb, odrzucanie jest ryzykowne.