finden median in eine Feste Größe-verschieben-Fenster über eine lange Abfolge von Daten

O(n*lg m) ist einfach:

Nur pflegen Sie Ihre Fenster, wie zwei std::sets, eine für die untere Hälfte, eine für die Obere Hälfte. Einfügen eines neuen Elements Kosten O(lg m), zur Feststellung und Entfernung der alten-element kostet das gleiche. Die Bestimmung der median mithilfe der Methode, die Sie beschrieben, in Ihrer Frage kostet O(1).

Wie Sie schieben Sie das Fenster über der Sequenz, in jeder iteration entfernen Sie das Element, Sturz aus dem Fenster (O(lg m)), fügen das neue Element ein (O(lg m)) und berechnen Sie den median (O(1)), was eine Gesamtanzahl von O(n lg m).

Diese Lösung verwendet Speicherplatz O(m), natürlich, aber ich glaube nicht, dass Sie Weg erhalten können, ohne speichern das Fenster Inhalt.

Gleiche Antwort wie hc_ aber statt mit einem stock BST verwenden Sie eine version, bei der jeder Knoten die Anzahl der Elemente im sub-Baum. Auf diese Weise finden median in O(log(m)).

Lege ich meine segment-Baum (siehe meinen anderen post), das es erlaubt, die Frequenz-Verteilung der Zählungen sehr effizient abgefragt werden.

Diese implementiert die folgende Datenstruktur:

|-------------------------------|
|--------------- | ---------------|
|------- | ------- | ------- | -------|
|--- | --- | --- | --- | --- | --- | --- | ---|
  0   1   2   3   4   5   6   7  

Jedes segment hält die Anzahl der Elemente in der Reihe, die es abdeckt.
Ich benutze 2N Segmente für einen Wertebereich von 1..N.
Diese befinden sich in einer einzigen ausgerollt Vektor anstatt die Baum-format zeigen bildlich vor.

Also, wenn Sie berechnen, die rolling gemittelt über eine Reihe von ganzen zahlen, die variieren von 1..65536, dann brauchen Sie nur 128kb zu speichern, und können die insert/delete/query mit O(ln N), wobei N = die Größe des Bereichs, d.h. 2**16 Operationen.

Dies ist ein großer Gewinn, wenn die Daten-Bandbreite ist viel kleiner als Ihre rollenden Fenster.

#if !defined(SEGMENT_TREE_H)
#define SEGMENT_TREE_H
#include <cassert>
#include <array>
#include <algorithm>
#include <set>

#ifndef NDEBUG
#include <set>
#endif

template<typename COUNTS, unsigned BITS>
class t_segment_tree
{
    static const unsigned                       cnt_elements    = (1 << BITS);
    static const unsigned                       cnt_storage     = cnt_elements << 1;
    std::array<COUNTS, cnt_elements * 2 - 1>    counts;
    unsigned                                    count;

#ifndef NDEBUG
    std::multiset<unsigned>                     elements;
#endif
    public:

    //____________________________________________________________________________________

    // constructor

    //____________________________________________________________________________________
    t_segment_tree(): count(0)
    {
        std::fill_n(counts.begin(), counts.size(),  0);
    }
    //~t_segment_tree();

    //____________________________________________________________________________________

    // size

    //____________________________________________________________________________________
    unsigned size() const  { return count; }

    //____________________________________________________________________________________

    // constructor

    //____________________________________________________________________________________
    void insert(unsigned x)
    {
#ifndef NDEBUG
        elements.insert(x);
        assert("...............This element is too large for the number of BITs!!..............." && cnt_elements > x);
#endif
        unsigned ii = x + cnt_elements;
        while (ii)
        {
            ++counts[ii - 1];
            ii >>= 1;
        }
        ++count;
    }

    //____________________________________________________________________________________

    // erase 

    //     assumes erase is in the set
    //____________________________________________________________________________________
    void erase(unsigned x)
    {
#ifndef NDEBUG
        //if the assertion failed here, it means that x was never "insert"-ed in the first place
        assert("...............This element was not 'insert'-ed before it is being 'erase'-ed!!..............." && elements.count(x));
        elements.erase(elements.find(x));
#endif
        unsigned ii = x + cnt_elements;
        while (ii)
        {
            --counts[ii - 1];
            ii >>= 1;
        }
        --count;
    }

    //
    //____________________________________________________________________________________

    // kth element

    //____________________________________________________________________________________
    unsigned operator[](unsigned k)
    {
        assert("...............The kth element: k needs to be smaller than the number of elements!!..............." && k < size());
        unsigned ii = 1;
        while (ii < cnt_storage)
        {
            if (counts[ii - 1] <= k)
               k -= counts[ii++ - 1];
            ii <<= 1;
        }
        return (ii >> 1) - cnt_elements;
    }

};
#endif