Finden running median aus einem stream von ganzen zahlen

Gibt es eine Reihe von verschiedenen Lösungen für die Suche nach running median von gestreamten Daten, werde ich kurz darüber sprechen, ganz am Ende der Antwort.

Die Frage ist, über die details der eine bestimmte Lösung (max-heap/min-heap-Lösung), und wie heap-basierte Lösung funktioniert, ist unten erklärt:

Für die ersten beiden Elemente hinzufügen kleineres zum maxHeap auf der linken Seite, und der größere zu der minHeap auf der rechten Seite. Dann den Prozess Strom-Daten eins nach dem anderen,

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

Dann zu einem gegebenen Zeitpunkt können Sie berechnen den median so:

   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

Jetzt werde ich sprechen über das problem im Allgemeinen, wie versprochen, die Antwort beginnt. Suche nach running median aus einem Strom von Daten ist ein schwieriges problem, und der Suche nach einem genau die Lösung, die mit Speicher-Einschränkungen effizient ist wahrscheinlich unmöglich für den Allgemeinen Fall. Auf der anderen Seite, wenn die Daten hat einige Eigenschaften, die wir ausnutzen können, entwickeln wir für Sie effiziente Lösungen spezialisiert. Zum Beispiel, wenn wir wissen, dass die Daten ist ein integraler Typ ist, dann können wir zählen, Sortieren, das kann Ihnen eine ständige Erinnerung Konstante Zeit-Algorithmus. Heap-basierten Lösung ist eine Allgemeine Lösung, weil es kann verwendet werden, für andere Datentypen (Double) als gut. Und schließlich, wenn der genaue median ist nicht erforderlich und eine Angleichung genug ist, können Sie nur versuchen, Schätzung einer Wahrscheinlichkeits-Dichte-Funktion für die Daten und Schätzung median benutzen.

Wenn die Varianz der Eingang ist statistisch verteilt (z.B. normal -, log-normal ... usw) dann reservoir sampling ist eine sinnvolle Schätzung der Perzentile/Mediane aus einer beliebig langen Strom von zahlen.

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;
      }
  }
}

"reservoir" ist dann ein Lauf, gleichmäßige (gerechte), die Probe von allen Eingangs - unabhängig von der Größe. Das finden der median (oder jedem Perzentil) ist dann ein straight-forward Angelegenheit der Sortierung der Stausee und der Abruf der interessante Punkt.

Da das reservoir ist mit fester Größe, der Art angesehen werden können, effektiv O(1) - und diese Methode wird ausgeführt, sowohl mit konstanter Zeit-und Speicherbedarf.

Dieses problem hat eine exakte Lösung, muss nur die n zuletzt gesehen Elemente werden im Speicher gehalten. Es ist schnell und skaliert gut.

Einer Wende skiplist unterstützt O(ln n) - einfügen, entfernen, und die indizierte Suche von beliebigen Elementen, während die Aufrechterhaltung der sortierten Reihenfolge. Wenn gepaart mit einem FIFO-Warteschlange, dass die tracks, die n-te ältesten Eintrag, die Lösung ist einfach:

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]

Hier sind die links zu den kompletten funktionierenden code (ein einfach-zu-verstehen-Klasse-version und eine optimierte generator-version mit der Wende skiplist-code inlined):

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

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

Effiziente, ist ein Wort, das abhängig vom Kontext. Die Lösung für dieses problem hängt von der Anzahl der Anfragen erfolgt im Vergleich zu der Menge von Einfügungen. Angenommen, Sie sind das einfügen von N zahlen und K-mal gegen Ende waren Sie interessiert an den median. Die heap-basierten Algorithmus die Komplexität wäre O(N log N + K).

Betrachten Sie die folgende alternative. Zupfen Sie die zahlen in ein array, und für jede Abfrage, ausführen der linear-Auswahl-Algorithmus (unter Verwendung des quicksort-pivot, sagen). Jetzt haben Sie einen Algorithmus mit Laufzeit O(K N).

Nun, wenn K hinreichend klein ist (seltene Abfragen), letzterer Algorithmus ist effizienter und Umgekehrt.