C++ Cálculo eficiente de una media móvil

Question

Aquellos de ustedes que han leído mis preguntas anteriores conocen mi trabajo para comprender e implementar quicksort y quickselect, así como algunos otros algoritmos básicos.

La selección rápida se usa para calcular el k-ésimo elemento más pequeño en una lista desordenada, y este concepto también se puede usar para buscar la mediana en una lista desordenada.

Esta vez, necesito ayuda para diseñar una técnica eficiente para calcular con la mediana, porque la selección rápida no es una buena opción, ya que necesita volver a calcular cada vez que cambia la lista. Debido a que quickselect tiene que reiniciarse cada vez, no puede aprovechar los cálculos previos realizados, por lo que estoy buscando un algoritmo diferente que sea similar (posiblemente) pero que sea más eficiente en el área de ejecutar medianas.

Answer 1

El streaming median se calcula utilizando dos montones. Todos los números menores o iguales que la mediana actual están en el montón izquierdo, que está organizado de manera que el número máximo está en la raíz del montón. Todos los números mayores o iguales a la mediana actual están en el montón derecho, que está organizado de modo que el número mínimo esté en la raíz del montón. Tenga en cuenta que los números iguales a la mediana actual pueden estar en cualquier montón. El recuento de números en los dos montones nunca difiere en más de 1.

Cuando comienza el proceso, los dos montones están inicialmente vacíos. El primer número en la secuencia de entrada se agrega a uno de los montones, no importa cuál, y regresó como la primera mediana de transmisión. El segundo número en la secuencia de entrada se agrega al otro montón, si la raíz del montón derecho es menor que la raíz del montón izquierdo, los dos montones se intercambian, y el promedio de los dos números se devuelve como el segundo flujo mediana.

Luego comienza el algoritmo principal. Cada número subsiguiente en la secuencia de entrada se compara con la mediana actual, y se agrega al montón izquierdo si es menor que la mediana actual o al montón derecho si es mayor que la mediana actual; si el número de entrada es igual a la mediana actual, se agrega a cualquier pila que tenga el recuento menor, o bien a un montón arbitrariamente si tienen el mismo recuento. Si eso hace que los recuentos de los dos montones difieran en más de 1, la raíz del montón más grande se elimina y se inserta en el montón más pequeño. Entonces la mediana actual se calcula como la raíz del montón más grande, si difieren en el conteo, o el promedio de las raíces de los dos montones, si son del mismo tamaño.

El código en Scheme y Python está disponible en mi blog.

Answer 2

Una solución sería mantener un order statistic tree, insertando cada elemento de la secuencia sucesivamente, luego calcule la mediana de los elementos en el árbol.

Esto llevaría O (lg n) Tiempo de tiempo por inserción y O (lg n) vez por la mediana, para un total de O (n lg n), más O (n) espacio.

Answer 3

The Jeff McClintock cuenta con una mediana de presupuesto. Requiere mantener solo dos valores. Este ejemplo itera sobre una matriz de valores muestreados (consumo de CPU). Parece converger relativamente rápido (alrededor de 100 muestras) a una estimación de la mediana. La idea es en cada iteración de las pulgadas medianas hacia la señal de entrada a una velocidad constante. La tasa depende de la magnitud que calcule que la mediana sea. Uso el promedio como una estimación de la magnitud de la mediana para determinar el tamaño de cada incremento de la mediana. Si necesita una mediana de precisión de aproximadamente 1%, use un tamaño de paso de 0.01 * el promedio

float median = 0.0f; 
float average = 0.0f; 

// for each sample 
{ 
    average += (sample - average) * 0.1f; // rough running average. 
    median += _copysign(average * 0.01, sample - median); 
} 

Answer 4

Aquí es una estructura de árbol equilibrado C++ que proporciona la capacidad de consultar por el índice en la lista ordenada. Como mantiene todos los valores en orden ordenado, no es tan eficiente como el enfoque de dos montones, pero ofrece cierta flexibilidad adicional. Por ejemplo, también podría darle un cuartil corriente.

template <typename T> 
class Node 
{ 
public: 
    T key; 
    Node* left; 
    Node* right; 
    size_t size; 

    Node(T k) : key(k) 
    { 
     isolate(); 
    } 

    ~Node() 
    { 
     delete(left); 
     delete(right); 
    } 

    void isolate() 
    { 
     left = NULL; 
     right = NULL; 
     size = 1; 
    } 

    void recount() 
    { 
     size = 1 + (left ? left->size : 0) + (right ? right->size : 0); 
    } 

    Node<T>* rotateLeft() 
    { 
     Node<T>* c = right; 
     Node<T>* gc = right->left; 
     right = gc; 
     c->left = this; 
     recount(); 
     c->recount(); 
     return c; 
    } 

    Node<T>* rotateRight() 
    { 
     Node<T>* c = left; 
     Node<T>* gc = left->right; 
     left = gc; 
     c->right = this; 
     recount(); 
     c->recount(); 
     return c; 
    } 

    Node<T>* balance() 
    { 
     size_t lcount = left ? left->size : 0; 
     size_t rcount = right ? right->size : 0; 
     if((lcount + 1) * 2 < (rcount + 1)) 
     { 
      size_t lcount2 = right->left ? right->left->size : 0; 
      size_t rcount2 = right->right ? right->right->size : 0; 
      if(lcount2 > rcount2) 
       right = right->rotateRight(); 
      return rotateLeft(); 
     } 
     else if((rcount + 1) * 2 <= (lcount + 1)) 
     { 
      size_t lcount2 = left->left ? left->left->size : 0; 
      size_t rcount2 = left->right ? left->right->size : 0; 
      if(lcount2 < rcount2) 
       left = left->rotateLeft(); 
      return rotateRight(); 
     } 
     else 
     { 
      recount(); 
      return this; 
     } 
    } 

    Node<T>* insert(Node<T>* newNode) 
    { 
     if(newNode->key < key) 
     { 
      if(left) 
       left = left->insert(newNode); 
      else 
       left = newNode; 
     } 
     else 
     { 
      if(right) 
       right = right->insert(newNode); 
      else 
       right = newNode; 
     } 
     return balance(); 
    } 

    Node<T>* get(size_t index) 
    { 
     size_t lcount = left ? left->size : 0; 
     if(index < lcount) 
      return left->get(index); 
     else if(index > lcount) 
      return right ? right->get(index - lcount - 1) : NULL; 
     else 
      return this; 
    } 

    Node<T>* find(T k, size_t start, size_t* outIndex) 
    { 
     if(k < key) 
      return left ? left->find(k, start, outIndex) : NULL; 
     else if(k > key) 
      return right ? right->find(k, left ? start + left->size + 1 : start + 1, outIndex) : NULL; 
     else 
     { 
      if(outIndex) 
       *outIndex = start + (left ? left->size : 0); 
      return this; 
     } 
    } 

    Node<T>* remove_by_index(size_t index, Node<T>** outNode) 
    { 
     size_t lcount = left ? left->size : 0; 
     if(index < lcount) 
      left = left->remove_by_index(index, outNode); 
     else if(index > lcount) 
      right = right->remove_by_index(index - lcount - 1, outNode); 
     else 
     { 
      *outNode = this; 
      size_t rcount = right ? right->size : 0; 
      if(lcount < rcount) 
       return left ? right->insert(left) : right; 
      else 
       return right ? left->insert(right) : left; 
     } 
     return balance(); 
    } 

    Node<T>* remove_by_value(T k, Node<T>** outNode) 
    { 
     if(k < key) 
     { 
      if(!left) 
       throw "not found"; 
      left = left->remove_by_value(k, outNode); 
     } 
     else if(k > key) 
     { 
      if(!right) 
       throw "not found"; 
      right = right->remove_by_value(k, outNode); 
     } 
     else 
     { 
      *outNode = this; 
      size_t lcount = left ? left->size : 0; 
      size_t rcount = right ? right->size : 0; 
      if(lcount < rcount) 
       return left ? right->insert(left) : right; 
      else 
       return right ? left->insert(right) : left; 
     } 
     return balance(); 
    } 
}; 

template <typename T> 
class MyReasonablyEfficientRunningSortedIndexedCollection 
{ 
private: 
    Node<T>* root; 
    Node<T>* spare; 

public: 
    MyReasonablyEfficientRunningSortedIndexedCollection() : root(NULL), spare(NULL) 
    { 
    } 

    ~MyReasonablyEfficientRunningSortedIndexedCollection() 
    { 
     delete(root); 
     delete(spare); 
    } 

    void insert(T key) 
    { 
     if(spare) 
      spare->key = key; 
     else 
      spare = new Node<T>(key); 
     if(root) 
      root = root->insert(spare); 
     else 
      root = spare; 
     spare = NULL; 
    } 

    void drop_by_index(size_t index) 
    { 
     if(!root || index >= root->size) 
      throw "out of range"; 
     delete(spare); 
     root = root->remove_by_index(index, &spare); 
     spare->isolate(); 
    } 

    void drop_by_value(T key) 
    { 
     if(!root) 
      throw "out of range"; 
     delete(spare); 
     root = root->remove_by_value(key, &spare); 
     spare->isolate(); 
    } 

    T get(size_t index) 
    { 
     if(!root || index >= root->size) 
      throw "out of range"; 
     return root->get(index)->key; 
    } 

    size_t find(T key) 
    { 
     size_t outIndex; 
     Node<T>* node = root ? root->find(key, 0, &outIndex) : NULL; 
     if(node) 
      return outIndex; 
     else 
      throw "not found"; 
    } 

    size_t size() 
    { 
     return root ? root->size : 0; 
    } 
}; 

Answer 5

Algoritmo de rodar la mediana de la ventana:

mediana es una matriz ordenada donde se toma de ella el valor medio.

la implementación de rolling simple es con una cola (dqueue) y sorted_array (cualquier implementación, árbol binario, skiparray).

d_queue es una matriz en la que puede presionar para retroceder y desplazarse (pop) desde la parte frontal de la matriz.

sorted_array es una matriz donde se inserta por orden en la posición que se encuentra utilizando la búsqueda binaria.

Utilicé una cola (matriz de primero en entrar, primero en salir) para rastrear el orden de los valores agregados para saber qué elementos eliminar de la matriz mediana, cuando la cola es más larga que el tamaño deseado. para omitir elementos por fecha y hora o algún índice en ejecución, es posible agregar otra cola y verificar que el primer elemento sea demasiado antiguo, y decidir si eliminar el primer valor de ambas colas.

Para calcular una mediana de manera eficiente, utilizo una técnica de matriz ordenada. es cuando inserta nuevos elementos en su lugar ordenado, por lo que la matriz siempre se ordena.

1. El inserto:

   • Insertar en lugar ordenado en la sorted_array,
   • y empuje un valor en una cola.

2. La remove:

   • Si d_queue primer elemento está fuera de la ventana, o si en una otra cola que puede tener con los índices, el índice es demasiado viejo, entonces:
     • elimine el primer elemento de d_queue (s),
     • y búsquelo en la matriz ordenada y quítelo.

3. Para que la mediana:

   • Utiliza el valor (s) en el medio de la sorted_array.
   • Si sorted_array length es incluso use el elemento en el medio.
   • Si sorted_array length es impar, use un promedio de dos elementos en el medio.

Answer 6

#include<cstdio> 
#include<iostream> 
#include<queue> 
#include <vector>   
#include <functional> 

typedef priority_queue<unsigned int> type_H_low; 
typedef priority_queue<unsigned int, std::vector<unsigned int>, std::greater<unsigned int> > type_H_high; 

size_t signum(int left, int right) { 
    if (left == right){ 
     return 0; 
    } 
    return (left < right)?-1:1; 
} 

void get_median(unsigned int x_i, unsigned int &m, type_H_low *l, type_H_high *r) { 

    switch (signum(l->size(), r->size())) { 
    case 1: // There are more elements in left (max) heap 
     if (x_i < m) { 
      r->push(l->top()); 
      l->pop(); 
      l->push(x_i); 
     } else { 
      r->push(x_i); 
     } 
     break; 

    case 0: // The left and right heaps contain same number of elements 
     if (x_i < m){ 
      l->push(x_i); 
     } else { 
      r->push(x_i); 
     } 
     break; 

    case -1: // There are more elements in right (min) heap 
     if (x_i < m){ 
      l->push(x_i); 
     } else { 
      l->push(r->top()); 
      r->pop(); 
      r->push(x_i); 
     } 
     break; 
    } 

    if (l->size() == r->size()){ 
     m = l->top(); 
    } else if (l->size() > r->size()){ 
     m = l->top(); 
    } else { 
     m = r->top(); 
    } 

    return; 
} 

void print_median(vector<unsigned int> v) { 
    unsigned int median = 0; 
    long int sum = 0; 
    type_H_low H_low; 
    type_H_high H_high; 

    for (vector<unsigned int>::iterator x_i = v.begin(); x_i != v.end(); x_i++) { 
     get_median(*x_i, median, &H_low, &H_high); 
     std::cout << median << std::endl; 
    } 
}