Schneller Algorithmus für wiederholte Berechnung der Perzentile?

Question

In einem Algorithmus muss ich berechnen die 75. Perzentil eines Datensatzes, wenn ich ein hinzufügen Wert. Im Moment habe ich tue dies:

1. Get Wert x
2. Einfügen x in ein bereits sortierten Array auf der Rückseite
3. Swap x nach unten, bis das Array wird sortiert
4. Lesen Sie das Element an Position array[array.size * 3/4]

Punkt 3 ist O (n), und der Rest ist O (1), aber das ist immer noch recht langsam, vor allem, wenn das Array größer wird. Gibt es eine Möglichkeit das?

zu optimieren

UPDATE

Danke Nikita! Da ich C ++ verwenden das ist die Lösung am einfachsten zu implementieren. Hier ist der Code:

template<class T>
class IterativePercentile {
public:
  /// Percentile has to be in range [0, 1(
  IterativePercentile(double percentile)
    : _percentile(percentile)
  { }

  // Adds a number in O(log(n))
  void add(const T& x) {
    if (_lower.empty() || x <= _lower.front()) {
      _lower.push_back(x);
      std::push_heap(_lower.begin(), _lower.end(), std::less<T>());
    } else {
      _upper.push_back(x);
      std::push_heap(_upper.begin(), _upper.end(), std::greater<T>());
    }

    unsigned size_lower = (unsigned)((_lower.size() + _upper.size()) * _percentile) + 1;
    if (_lower.size() > size_lower) {
      // lower to upper
      std::pop_heap(_lower.begin(), _lower.end(), std::less<T>());
      _upper.push_back(_lower.back());
      std::push_heap(_upper.begin(), _upper.end(), std::greater<T>());
      _lower.pop_back();
    } else if (_lower.size() < size_lower) {
      // upper to lower
      std::pop_heap(_upper.begin(), _upper.end(), std::greater<T>());
      _lower.push_back(_upper.back());
      std::push_heap(_lower.begin(), _lower.end(), std::less<T>());
      _upper.pop_back();
    }            
  }

  /// Access the percentile in O(1)
  const T& get() const {
    return _lower.front();
  }

  void clear() {
    _lower.clear();
    _upper.clear();
  }

private:
  double _percentile;
  std::vector<T> _lower;
  std::vector<T> _upper;
};

Answer 1

Sie können es mit zwei Haufen . Nicht sicher, ob es eine weniger ‚erfunden‘ Lösung, aber diese bietet O(logn) Zeitkomplexität und Haufen sind auch in Standard-Bibliotheken von den meisten Programmiersprachen enthalten.

Erster Haufen (Heap A) enthält kleinste 75% Elemente, einen weiteren Haufen (heap B) - den Rest (größte 25%). Zuerst hat man größte Element auf der Oberseite, zweiten -. Kleinste

1. Hinzufügen Element.

Sehen Sie, wenn neues Element x ist <= max(A). Wenn ja, fügen Sie es zu Haufen A, sonst - zu Haufen B
. Wenn wir nun x zu Haufen A hinzugefügt und es wurde zu groß (hält mehr als 75% der Elemente), brauchen wir größte Element aus A (O (log n)) und fügen Sie es zu Haufen B (auch O (log n) entfernen ).
Ähnliche, wenn Heap-B zu groß geworden ist.

2. Finding "0,75 Median"

Nehmen Sie einfach das größte Element von A (oder kleinsten von B). Benötigt O (log n) oder O (1) Zeit, abhängig von Heap-Implementierung.

Bearbeiten
Dolphin erwähnt, müssen wir genau angeben, wie groß die einzelnen Haufen für jedes n sein sollte (wenn wir präzise Antwort möchten). Zum Beispiel, wenn size(A) = floor(n * 0.75) und size(B) der Rest ist dann für jeden n > 0, array[array.size * 3/4] = min(B).

Answer 2

Eine einfache Sortieren Statistik Baum dies genug ist, .

Eine ausgewogene Version dieser Baumstützen O (log n) Zeit einfügen / löschen und den Zugang von Rank. So können Sie nicht nur das 75% Perzentile, aber auch das 66% oder 50% oder was auch immer Sie brauchen, ohne den Code zu ändern.

Wenn Sie die 75% Perzentile häufig zugreifen, aber nur Einsatz weniger häufig, können Sie immer Cache die 75% Perzentile Element während eines Einsatzes / Löschvorgang.

Die meisten Standard-Implementierungen (wie Java TreeMap) sind Ordnungsstatistik Bäume.

Answer 3

Sie können binäre Suche verwenden zu tun, die richtige Position in O (log n) zu finden. Jedoch bis das Array Verschiebung noch O (n).

Answer 4

Hier ist eine JavaScript-Lösung. Copy-Paste es in Browser-Konsole und es funktioniert. $scores enthält die Liste der Partituren und $percentilegives die n-th percentile der Liste. So 75. Perzentil ist 76,8 und 99 Perzentil ist 87,9.

function get_percentile($percentile, $array) {
    $array = $array.sort();
    $index = ($percentile/100) * $array.length;
    if (Math.floor($index) === $index) {
         $result = ($array[$index-1] + $array[$index])/2;
    }
    else {
        $result = $array[Math.floor($index)];
    }
    return $result;
}

$scores = [22.3, 32.4, 12.1, 54.6, 76.8, 87.3, 54.6, 45.5, 87.9];

get_percentile(75, $scores);
get_percentile(90, $scores);

Answer 5

Wenn Sie einen bekannten Satz von Werten haben, werden folgende sehr schnell sein:

Erstellen Sie eine große Array von ganzen Zahlen (Bytes selbst Willen der Arbeit) mit der Anzahl der Elemente auf Maximalwert Ihrer Daten entspricht. wenn der Maximalwert von t ist beispielsweise 100.000 erstellen ein Array

int[] index = new int[100000]; // 400kb

Jetzt Iterierte über den gesamten Satz von Werten, wie

for each (int t : set_of_values) {
  index[t]++;
}

// You can do a try catch on ArrayOutOfBounds just in case :)

Jetzt berechnen Perzentile als

int sum = 0, i = 0;
while (sum < 0.9*set_of_values.length) {
  sum += index[i++];
}

return i;

Sie können auch eine TreeMap statt Array betrachten verwenden, wenn die Werte nicht bestätigen diese Einschränkungen.