algorithme rapide pour le calcul répété de percentile?

Question

Dans un algorithme, je dois calculer le 75e percentile d'un ensemble de données chaque fois que j'ajouter une valeur. En ce moment, je fais ceci:

1. Obtenir la valeur x
2. Insérer x dans un tableau déjà trié à l'arrière
3. échange x jusqu'à ce que le tableau est trié
4. Lire l'élément à array[array.size * 3/4] position

Le point 3 est O (n), et le reste est O (1), mais cela est encore assez lent, surtout si le tableau devient plus grand. Est-il possible d'optimiser cela?

UPDATE

Merci Nikita! Depuis que je suis en utilisant C ++ c'est la solution la plus simple à mettre en œuvre. Voici le 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

Vous pouvez le faire avec deux tas . Je ne sais pas s'il y a une solution moins « arrangé », mais celui-ci fournit la complexité du temps et des tas O(logn) sont également inclus dans les bibliothèques standard de la plupart des langages de programmation.

D'abord tas (heap A) contient plus petits éléments 75%, un autre tas (heap B) - le reste (le plus grand de 25%). Tout d'abord on a le plus grand élément au sommet, deuxième -. Le plus petit

1. Ajout élément.

Voir si nouveau x élément est <= max(A). Le cas échéant, l'ajouter à A tas, sinon - à B tas
. Maintenant, si nous avons ajouté x à tas A et il est devenu trop grand (détient plus de 75% des éléments), nous devons retirer l'élément le plus grand de A (O (log n)) et l'ajouter à tas B (également O (logn) ).
Similaire si tas B est devenu trop grand.

2. Recherche "0,75 médiane"

Il suffit de prendre le plus grand élément de A (ou plus petit de B). Nécessite O (logn) ou O (1) fois, en fonction de la mise en œuvre tas.

modifier Dolphin a noté, nous devons préciser avec précision la taille de chaque tas doit être pour chaque n (si nous voulons répondre de façon précise). Par exemple, si size(A) = floor(n * 0.75) et size(B) est le reste, alors, pour chaque n > 0, array[array.size * 3/4] = min(B).

Answer 2

Un simple Arbre ordre statistique suffit pour cela .

Une version équilibrée de ces supports d'arbre O (logn) insertion de temps / suppression et accès par Rank. Donc, vous obtenez non seulement le percentile 75%, mais aussi 66% ou 50% ou tout ce que vous avez besoin sans avoir à changer votre code.

Si vous accédez à 75% percentile souvent, mais seulement insérer moins fréquemment, vous pouvez toujours mettre en cache l'élément 75% percentile au cours d'une opération d'insertion / suppression.

La plupart des implémentations standard (comme TreeMap Java) sont des arbres de statistique d'ordre.

Answer 3

Vous pouvez utiliser la recherche binaire faire pour trouver la bonne position dans O (log n). Cependant, en déplaçant la matrice est encore jusqu'à O (n).

Answer 4

Voici une solution javaScript. Copier-coller dans la console du navigateur et cela fonctionne. $scores contient la liste des scores et, $percentilegives la n-th percentile de la liste. Donc, 75e percentile est 76,8 et 99 percentile est 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

Si vous avez un ensemble connu de valeurs, suivant sera très rapide:

Créer un grand tableau d'entiers (octets même volonté de travail) avec nombre d'éléments égal à la valeur maximale de vos données. Par exemple, si la valeur maximale de 100 000 t est de créer un tableau

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

itérer sur l'ensemble des valeurs, comme

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

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

Calculer percentile

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

return i;

Vous pouvez également envisager d'utiliser un TreeMap au lieu de tableau, si les valeurs ne confirment pas à ces restrictions.