algoritmo rápido para el cálculo repetido de percentil?

Question

En un algoritmo que tengo que calcular el percentil 75 de un conjunto de datos cada vez que agrego una valor. En este momento estoy haciendo esto:

1. Obtener valor x
2. Insertar x en una matriz ya ordenados en la parte posterior
3. abajo intercambio x hasta que la matriz es ordenada
4. Leer el elemento en la posición array[array.size * 3/4]

Point 3 es O (n), y el resto es O (1), pero esto es todavía bastante lento, especialmente si la matriz se hace más grande. ¿Hay alguna manera de optimizar esto?

Actualizar

Gracias Nikita! Desde que estoy usando C ++ esta es la solución más fácil de implementar. Aquí está el código:

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

Puede hacerlo con dos montones . No estoy seguro si hay una solución menos 'impuesta', pero éste proporciona O(logn) tiempo de complejidad y montones también se incluyen en las bibliotecas estándar de la mayoría de los lenguajes de programación.

Primera heap (montón A) contiene más pequeños elementos 75%, otro montón (heap B) - el resto (mayor del 25%). El primero tiene mayor elemento en la parte superior, un segundo -. Más pequeño

1. elemento Adición.

A ver si x nuevo elemento es <= max(A). Si es así, añadirlo a A montón, de lo contrario - a B montón
. Ahora bien, si añadimos x al montón A y se hizo demasiado grande (cuenta con más de 75% de elementos), tenemos que eliminar el mayor elemento de A (O (log n)) y añadirlo al montón B (también O (log n) ).
Similar si el montón B se hizo demasiado grande.

2. Búsqueda de "mediana 0,75"

Simplemente tome el mayor elemento de A (o más pequeño de B). Requiere O (log n) o O (1) el tiempo, dependiendo de la implementación montón.

editar
Como Dolphin ha señalado, tenemos que especificar con precisión qué tan grande cada pila debe ser, para cada n (si queremos una respuesta precisa). Por ejemplo, si size(A) = floor(n * 0.75) y size(B) es el resto, a continuación, para cada n > 0, array[array.size * 3/4] = min(B).

Answer 2

Un simple Solicitar Estadísticas árbol es suficiente para este .

Una versión equilibrada de este árbol soportes O (log n) Tiempo de insertar / eliminar y de acceso por Rank. Así que no sólo obtener el percentil 75%, sino también el 66% o el 50% o lo que usted necesita sin tener que cambiar su código.

Si tiene acceso al 75% percentil frecuencia, pero sólo inserto con menos frecuencia, siempre se puede almacenar en caché el 75% percentil elemento durante una operación de inserción / eliminación.

La mayoría de las implementaciones estándar (como TreeMap de Java) son árboles estadístico de orden.

Answer 3

Puede utilizar la búsqueda binaria para hacer encontrar la posición correcta en O (log n). Sin embargo, el desplazamiento de la matriz de arriba todavía es O (n).

Answer 4

Aquí es una solución Javascript. Copiar y pegar en el navegador de la consola y funciona. $scores contiene la lista de resultados y, $percentilegives la n-th percentile de la lista. Así percentil 75º es 76,8 y el 99 percentil es 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 usted tiene un conjunto conocido de valores, siguiendo será muy rápido:

Crear un gran conjunto de números enteros (incluso bytes de trabajo voluntad) con el número de elementos igual que el valor máximo de los datos. Por ejemplo, si el valor máximo de t es 100.000 crear una matriz

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

Ahora iterar sobre todo el conjunto de valores, como

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

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

percentil Ahora calcula como

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

return i;

También puede considerar el uso de un TreeMap en lugar de la matriz, si los valores no confirma a estas restricciones.