algorithm - Algoritmo rápido para el cálculo repetido del percentil

optimization data-structures

Question

En un algoritmo, debo calcular el percentil 75 de un conjunto de datos siempre que agregue un valor. En este momento estoy haciendo esto:

1. Obtener valor x
2. Inserta x en una matriz ya ordenada en la parte posterior
3. intercambie x abajo hasta que la matriz esté ordenada
4. Lea el elemento en la array[array.size * 3/4] posición array[array.size * 3/4]

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

ACTUALIZAR

Gracias Nikita! Como uso 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

Aquí hay una solución javaScript. Copiar y pegar en la consola del navegador y funciona. $scores contiene la Lista de puntajes y, $percentile da el n-th percentile de la lista. Entonces, el percentil 75 es 76.8 y el percentil 99 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 2

Puede usar la búsqueda binaria para encontrar la posición correcta en O (log n). Sin embargo, desplazar el conjunto hacia arriba sigue siendo O (n).

Answer 3

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

El primer montón (pila A) contiene el 75% de elementos más pequeños, otro montón (pila B), el resto (el 25% más grande). El primero tiene el elemento más grande en la parte superior, el segundo más pequeño.

1. Agregar elemento.

Ver si el nuevo elemento x es <= max(A) . Si es así, agréguelo al montón A , de lo contrario, para acumular B
Ahora, si añadimos x al montón A y se hizo demasiado grande (contiene más del 75% de los elementos), necesitamos eliminar el elemento más grande de A (O (logn)) y agregarlo al montón B (también O (logn) )
Similar si el montón B se hizo demasiado grande.

2. Encontrar "0.75 mediana"

Simplemente toma el elemento más grande de A (o el más pequeño de B). Requiere tiempo O (logn) u O (1), dependiendo de la implementación del montón.

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

Answer 4

Si tiene un conjunto de valores conocido, lo siguiente será muy rápido:

Cree una gran matriz de enteros (incluso los bytes funcionarán) con una cantidad de elementos igual al valor máximo de sus datos. Por ejemplo, si el valor máximo de t es 100,000, crea una matriz

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

Ahora itere 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 :)

Ahora calcule el percentil 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 una matriz, si los valores no confirman estas restricciones.

Answer 5

Un simple árbol de estadísticas de pedidos es suficiente para esto.

Una versión equilibrada de este árbol admite la inserción / eliminación de O (logn) time y el acceso por rango. Por lo tanto, no solo obtendrá el percentil del 75%, sino también el 66% o el 50% o lo que necesite sin tener que cambiar su código.

Si accede al percentil 75% con frecuencia, pero solo inserta con menos frecuencia, siempre puede almacenar en caché el elemento percentil 75% durante una operación de inserción / eliminación.

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