Algorytmy do obliczenia działającej mediany?

W przypadku mniejszych rozmiarów okien n log nsortowanie może działać. Czy są jakieś lepsze algorytmy, aby to osiągnąć?

Zła forma sortowania tablicy w celu obliczenia mediany. Mediany (i inne kwantyle) są zazwyczaj obliczane przy użyciu algorytmu szybkiego wyboru , ze złożonością .$O(n)$

Możesz także zapoznać się z moją odpowiedzią na ostatnie powiązane pytanie tutaj .

Oto artykuł opisujący jeden z możliwych algorytmów. Zawiera kod źródłowy i dość poważną aplikację (wykrywanie fali grawitacyjnej w oparciu o interferometrię laserową), więc można oczekiwać, że będzie dobrze przetestowany.

Jeśli chcesz tolerować przybliżenie, istnieją inne metody. Na przykład jedno przybliżenie to wartość, której ranga znajduje się w pewnej (określonej przez użytkownika) odległości od prawdziwej mediany. Na przykład mediana ma (znormalizowaną) rangę 0,5, a jeśli określisz warunek błędu na poziomie 10%, potrzebujesz odpowiedzi, która ma rangę między 0,45 a 0,55.

Jeśli taka odpowiedź jest odpowiednia, istnieje wiele rozwiązań, które mogą działać na przesuwanych oknach danych. Podstawową ideą jest utrzymanie próbki danych o określonym rozmiarze (około 1 / błąd) i obliczenie mediany dla tej próbki. Można wykazać, że z dużym prawdopodobieństwem, niezależnie od charakteru danych wejściowych, uzyskana mediana spełnia wyżej wymienione właściwości.

Zatem głównym pytaniem jest, jak utrzymać bieżącą próbkę danych o określonej wielkości, i istnieje wiele podejść do tego, w tym technika znana jako pobieranie próbek ze złoża. Na przykład ten dokument: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.24.7136

Jeśli utrzymujesz okno danych o długości k jako posortowaną podwójnie połączoną listę, to za pomocą wyszukiwania binarnego (aby wstawić każdy nowy element, gdy zostanie on przesunięty do okna) i okrągłej tablicy wskaźników (aby natychmiast zlokalizować elementy, które należy usunąć), każde przesunięcie okna wymaga wysiłku O (log (k)) do wstawienia jednego elementu, tylko wysiłku O (1) do usunięcia elementu przesuniętego z okna i tylko wysiłku O (1) do znalezienia mediana (ponieważ za każdym razem, gdy jeden element jest wstawiany lub usuwany z listy, można zaktualizować wskaźnik do mediany w czasie O (1)). Całkowity wysiłek związany z przetwarzaniem tablicy o długości N wynosi zatem O ((nk) log (k)) <= O (n log (k)). Jest to lepsze niż którakolwiek z innych proponowanych dotychczas metod i nie jest to przybliżenie, jest dokładne.

Jak wspomniałeś, sortowanie będzie dotyczyło O(n·log n)okna o długości n. Wykonanie tego przeniesienia powoduje kolejne l=vectorlengthzwiększenie całkowitego kosztu O(l·n·log n).

Najprostszym sposobem, aby to zrobić, jest przechowywanie uporządkowanej listy ostatnich n elementów w pamięci podczas przechodzenia z jednego okna do następnego. Usunięcie / wstawienie jednego elementu z / do uporządkowanej listy O(n)powoduje oba koszty O(l·n).

Pseudo kod:

l = length(input)
aidvector = sort(input(1:n))
output(i) = aid(n/2)
for i = n+1:l
    remove input(i-n) from aidvector
    sort aid(n) into aidvector
    output(i) = aid(n/2)

Oto rozwiązanie O (1) do znalezienia bieżącej mediany i O (log n) do dodania nowego numeru http://www.dsalgo.com/RunningMedian.php

Jeśli możesz żyć z oszacowaniem zamiast z prawdziwą medianą, algorytm naprawczy (PDF) jest jednoprzebiegowy z niskimi wymaganiami dotyczącymi miejsca i dobrze zdefiniowaną dokładnością.

Środek zaradczy z bazą b przebiega przez obliczenie median z grup obserwacji b, a następnie median tych median, aż pozostanie tylko jedno oszacowanie. Ta metoda wymaga jedynie k tablic o rozmiarze b (gdzie n = b ^ k) ...

Korzystałem z tej biblioteki RunningStats C ++ we wbudowanej aplikacji. Jest to najprostsza biblioteka statystyk, jaką znalazłem do tej pory.

Z linku:

Kod jest rozszerzeniem metody Knutha i Welforda do obliczania odchylenia standardowego w jednym przejściu przez dane. Oblicza skośność i kurtozę również z podobnym interfejsem. Oprócz wymagania tylko jednego przejścia danych, algorytm jest stabilny numerycznie i dokładny.