Algorithme rapide de calcul répété de 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. swap x jusqu'à ce que le tableau est trié
  4. Lire l'élément à la position array[array.size * 3/4]

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

Mise à JOUR

Merci Nikita! Depuis que je suis à l'aide de 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;
};
  • Nice, j'ai eu une question similaire à une interview récemment. Nikita a déjà donné ma réponse.
  • Similaire != De même 🙂 je crois que le tas de solution n'est pas nécessaire ici. Il peut travailler pour ceci: stackoverflow.com/questions/2213707/..., mais je pense que c'est une erreur de l'application ici.
  • Je pense qu'il y a un comportement indéfini dans: if (_lower.empty() || x <= _lower.front()) { que l'ordre d'évaluation n'est pas défini.
  • L'ordre d'évaluation est bien défini, si _lower.empty() retourne vrai que le côté droit n'est pas évalué.
  • Vous avez raison, les opérateurs && et || sont une exception en ce qu'ils garantissent l'ordre d'évaluation. Le problème, c'est que leur surchargé homologues inverser ou ne garantit pas l'ordre d'évaluation, selon qu'ils sont définis comme des méthodes, mais ce n'est pas le cas ici. Je vais de référence cette excellente réponse, de SORTE sur le sujet.
InformationsquelleAutor martinus | 2010-09-17