Gewichtete median-Berechnung

Den gewichteten median ist definiert wie folgt:

Wenn x ist ein sortiertes array N Elemente, und w ist die Anordnung der GEWICHTE mit einem Gesamtgewicht W, dann der gewichtete median der letzten x[i] so dass die Summe der w[i] und alle vorherigen GEWICHTE sind weniger als oder gleich S/2.

In C++, kann dies ausgedrückt werden, wie so (vorausgesetzt x, w und W sind definiert wie oben)

double sum = 0;
int i;
for(i = 0; i < N; ++i)
{
    sum += w[i];
    if(sum > W/2)
        break;
}
double median = x[i-1];

BEARBEITEN

So scheint es, dass ich diese Frage beantwortet zu hastig und machte einige Fehler. Fand ich eine nette Beschreibung des gewichteten median von der R-Dokumentation, beschreibt es so:

Für die n Elemente x = c(x[1], x[2], ..., x[n]) mit positiven
GEWICHTE w = c(w[1], w[2], ..., w[n]) so dass sum(w) = S, die
gewichteter median ist definiert als das element x[k] für die erste der
Gesamtgewicht aller Elemente x[i] < x[k] ist weniger oder gleich S/2
und für die das Gesamt-Gewicht aller Elemente x[i] > x[k] weniger
oder gleich S/2.

Aus dieser Beschreibung haben wir ein ziemlich straight-forward-Implementierung des Algorithmus. Wenn wir beginnen, mit k == 0, dann gibt es keine Elemente vor x[k], so dass das Gesamtgewicht der Elemente x[i] < x[k] weniger als S/2. Je nach Daten, das Gesamtgewicht der Elemente x[i] > x[k] werden können oder nicht weniger als S/2. So können wir nur vorwärts durch das array, bis diese zweite Summe wird weniger als oder gleich S/2:

#include <cstddef>
#include <numeric>
#include <iostream>

int main()
{
  std::size_t const N = 5;
  double x[N] = {0, 1, 2, 3, 4};
  double w[N] = {.1, .2, .3, .4, .5};

  double S = std::accumulate(w, w+N, 0.0); //the total weight

  int k = 0;
  double sum = S - w[0]; //sum is the total weight of all `x[i] > x[k]`

  while(sum > S/2)
  {
    ++k;
    sum -= w[k];
  }

  std::cout << x[k] << std::endl;
}

Beachten Sie, dass, wenn der median ist das Letzte element (medianIndex == N-1), dann sum == 0, so ist die Bedingung sum > S/2 ausfällt. So k nie out of bounds (es sei denn N == 0!). Auch, wenn es zwei Elemente, die die Bedingung erfüllen, die der Algorithmus wählt immer die erste.