Algorithme rapide pour le calcul répété du percentile?

Dans un algorithme, je dois calculer la 75e centile d'un ensemble de données à chaque fois que j'ajoute une valeur. Je fais ceci:

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

Le Point 3 est O (n), et le reste est O(1), mais c'est encore assez lent, surtout si le tableau devient plus grand. Est-il possible de l'optimiser cette?

Mise à JOUR

Merci Nikita! Puisque j'utilise C++, c'est la solution la plus facile à implémenter. 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;
};
27
demandé sur martinus 2010-09-17 23:26:47

5 réponses

, Vous pouvez le faire avec deux tas. Je ne sais pas s'il existe une solution moins "artificielle", mais celle-ci fournit O(logn) la complexité temporelle et les tas sont également inclus dans les bibliothèques standard de la plupart des langages de programmation.

Le premier tas (tas A) contient les plus petits éléments de 75%, un autre tas (tas B) - le reste (plus grand 25%). Le premier a le plus grand élément sur le dessus, le second-le plus petit.

  1. ajout d'un élément.

Voir si le nouvel élément x est max(A). Si c'est le cas, ajoutez - le au tas A, sinon-au tas B.
Maintenant, si nous avons ajouté x au tas A et qu'il est devenu trop grand (contient plus de 75% des éléments), nous devons supprimer le plus gros élément de A (O(logn)) et l'ajouter au tas B (aussi O(logn)).
Similaire si le tas B est devenu trop grand.

  1. Trouver "0.75"médiane

Il suffit de prendre le plus grand élément de A (ou le plus petit de B). Nécessite O(logn) ou O (1) temps, selon tas application.

Modifier
CommeDolphin l'a noté, nous devons spécifier avec précision la taille de chaque tas pour chaque n (si nous voulons une réponse précise). Par exemple, si size(A) = floor(n * 0.75) et size(B) est le reste, ensuite, pour chaque n > 0, array[array.size * 3/4] = min(B).

30
répondu Nikita Rybak 2015-10-26 09:57:10

Un simpleArbre de statistiques D'ordre est suffisant pour cela.

Une version équilibrée de cet arbre prend en charge o (logn) time insert / delete et access by Rank. Donc, vous obtenez non seulement le percentile de 75%, mais aussi le 66% ou 50% ou tout ce dont vous avez besoin sans avoir à changer votre code.

Si vous accédez fréquemment au percentile 75%, mais que vous insérez moins fréquemment, vous pouvez toujours mettre en cache l'élément 75% percentile pendant une opération d'insertion / suppression.

La Plupart des les implémentations (comme le TreeMap de Java) sont des arbres de statistiques d'ordre.

14
répondu Tautvydas 2017-05-12 20:58:57

Vous pouvez utiliser la recherche binaire pour trouver la position correcte dans O (log n). Cependant, le déplacement du tableau vers le haut est toujours O (n).

-1
répondu Matthew Flaschen 2010-09-17 19:29:17

Voici une solution javaScript . Copiez-collez-le dans la console du navigateur et cela fonctionne . $scores contient la Liste des scores et l' , $percentiledonne 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);
-1
répondu sapy 2016-02-03 06:58:13

Si vous avez un ensemble de valeurs, la suite sera très rapide:

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

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

Maintenant 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 :)

Calculez maintenant le percentile comme 

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 d'un tableau, si les valeurs ne confirment pas celles-ci restriction.

-3
répondu Abhinav Maheshwari 2012-09-24 11:48:02