Rollender Median-Algorithmus in C.

Ich arbeite derzeit an einem Algorithmus zur Implementierung eines rollierenden Medianfilters (analog zu einem rollierenden Mittelwertfilter) in C. Aus meiner Literaturrecherche geht hervor, dass es zwei einigermaßen effiziente Möglichkeiten gibt, dies zu tun. Das erste besteht darin, das anfängliche Wertefenster zu sortieren und dann eine binäre Suche durchzuführen, um den neuen Wert einzufügen und den vorhandenen bei jeder Iteration zu entfernen.

Die zweite (von Hardle und Steiger, 1995, JRSS-C, Algorithmus 296) baut eine doppelendige Heap-Struktur auf, mit einem Maxheap an einem Ende, einem Minheap am anderen und dem Median in der Mitte. Dies ergibt einen linearen Zeitalgorithmus anstelle eines Algorithmus, der O (n log n) ist.

Hier ist mein Problem: Die Implementierung des ersteren ist machbar, aber ich muss dies auf Millionen von Zeitreihen ausführen, daher ist Effizienz sehr wichtig. Letzteres erweist sich als sehr schwierig umzusetzen. Ich habe Code in der Datei Trunmed.c des Codes für das Statistikpaket von R gefunden, aber er ist ziemlich nicht zu entziffern.

Kennt jemand eine gut geschriebene C-Implementierung für den linearen zeitlich rollierenden Medianalgorithmus?

Bearbeiten: Link zum Trunmed.c-Code http://google.com/codesearch/p?hl=de&sa=N&cd=1&ct=rc#mYw3h_Lb_e0/R-2.2.0/src/library/stats/src/Trunmed.c

Ich habe mir R's src/library/stats/src/Trunmed.cein paar Mal angesehen, da ich auch etwas Ähnliches in einer eigenständigen C ++ - Klasse / C-Subroutine haben wollte. Beachten Sie, dass dies tatsächlich zwei Implementierungen in einer sind (siehe src/library/stats/man/runmed.RdQuelle der Hilfedatei)

\details{
  Apart from the end values, the result \code{y = runmed(x, k)} simply has
  \code{y[j] = median(x[(j-k2):(j+k2)])} (k = 2*k2+1), computed very
  efficiently.

  The two algorithms are internally entirely different:
  \describe{
    \item{"Turlach"}{is the Härdle-Steiger
      algorithm (see Ref.) as implemented by Berwin Turlach.
      A tree algorithm is used, ensuring performance \eqn{O(n \log
        k)}{O(n * log(k))} where \code{n <- length(x)} which is
      asymptotically optimal.}
    \item{"Stuetzle"}{is the (older) Stuetzle-Friedman implementation
      which makes use of median \emph{updating} when one observation
      enters and one leaves the smoothing window.  While this performs as
      \eqn{O(n \times k)}{O(n * k)} which is slower asymptotically, it is
      considerably faster for small \eqn{k} or \eqn{n}.}
  }
}

Es wäre schön zu sehen, dass dies eigenständiger wiederverwendet wird. Machst du Freiwilligenarbeit? Ich kann mit einigen der R-Bits helfen.

Edit 1 : Neben dem Link zur älteren Version von Trunmed.c oben sind hier aktuelle SVN-Kopien von

• Srunmed.c (für die Stuetzle-Version)
• Trunmed.c (für die Turlach-Version)
• runmed.R für die R-Funktion, die diese aufruft

Edit 2 : Ryan Tibshirani hat einen C- und Fortran-Code für schnelles Median-Binning, der ein geeigneter Ausgangspunkt für einen Ansatz mit Fenster sein kann.

Ich konnte keine moderne Implementierung einer C ++ - Datenstruktur mit Ordnungsstatistik finden, sodass beide Ideen in dem von MAK vorgeschlagenen Link für Top-Codierer implementiert wurden ( Match Editorial : Scrollen Sie nach unten zu FloatingMedian).

Zwei Multisets

Die erste Idee unterteilt die Daten in zwei Datenstrukturen (Heaps, Multisets usw.) mit O (ln N) pro Einfügen / Löschen, sodass das Quantil nicht ohne große Kosten dynamisch geändert werden kann. Das heißt, wir können einen rollierenden Median oder einen rollierenden 75% haben, aber nicht beide gleichzeitig.

Segmentbaum

Die zweite Idee verwendet einen Segmentbaum, der O (ln N) für Einfügen / Löschen / Abfragen ist, aber flexibler ist. Das Beste von allem ist, dass "N" die Größe Ihres Datenbereichs ist. Wenn Ihr rollierender Median ein Fenster von einer Million Elementen hat, Ihre Daten jedoch von 1..65536 abweichen, sind nur 16 Operationen pro Bewegung des rollenden Fensters von 1 Million erforderlich !!

Der c ++ - Code ähnelt dem, was Denis oben gepostet hat ("Hier ist ein einfacher Algorithmus für quantisierte Daten").

Statistische Bäume der GNU-Ordnung

Kurz bevor ich aufgab, stellte ich fest, dass stdlibc ++ Ordnungsstatistikbäume enthält !!!

Diese haben zwei kritische Operationen:

iter = tree.find_by_order(value)
order = tree.order_of_key(value)

Siehe libstdc ++ Handbuch policy_based_data_structures_test (Suche nach "split and join").

Ich habe den Baum zur Verwendung in einen praktischen Header für Compiler eingeschlossen, die partielle Typedefs im Stil von c ++ 0x / c ++ 11 unterstützen:

#if !defined(GNU_ORDER_STATISTIC_SET_H)
#define GNU_ORDER_STATISTIC_SET_H
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

// A red-black tree table storing ints and their order
// statistics. Note that since the tree uses
// tree_order_statistics_node_update as its update policy, then it
// includes its methods by_order and order_of_key.
template <typename T>
using t_order_statistic_set = __gnu_pbds::tree<
                                  T,
                                  __gnu_pbds::null_type,
                                  std::less<T>,
                                  __gnu_pbds::rb_tree_tag,
                                  // This policy updates nodes'  metadata for order statistics.
                                  __gnu_pbds::tree_order_statistics_node_update>;

#endif //GNU_ORDER_STATISTIC_SET_H

Ich habe eine getan C - Implementierung hier . Einige weitere Details finden Sie in dieser Frage: Rollender Median in der C-Turlach-Implementierung .

Beispielnutzung:

int main(int argc, char* argv[])
{
   int i,v;
   Mediator* m = MediatorNew(15);

   for (i=0;i<30;i++)
   {
      v = rand()&127;
      printf("Inserting %3d \n",v);
      MediatorInsert(m,v);
      v=MediatorMedian(m);
      printf("Median = %3d.\n\n",v);
      ShowTree(m);
   }
}

Ich verwende diesen inkrementellen Medianschätzer:

median += eta * sgn(sample - median)

welches die gleiche Form hat wie der allgemeinere Mittelwertschätzer:

mean += eta * (sample - mean)

Hier ist eta ein kleiner Lernratenparameter (z. B. 0.001) und sgn()die Signumfunktion, die einen von zurückgibt {-1, 0, 1}. (Verwenden Sie eine Konstante etawie diese, wenn die Daten nicht stationär sind und Sie Änderungen im Laufe der Zeit verfolgen möchten. Andernfalls verwenden Sie für stationäre Quellen eine Art eta = 1 / nKonvergenz, bei der ndie Anzahl der bisher gesehenen Proben angegeben ist.)

Außerdem habe ich den Medianschätzer so geändert, dass er für beliebige Quantile funktioniert. Im Allgemeinen gibt eine Quantilfunktion den Wert an, der die Daten in zwei Brüche unterteilt: pund 1 - p. Im Folgenden wird dieser Wert schrittweise geschätzt:

quantile += eta * (sgn(sample - quantile) + 2.0 * p - 1.0)

Der Wert psollte innerhalb liegen [0, 1]. Dies verschiebt im Wesentlichen die sgn()symmetrische Ausgabe der Funktion, {-1, 0, 1}um sich zu einer Seite zu neigen, wobei die Datenproben in zwei ungleich große Bins aufgeteilt werden (Brüche pund 1 - pDaten sind kleiner als / größer als die Quantilschätzung). Beachten Sie, dass sich p = 0.5dies auf den Medianschätzer reduziert.

Hier ist ein einfacher Algorithmus für quantisierte Daten (Monate später):

""" median1.py: moving median 1d for quantized, e.g. 8-bit data

Method: cache the median, so that wider windows are faster.
    The code is simple -- no heaps, no trees.

Keywords: median filter, moving median, running median, numpy, scipy

See Perreault + Hebert, Median Filtering in Constant Time, 2007,
    http://nomis80.org/ctmf.html: nice 6-page paper and C code,
    mainly for 2d images

Example:
    y = medians( x, window=window, nlevel=nlevel )
    uses:
    med = Median1( nlevel, window, counts=np.bincount( x[0:window] ))
    med.addsub( +, - )  -- see the picture in Perreault
    m = med.median()  -- using cached m, summ

How it works:
    picture nlevel=8, window=3 -- 3 1s in an array of 8 counters:
        counts: . 1 . . 1 . 1 .
        sums:   0 1 1 1 2 2 3 3
                        ^ sums[3] < 2 <= sums[4] <=> median 4
        addsub( 0, 1 )  m, summ stay the same
        addsub( 5, 1 )  slide right
        addsub( 5, 6 )  slide left

Updating `counts` in an `addsub` is trivial, updating `sums` is not.
But we can cache the previous median `m` and the sum to m `summ`.
The less often the median changes, the faster;
so fewer levels or *wider* windows are faster.
(Like any cache, run time varies a lot, depending on the input.)

See also:
    scipy.signal.medfilt -- runtime roughly ~ window size
    http://stackoverflow.com/questions/1309263/rolling-median-algorithm-in-c

"""

from __future__ import division
import numpy as np  # bincount, pad0

__date__ = "2009-10-27 oct"
__author_email__ = "denis-bz-py at t-online dot de"


#...............................................................................
class Median1:
    """ moving median 1d for quantized, e.g. 8-bit data """

    def __init__( s, nlevel, window, counts ):
        s.nlevel = nlevel  # >= len(counts)
        s.window = window  # == sum(counts)
        s.half = (window // 2) + 1  # odd or even
        s.setcounts( counts )

    def median( s ):
        """ step up or down until sum cnt to m-1 < half <= sum to m """
        if s.summ - s.cnt[s.m] < s.half <= s.summ:
            return s.m
        j, sumj = s.m, s.summ
        if sumj <= s.half:
            while j < s.nlevel - 1:
                j += 1
                sumj += s.cnt[j]
                # print "j sumj:", j, sumj
                if sumj - s.cnt[j] < s.half <= sumj:  break
        else:
            while j > 0:
                sumj -= s.cnt[j]
                j -= 1
                # print "j sumj:", j, sumj
                if sumj - s.cnt[j] < s.half <= sumj:  break
        s.m, s.summ = j, sumj
        return s.m

    def addsub( s, add, sub ):
        s.cnt[add] += 1
        s.cnt[sub] -= 1
        assert s.cnt[sub] >= 0, (add, sub)
        if add <= s.m:
            s.summ += 1
        if sub <= s.m:
            s.summ -= 1

    def setcounts( s, counts ):
        assert len(counts) <= s.nlevel, (len(counts), s.nlevel)
        if len(counts) < s.nlevel:
            counts = pad0__( counts, s.nlevel )  # numpy array / list
        sumcounts = sum(counts)
        assert sumcounts == s.window, (sumcounts, s.window)
        s.cnt = counts
        s.slowmedian()

    def slowmedian( s ):
        j, sumj = -1, 0
        while sumj < s.half:
            j += 1
            sumj += s.cnt[j]
        s.m, s.summ = j, sumj

    def __str__( s ):
        return ("median %d: " % s.m) + \
            "".join([ (" ." if c == 0 else "%2d" % c) for c in s.cnt ])

#...............................................................................
def medianfilter( x, window, nlevel=256 ):
    """ moving medians, y[j] = median( x[j:j+window] )
        -> a shorter list, len(y) = len(x) - window + 1
    """
    assert len(x) >= window, (len(x), window)
    # np.clip( x, 0, nlevel-1, out=x )
        # cf http://scipy.org/Cookbook/Rebinning
    cnt = np.bincount( x[0:window] )
    med = Median1( nlevel=nlevel, window=window, counts=cnt )
    y = (len(x) - window + 1) * [0]
    y[0] = med.median()
    for j in xrange( len(x) - window ):
        med.addsub( x[j+window], x[j] )
        y[j+1] = med.median()
    return y  # list
    # return np.array( y )

def pad0__( x, tolen ):
    """ pad x with 0 s, numpy array or list """
    n = tolen - len(x)
    if n > 0:
        try:
            x = np.r_[ x, np.zeros( n, dtype=x[0].dtype )]
        except NameError:
            x += n * [0]
    return x

#...............................................................................
if __name__ == "__main__":
    Len = 10000
    window = 3
    nlevel = 256
    period = 100

    np.set_printoptions( 2, threshold=100, edgeitems=10 )
    # print medians( np.arange(3), 3 )

    sinwave = (np.sin( 2 * np.pi * np.arange(Len) / period )
        + 1) * (nlevel-1) / 2
    x = np.asarray( sinwave, int )
    print "x:", x
    for window in ( 3, 31, 63, 127, 255 ):
        if window > Len:  continue
        print "medianfilter: Len=%d window=%d nlevel=%d:" % (Len, window, nlevel)
            y = medianfilter( x, window=window, nlevel=nlevel )
        print np.array( y )

# end median1.py

Der rollierende Median kann ermittelt werden, indem zwei Partitionen von Zahlen beibehalten werden.

Verwenden Sie zum Verwalten von Partitionen Min Heap und Max Heap.

Max Heap enthält Zahlen, die kleiner als der Median sind.

Min Heap enthält Zahlen, die größer als der Median sind.

Ausgleichsbeschränkung: Wenn die Gesamtzahl der Elemente gerade ist, sollten beide Heaps gleiche Elemente haben.

Wenn die Gesamtzahl der Elemente ungerade ist, hat Max Heap ein Element mehr als Min Heap.

Medianelement: Wenn beide Partitionen die gleiche Anzahl von Elementen haben, ist der Median die Hälfte der Summe aus dem maximalen Element der ersten Partition und dem minimalen Element der zweiten Partition.

Andernfalls ist der Median das maximale Element der ersten Partition.

Algorithmus-
1- Nimm zwei Haufen (1 Min Heap und 1 Max Heap)
   Max Heap enthält die erste Hälfte der Elemente
   Min Heap enthält die zweite Hälfte der Elemente

2- Vergleichen Sie die neue Nummer aus dem Stream mit der Spitze von Max Heap. 
   Wenn es kleiner oder gleich ist, fügen Sie diese Zahl im maximalen Heap hinzu. 
   Andernfalls fügen Sie die Nummer in Min Heap hinzu.

3- wenn min Heap mehr Elemente als Max Heap hat 
   Entfernen Sie dann das oberste Element von Min Heap und fügen Sie Max Heap hinzu.
   wenn max Heap mehr als ein Element als in Min Heap hat 
   Entfernen Sie dann das oberste Element von Max Heap und fügen Sie Min Heap hinzu.

4- Wenn beide Heaps die gleiche Anzahl von Elementen haben, dann
   Der Median ist die Hälfte der Summe aus max Element aus Max Heap und min Element aus Min Heap.
   Andernfalls ist der Median das maximale Element der ersten Partition.

public class Solution {

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        RunningMedianHeaps s = new RunningMedianHeaps();
        int n = in.nextInt();
        for(int a_i=0; a_i < n; a_i++){
            printMedian(s,in.nextInt());
        }
        in.close();       
    }

    public static void printMedian(RunningMedianHeaps s, int nextNum){
            s.addNumberInHeap(nextNum);
            System.out.printf("%.1f\n",s.getMedian());
    }
}

class RunningMedianHeaps{
    PriorityQueue<Integer> minHeap = new PriorityQueue<Integer>();
    PriorityQueue<Integer> maxHeap = new PriorityQueue<Integer>(Comparator.reverseOrder());

    public double getMedian() {

        int size = minHeap.size() + maxHeap.size();     
        if(size % 2 == 0)
            return (maxHeap.peek()+minHeap.peek())/2.0;
        return maxHeap.peek()*1.0;
    }

    private void balanceHeaps() {
        if(maxHeap.size() < minHeap.size())
        {
            maxHeap.add(minHeap.poll());
        }   
        else if(maxHeap.size() > 1+minHeap.size())
        {
            minHeap.add(maxHeap.poll());
        }
    }

    public void addNumberInHeap(int num) {
        if(maxHeap.size()==0 || num <= maxHeap.peek())
        {
            maxHeap.add(num);
        }
        else
        {
            minHeap.add(num);
        }
        balanceHeaps();
    }
}

Es ist vielleicht erwähnenswert, dass es einen Sonderfall gibt, der eine einfache exakte Lösung hat: Wenn alle Werte im Stream Ganzzahlen innerhalb eines (relativ) kleinen definierten Bereichs sind. Angenommen, sie müssen alle zwischen 0 und 1023 liegen. In diesem Fall definieren Sie einfach ein Array mit 1024 Elementen und eine Anzahl und löschen alle diese Werte. Inkrementieren Sie für jeden Wert im Stream den entsprechenden Bin und die Anzahl. Nachdem der Stream beendet ist, suchen Sie den Behälter, der den höchsten Wert für count / 2 enthält. Dies kann leicht durch Hinzufügen aufeinanderfolgender Behälter ab 0 erreicht werden. Mit derselben Methode kann der Wert einer beliebigen Rangfolge ermittelt werden. (Es gibt eine geringfügige Komplikation, wenn das Erkennen der Behälter-Sättigung und das "Aufrüsten" der Größe der Lagerplätze auf einen größeren Typ während eines Laufs erforderlich ist.)

Dieser Sonderfall mag künstlich erscheinen, ist aber in der Praxis sehr häufig. Es kann auch als Annäherung für reelle Zahlen verwendet werden, wenn sie innerhalb eines Bereichs liegen und eine "gut genug" Genauigkeit bekannt ist. Dies würde für so ziemlich jede Reihe von Messungen an einer Gruppe von "realen" Objekten gelten. Zum Beispiel die Höhen oder Gewichte einer Gruppe von Menschen. Nicht groß genug? Es würde genauso gut für die Längen oder Gewichte aller (einzelnen) Bakterien auf dem Planeten funktionieren - vorausgesetzt, jemand könnte die Daten liefern!

Es sieht so aus, als hätte ich das Original falsch verstanden - es scheint, als würde es einen Schiebefenster-Median anstelle des Medians eines sehr langen Streams wollen. Dieser Ansatz funktioniert immer noch dafür. Laden Sie die ersten N Stream-Werte für das Anfangsfenster, und erhöhen Sie dann für den N + 1. Stream-Wert den entsprechenden Bin, während Sie den Bin entsprechend dem 0. Stream-Wert dekrementieren. In diesem Fall müssen die letzten N Werte beibehalten werden, um die Dekrementierung zu ermöglichen. Dies kann effizient erfolgen, indem ein Array der Größe N zyklisch adressiert wird. Da sich die Position des Medians nur um -2, -1,0,1 ändern kann Bei 2 in jedem Schritt des Schiebefensters müssen nicht alle Bins bis zum Median in jedem Schritt summiert werden. Passen Sie einfach den "Medianzeiger" an, je nachdem, welche Seitenfächer geändert wurden. Zum Beispiel, Wenn sowohl der neue als auch der entfernte Wert unter den aktuellen Median fallen, ändert sich dieser nicht (Offset = 0). Die Methode bricht zusammen, wenn N zu groß wird, um bequem im Speicher gehalten zu werden.

Wenn Sie in der Lage sind, Werte als Funktion von Zeitpunkten zu referenzieren, können Sie Werte durch Ersetzen abtasten und Bootstrapping anwenden , um einen Bootstrap-Medianwert innerhalb von Konfidenzintervallen zu generieren. Auf diese Weise können Sie einen ungefähren Median mit größerer Effizienz berechnen, als eingehende Werte ständig in eine Datenstruktur zu sortieren.

Für diejenigen, die einen laufenden Median in Java benötigen ... PriorityQueue ist Ihr Freund. O (log N) einfügen, O (1) aktueller Median und O (N) entfernen. Wenn Sie die Verteilung Ihrer Daten kennen, können Sie viel besser als dies tun.

public class RunningMedian {
  // Two priority queues, one of reversed order.
  PriorityQueue<Integer> lower = new PriorityQueue<Integer>(10,
          new Comparator<Integer>() {
              public int compare(Integer arg0, Integer arg1) {
                  return (arg0 < arg1) ? 1 : arg0 == arg1 ? 0 : -1;
              }
          }), higher = new PriorityQueue<Integer>();

  public void insert(Integer n) {
      if (lower.isEmpty() && higher.isEmpty())
          lower.add(n);
      else {
          if (n <= lower.peek())
              lower.add(n);
          else
              higher.add(n);
          rebalance();
      }
  }

  void rebalance() {
      if (lower.size() < higher.size() - 1)
          lower.add(higher.remove());
      else if (higher.size() < lower.size() - 1)
          higher.add(lower.remove());
  }

  public Integer getMedian() {
      if (lower.isEmpty() && higher.isEmpty())
          return null;
      else if (lower.size() == higher.size())
          return (lower.peek() + higher.peek()) / 2;
      else
          return (lower.size() < higher.size()) ? higher.peek() : lower
                  .peek();
  }

  public void remove(Integer n) {
      if (lower.remove(n) || higher.remove(n))
          rebalance();
  }
}

Hier ist eine, die verwendet werden kann, wenn die genaue Ausgabe nicht wichtig ist (für Anzeigezwecke usw.). Sie benötigen Totalcount und Lastmedian sowie den neuen Wert.

{
totalcount++;
newmedian=lastmedian+(newvalue>lastmedian?1:-1)*(lastmedian==0?newvalue: lastmedian/totalcount*2);
}

Erzeugt ziemlich genaue Ergebnisse für Dinge wie page_display_time.

Regeln: Der Eingabestream muss in der Reihenfolge der Seitenanzeigezeit glatt sein, eine große Anzahl (> 30 usw.) aufweisen und einen Median ungleich Null haben.

Beispiel: Ladezeit der Seite, 800 Elemente, 10 ms ... 3000 ms, Durchschnitt 90 ms, realer Median: 11 ms

Nach 30 Eingaben beträgt der Medianfehler im Allgemeinen <= 20% (9 ms..12 ms) und wird immer geringer. Nach 800 Eingaben beträgt der Fehler + -2%.

Ein anderer Denker mit einer ähnlichen Lösung ist hier: Median Filter Super effiziente Implementierung

Hier ist die Java-Implementierung

package MedianOfIntegerStream;

import java.util.Comparator;
import java.util.HashSet;
import java.util.Iterator;
import java.util.Set;
import java.util.TreeSet;


public class MedianOfIntegerStream {

    public Set<Integer> rightMinSet;
    public Set<Integer> leftMaxSet;
    public int numOfElements;

    public MedianOfIntegerStream() {
        rightMinSet = new TreeSet<Integer>();
        leftMaxSet = new TreeSet<Integer>(new DescendingComparator());
        numOfElements = 0;
    }

    public void addNumberToStream(Integer num) {
        leftMaxSet.add(num);

        Iterator<Integer> iterMax = leftMaxSet.iterator();
        Iterator<Integer> iterMin = rightMinSet.iterator();
        int maxEl = iterMax.next();
        int minEl = 0;
        if (iterMin.hasNext()) {
            minEl = iterMin.next();
        }

        if (numOfElements % 2 == 0) {
            if (numOfElements == 0) {
                numOfElements++;
                return;
            } else if (maxEl > minEl) {
                iterMax.remove();

                if (minEl != 0) {
                    iterMin.remove();
                }
                leftMaxSet.add(minEl);
                rightMinSet.add(maxEl);
            }
        } else {

            if (maxEl != 0) {
                iterMax.remove();
            }

            rightMinSet.add(maxEl);
        }
        numOfElements++;
    }

    public Double getMedian() {
        if (numOfElements % 2 != 0)
            return new Double(leftMaxSet.iterator().next());
        else
            return (leftMaxSet.iterator().next() + rightMinSet.iterator().next()) / 2.0;
    }

    private class DescendingComparator implements Comparator<Integer> {
        @Override
        public int compare(Integer o1, Integer o2) {
            return o2 - o1;
        }
    }

    public static void main(String[] args) {
        MedianOfIntegerStream streamMedian = new MedianOfIntegerStream();

        streamMedian.addNumberToStream(1);
        System.out.println(streamMedian.getMedian()); // should be 1

        streamMedian.addNumberToStream(5);
        streamMedian.addNumberToStream(10);
        streamMedian.addNumberToStream(12);
        streamMedian.addNumberToStream(2);
        System.out.println(streamMedian.getMedian()); // should be 5

        streamMedian.addNumberToStream(3);
        streamMedian.addNumberToStream(8);
        streamMedian.addNumberToStream(9);
        System.out.println(streamMedian.getMedian()); // should be 6.5
    }
}

Wenn Sie nur einen geglätteten Durchschnitt benötigen, können Sie schnell / einfach den neuesten Wert mit x und den Durchschnittswert mit (1-x) multiplizieren und dann addieren. Dies wird dann der neue Durchschnitt.

Bearbeiten: Nicht das, wonach der Benutzer gefragt hat und nicht so statistisch gültig, aber gut genug für viele Zwecke.
Ich werde es hier (trotz der Abstimmungen) für die Suche lassen!