Znajdź działającą medianę ze strumienia liczb całkowitych

Możliwa duplikat:
kroczący algorytm mediany w C

Biorąc pod uwagę, że liczby całkowite są odczytywane ze strumienia danych. Znajdź medianę odczytanych do tej pory elementów w efektywny sposób.

Rozwiązanie:

Po przetworzeniu elementu przychodzącego liczba elementów w stosach różni się co najwyżej o 1 element. Gdy obie hałdy zawierają tę samą liczbę elementów, znajdujemy średnią danych głównych sterty jako skuteczną medianę. Gdy hałdy nie są zrównoważone, wybieramy efektywną medianę z katalogu głównego hałdy zawierającej więcej elementów.

Ale jak skonstruowalibyśmy stertę maksymalną i stertę minimalną, tj. Skąd mielibyśmy poznać efektywną medianę? Myślę, że wstawilibyśmy 1 element do max-sterty, a następnie następny 1 element do min-sterty i tak dalej dla wszystkich elementów. Popraw mnie Jeśli się tutaj mylę.

Istnieje wiele różnych rozwiązań pozwalających znaleźć medianę z danych przesyłanych strumieniowo, krótko o nich opowiem na samym końcu odpowiedzi.

Pytanie dotyczy szczegółów konkretnego rozwiązania (maks. Sterty / min sterty), a sposób działania rozwiązania opartego na sterty wyjaśniono poniżej:

Dla pierwszych dwóch elementów dodaj mniejszy jeden do maxHeap po lewej stronie, a większy do minHeap po prawej stronie. Następnie przetwarzaj strumień danych jeden po drugim,

Step 1: Add next item to one of the heaps

   if next item is smaller than maxHeap root add it to maxHeap,
   else add it to minHeap

Step 2: Balance the heaps (after this step heaps will be either balanced or
   one of them will contain 1 more item)

   if number of elements in one of the heaps is greater than the other by
   more than 1, remove the root element from the one containing more elements and
   add to the other one

Następnie w dowolnym momencie możesz obliczyć medianę w następujący sposób:

   If the heaps contain equal amount of elements;
     median = (root of maxHeap + root of minHeap)/2
   Else
     median = root of the heap with more elements

Teraz omówię ogólnie problem, jak obiecano na początku odpowiedzi. Znalezienie uruchomionej mediany ze strumienia danych jest trudnym problemem, a skuteczne znalezienie dokładnego rozwiązania z ograniczeniami pamięci prawdopodobnie nie jest możliwe w ogólnym przypadku. Z drugiej strony, jeśli dane mają pewne cechy, które możemy wykorzystać, możemy opracować wydajne specjalistyczne rozwiązania. Na przykład, jeśli wiemy, że dane są typem integralnym, możemy zastosować sortowanie według liczenia, co może zapewnić stały algorytm stałej pamięci czasu. Rozwiązanie oparte na stertach jest rozwiązaniem bardziej ogólnym, ponieważ można go również stosować do innych typów danych (podwójnych). I na koniec, jeśli dokładna mediana nie jest wymagana i wystarczy przybliżenie, możesz po prostu spróbować oszacować funkcję gęstości prawdopodobieństwa dla danych i oszacować medianę za pomocą tego.

Jeśli nie możesz zatrzymać wszystkich elementów jednocześnie, problem staje się znacznie trudniejszy. Rozwiązanie sterty wymaga jednoczesnego przechowywania wszystkich elementów w pamięci. Nie jest to możliwe w większości rzeczywistych zastosowań tego problemu.

Zamiast tego, jak widać numery, śledzić zliczania liczby czasów widać każdą liczbę całkowitą. Zakładając 4 bajty liczb całkowitych, to 2 ^ 32 segmentów lub co najwyżej 2 ^ 33 liczb całkowitych (klucz i liczba dla każdej liczby całkowitej), czyli 2 ^ 35 bajtów lub 32 GB. Prawdopodobnie będzie znacznie mniej niż to, ponieważ nie musisz przechowywać klucza ani liczyć dla tych wpisów, które są 0 (tj. Jak defaultdict w python). Wstawianie każdej nowej liczby całkowitej zajmuje cały czas.

Następnie w dowolnym momencie, aby znaleźć medianę, wystarczy użyć liczb, aby określić, która liczba całkowita jest środkowym elementem. Zajmuje to stały czas (choć duża stała, ale jednak stała).

Jeśli wariancja danych wejściowych jest statystycznie rozłożona (np. Normalna, log-normalna itp.), Wówczas próbkowanie w zbiorniku jest rozsądnym sposobem oszacowania percentyli / median na podstawie arbitralnie długiego strumienia liczb.

int n = 0;  // Running count of elements observed so far  
#define SIZE 10000
int reservoir[SIZE];  

while(streamHasData())
{
  int x = readNumberFromStream();

  if (n < SIZE)
  {
       reservoir[n++] = x;
  }         
  else 
  {
      int p = random(++n); // Choose a random number 0 >= p < n
      if (p < SIZE)
      {
           reservoir[p] = x;
      }
  }
}

„zbiornik” jest wówczas ciągłą, jednolitą (uczciwą) próbką wszystkich danych wejściowych - niezależnie od wielkości. Znalezienie mediany (lub dowolnego percentyla) jest wtedy prostą sprawą sortowania zbiornika i odpytywania interesującego punktu.

Ponieważ zbiornik ma stały rozmiar, sortowanie można uznać za efektywnie O (1) - i ta metoda działa zarówno przy stałym zużyciu czasu, jak i pamięci.

Najbardziej skutecznym sposobem obliczenia percentyla strumienia, który znalazłem, jest algorytm P²: Raj Jain, Imrich Chlamtac: Algorytm P² do dynamicznego obliczania kwantyli i histogramów bez przechowywania obserwacji. Commun ACM 28 (10): 1076-1085 (1985)

Algorytm jest prosty do wdrożenia i działa wyjątkowo dobrze. Jest to jednak szacunek, więc miej to na uwadze. Z streszczenia:

Algorytm heurystyczny jest proponowany do obliczeń dynamicznych q mediany i innych kwantyli. Szacunki są tworzone dynamicznie w miarę generowania obserwacji. Obserwacje nie są przechowywane; dlatego algorytm ma bardzo małe i stałe wymagania dotyczące przechowywania, niezależnie od liczby obserwacji. To sprawia, że ​​idealnie nadaje się do implementacji w chipie kwantowym, który może być wykorzystywany w kontrolerach przemysłowych i rejestratorach. Algorytm został rozszerzony na wykres histogramu. Dokładność algorytmu jest analizowana.

Jeśli chcemy znaleźć medianę n ostatnio widzianych elementów, problem ten ma dokładne rozwiązanie, które potrzebuje tylko n ostatnio widzianych elementów do zachowania w pamięci. Jest szybki i dobrze się skaluje.

An wieloostrzowe skiplist podpory O (ln n) wstawianie, usuwanie, a indeksowane wyszukiwania dowolnych elementów, przy utrzymaniu ich kolejność. W połączeniu z kolejką FIFO, która śledzi n-ty najstarszy wpis, rozwiązanie jest proste:

class RunningMedian:
    'Fast running median with O(lg n) updates where n is the window size'

    def __init__(self, n, iterable):
        self.it = iter(iterable)
        self.queue = deque(islice(self.it, n))
        self.skiplist = IndexableSkiplist(n)
        for elem in self.queue:
            self.skiplist.insert(elem)

    def __iter__(self):
        queue = self.queue
        skiplist = self.skiplist
        midpoint = len(queue) // 2
        yield skiplist[midpoint]
        for newelem in self.it:
            oldelem = queue.popleft()
            skiplist.remove(oldelem)
            queue.append(newelem)
            skiplist.insert(newelem)
            yield skiplist[midpoint]

Oto linki do kompletnego działającego kodu (łatwa do zrozumienia wersja klasy i zoptymalizowana wersja generatora z wbudowanym indeksowanym kodem skiplist):

• http://code.activestate.com/recipes/576930-efficient-running-median-using-an-indexable-skipli/

• http://code.activestate.com/recipes/577073 .

Intuicyjny sposób myślenia o tym jest taki, że gdybyś miał w pełni zrównoważone drzewo wyszukiwania binarnego, to pierwiastek byłby elementem mediany, ponieważ byłaby taka sama liczba mniejszych i większych elementów. Teraz, jeśli drzewo nie jest pełne, nie będzie tak wcale, ponieważ na ostatnim poziomie będą brakować elementów.

Zamiast tego możemy zamiast tego mieć medianę i dwa zrównoważone drzewa binarne, jedno dla elementów mniejszych niż mediana i jedno dla elementów większych niż mediana. Dwa drzewa muszą być utrzymywane w tym samym rozmiarze.

Kiedy otrzymujemy nową liczbę całkowitą ze strumienia danych, porównujemy ją do mediany. Jeśli jest większa niż mediana, dodajemy ją do odpowiedniego drzewa. Jeśli dwa rozmiary drzew różnią się więcej niż 1, usuwamy element min prawego drzewa, zmieniamy go w nową medianę i umieszczamy starą medianę w lewym drzewie. Podobnie dla mniejszych.

Skuteczne to słowo, które zależy od kontekstu. Rozwiązanie tego problemu zależy od liczby wykonanych zapytań w stosunku do liczby wstawień. Załóżmy, że wstawiasz N liczb i razy K pod koniec, że interesowała Cię mediana. Złożoność algorytmu sterta byłaby O (N log N + K).

Rozważ następującą alternatywę. Umieść liczby w tablicy i dla każdego zapytania uruchom algorytm selekcji liniowej (powiedzmy, używając osi przestawnej Quicksort). Teraz masz algorytm z czasem działania O (KN).

Teraz, gdy K jest wystarczająco małe (rzadkie zapytania), ten ostatni algorytm jest faktycznie bardziej wydajny i na odwrót.

Nie możesz tego zrobić za pomocą tylko jednego sterty? Aktualizacja: nie. Zobacz komentarz.

Niezmiennik: po odczytaniu 2*ndanych wejściowych miniparfa zawiera nnajwiększą z nich.

Pętla: odczyt 2 wejść. Dodaj je oba do sterty i usuń min. Sterty. To przywraca niezmiennik.

Więc po 2nodczytaniu danych wejściowych min. Sterty jest n-tym największym. Trzeba będzie trochę dodatkowej komplikacji, aby uśrednić dwa elementy wokół pozycji środkowej i obsługiwać zapytania po nieparzystej liczbie danych wejściowych.