algoritmo veloce per ripetute calcolo del percentile?

Question

In un algoritmo devo calcolare la 75 ° percentile di un insieme di dati ogni volta aggiungo un valore. In questo momento sto facendo questo:

1. Ottieni valore x
2. Inserisci x in un array già ordinato sul retro
3. di swap x verso il basso fino a quando l'array è ordinato
4. Leggi l'elemento in posizione di array[array.size * 3/4]

Il punto 3 è O (n), e il resto è O (1), ma questo è ancora piuttosto lento, soprattutto se la matrice diventa più grande. Esiste un modo per ottimizzare questo?

Aggiorna

Grazie Nikita! Dal momento che sto usando C ++ questa è la soluzione più semplice da implementare. Ecco il codice:

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

Si può farlo con due cumuli . Non so se c'è una soluzione meno 'artificiosa', ma questo fornisce O(logn) volta complessità e cumuli sono inclusi anche in librerie standard della maggior parte dei linguaggi di programmazione.

Per prima mucchio (heap A) contiene più piccoli elementi il ??75%, un altro mucchio (heap B) - il resto (il più grande del 25%). In primo luogo si ha il più grande elemento in alto, secondo -. Più piccolo

1. elemento calcolata.

Vedere se nuovo elemento x è <= max(A). Se lo è, aggiungerlo al A mucchio, altrimenti - a B mucchio
. Ora, se abbiamo aggiunto x al mucchio A e 'diventato troppo grande (detiene oltre il 75% di elementi), abbiamo bisogno di rimuovere il più grande elemento da A (O (log n)) e aggiungerlo al mucchio B (anche O (log n) ).
Simile se mucchio B è diventato troppo grande.

2. Ricerca "0.75 mediana"

Basta prendere l'elemento più grande da A (o più piccolo da B). Richiede O (log n) o O (1) tempo, a seconda implementazione mucchio.

modifica
Come Dolphin notato, abbiamo bisogno di specificare con precisione quanto grande ogni heap dovrebbe essere per ogni n (se vogliamo risposta precisa). Per esempio, se size(A) = floor(n * 0.75) e size(B) è il resto, poi, per ogni n > 0, array[array.size * 3/4] = min(B).

Answer 2

Un semplice Order Statistiche Albero è sufficiente per questo .

Una versione equilibrata di questo albero supporti O (log n) tempo di inserimento / cancellazione e di accesso da Rank. Quindi non solo ottenere il percentile 75%, ma anche il 66% o il 50% o qualunque cosa avete bisogno, senza dover modificare il codice.

Se si accede al 75% percentile di frequente, ma solo inserto meno frequentemente, si può sempre memorizzare nella cache il 75% percentile elemento nel corso di una / operazione di eliminazione di inserimento.

La maggior parte delle implementazioni standard (come TreeMap di Java) sono alberi ordine statistici.

Answer 3

È possibile usare la ricerca binaria per fare trovare la posizione corretta in O (log n). Tuttavia, spostando la matrice up è ancora O (n).

Answer 4

Ecco una soluzione Javascript. Copia-incolla in console del browser e funziona. $scores contiene l'elenco dei punteggi e, $percentilegives la n-th percentile della lista. percentile Quindi 75 ° è 76,8 e il 99 percentile è 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

Se si dispone di un insieme noto di valori, in seguito sarà molto veloce:

Crea una vasta gamma di numeri interi (byte anche il lavoro volontà) con il numero di elementi uguali a valore massimo dei dati. Ad esempio, se il valore massimo di t è 100.000 creare un array

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

Ora iterate sull'intero insieme di valori, come

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

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

Ora percentile calcolare come

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

return i;

Si può anche considerare l'utilizzo di un TreeMap invece di array, se i valori non confermano a tali limitazioni.