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

223

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ę.

Luv
źródło
10
Sprytny algorytm z wykorzystaniem hałd. Z tytułu nie mogłem od razu wymyślić rozwiązania.
Mooing Duck
1
rozwiązanie wezyra wygląda dla mnie dobrze, poza tym, że zakładałem (choć nie powiedziałeś), że ten strumień może być dowolnie długi, więc nie możesz zachować wszystkiego w pamięci. Czy tak jest w przypadku?
Dzikie
2
@RunningWild W przypadku dowolnie długich strumieni można uzyskać medianę ostatnich N elementów, używając stert Fibonacciego (aby uzyskać log (N) kasuje) i przechowując wskaźniki do wstawianych elementów w kolejności (np. Deque), a następnie usuwając najstarsze element na każdym kroku, gdy stosy są pełne (być może także przenoszenie rzeczy z jednego stosu na drugi). Możesz uzyskać coś lepszego niż N, przechowując liczbę powtarzających się elementów (jeśli jest wiele powtórzeń), ale ogólnie myślę, że musisz przyjąć jakieś założenia dystrybucyjne, jeśli chcesz mediany całego strumienia.
Dougal
2
Możesz zacząć od obu stosów pustych. Pierwsza int idzie w jednym stosie; drugi idzie albo w drugim, albo przenosisz pierwszy element na drugą stertę, a następnie wstawiasz. Uogólnia to: „nie zezwalaj, aby jedna sterty była większa niż druga +1” i nie jest wymagana specjalna obudowa („wartość korzenia” pustej sterty można zdefiniować jako 0)
Jon Watte
Po prostu dostałem to pytanie w wywiadzie MSFT. Dziękujemy za przesłanie
R Claven,

Odpowiedzi:

383

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.

Hakan Serce
źródło
6
Te hałdy rosną bez ograniczeń (tzn. Okno 100 elementów przesuwające się ponad 10 milionów elementów wymagałoby przechowywania 10 milionów elementów w pamięci). Zobacz poniżej inną odpowiedź przy użyciu indeksowanych list przewozowych, która wymaga tylko 100 ostatnio przechowywanych elementów w pamięci.
Raymond Hettinger
1
Możesz mieć ograniczone rozwiązanie pamięci za pomocą stosów, jak wyjaśniono w jednym z komentarzy do samego pytania.
Hakan Serce
1
Implementację rozwiązania opartego na sterty można znaleźć tutaj.
Ahelly
1
Wow, pomogło mi to nie tylko rozwiązać ten konkretny problem, ale także pomogło mi nauczyć się stosów, oto moja podstawowa implementacja w pythonie: github.com/PythonAlgo/DataStruct
swati saoji
2
@HakanSerce Czy możesz wyjaśnić, dlaczego zrobiliśmy to, co zrobiliśmy? Mam na myśli, że widzę, jak to działa, ale nie jestem w stanie zrozumieć tego intuicyjnie.
shiva
51

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).

Andrew C.
źródło
3
Jeśli prawie wszystkie liczby są widoczne raz, rzadka lista zajmie jeszcze więcej pamięci. I wydaje się raczej prawdopodobne, że jeśli masz tak wiele liczb, nie pasują one do liczby, że większość liczb pojawi się raz. Mimo to jest to sprytne rozwiązanie dla ogromnej liczby liczb.
Mooing Duck
1
Zgadzam się, że w przypadku rzadkiej listy jest to gorsze pod względem pamięci. Chociaż liczby całkowite są losowo rozmieszczone, duplikaty zaczniesz dużo szybciej, niż sugeruje to intuicja. Zobacz mathworld.wolfram.com/BirthdayProblem.html . Jestem więc prawie pewien, że stanie się to skuteczne, gdy tylko pojawi się kilka GB danych.
Andrew C
4
@AndrewC możesz wyjaśnić, w jaki sposób znalezienie mediany zajmie ciągły czas. Jeśli widziałem n różnych liczb całkowitych, to w najgorszym przypadku ostatnim elementem może być mediana. To sprawia, że ​​mediana znalezienia aktywności O (n).
shshnk
@shshnk Czy n nie jest całkowitą liczbą elementów, która w tym przypadku wynosi >>> 2 ^ 35?
VishAmdi,
@shshnk Masz rację, że nadal jest liniowa w liczbie różnych liczb całkowitych, które widziałeś, jak powiedział VishAmdi, zakładam, że dla tego rozwiązania zakładam, że n to liczba liczb, które widziałeś, co jest znacznie większy niż 2 ^ 33. Jeśli nie widzisz tak wielu liczb, rozwiązanie maxheap jest zdecydowanie lepsze.
Andrew C
49

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.

Colm MacCárthaigh
źródło
z ciekawości, dlaczego potrzebujesz wariancji?
LazyCat
Strumień może zwrócić mniej niż elementy SIZE, co spowoduje, że zbiornik będzie w połowie pusty. Należy wziąć to pod uwagę przy obliczaniu mediany.
Alex
Czy istnieje sposób, aby to przyspieszyć, obliczając różnicę zamiast mediany? Czy usunięta i dodana próbka oraz poprzednia mediana wystarczają do tego?
inf3rno
30

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.

Hellblazer
źródło
2
Szkic Count-Min jest lepszy niż P ^ 2, ponieważ daje również błąd związany, podczas gdy ten drugi nie.
sinoTrinity,
1
Weź również pod uwagę „Energooszczędne obliczanie online podsumowań kwantowych” autorstwa Greenwalda i Khanny, która również określa granice błędów i ma dobre wymagania dotyczące pamięci.
Paul Chernoch
1
Ponadto, jeśli chodzi o podejście probabilistyczne, zobacz ten post na blogu: research.neustar.biz/2013/09/16/…, a dokument, do którego się odnosi, znajduje się tutaj: arxiv.org/pdf/1407.1121v1.pdf Nazywa się to „Frugal” Streaming ”
Paul Chernoch
27

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):

Raymond Hettinger
źródło
7
Jeśli jednak dobrze to rozumiem, daje to tylko medianę z ostatnich N widocznych elementów, a nie wszystkich elementów do tego momentu. Wydaje się to jednak naprawdę sprytnym rozwiązaniem dla tej operacji.
Andrew C
16
Dobrze. Odpowiedź brzmi tak, jakby można było znaleźć medianę wszystkich elementów, po prostu zachowując ostatnie n elementów w pamięci - to w ogóle niemożliwe. Algorytm właśnie znajduje medianę ostatnich n elementów.
Hans-Peter Störr
8
Termin „działająca mediana” jest zwykle używany w odniesieniu do mediany podzbioru danych. OP stosuje się w powszechnym znaczeniu w niestandardowy sposób.
Rachel Hettinger
18

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.

Irene Papakonstantinou
źródło
Jak masz zamiar to zrobić? „usuwamy minimalny element prawego drzewa”
Hengameh
2
Miałem na myśli binarne drzewa wyszukiwania, więc element min jest całkowicie od korzenia.
Irene Papakonstantinou
7

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.

Piotr jest
źródło
1
W przykładzie stosu wyszukiwanie jest czasem stałym, więc myślę, że powinno to być O (N log N + K), ale twój punkt nadal obowiązuje.
Andrew C
Tak, dobra uwaga, wyedytuję to. Masz rację N log N jest nadal terminem wiodącym.
Peteris
-2

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.

Darius Bacon
źródło
1
Nie działa: możesz upuścić rzeczy, które później okażą się blisko szczytu. Na przykład wypróbuj algorytm z liczbami od 1 do 100, ale w odwrotnej kolejności: 100, 99, ..., 1.
zellyn
Dzięki, Zellyn. Głupie z mojej strony, by przekonać się, że niezmiennik został przywrócony.
Darius Bacon