c++ - guia - qgis manual

C++ Cálculo eficiente de una mediana en ejecución

Question

Esta pregunta ya tiene una respuesta aquí:

• Encontrar la mediana de una secuencia de enteros [duplicar] 8 respuestas

Aquellos de ustedes que han leído mis preguntas anteriores saben acerca de 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 kth elemento más pequeño en una lista sin clasificar, y este concepto también se puede usar para encontrar la mediana en una lista sin ordenar.

Esta vez, necesito ayuda para idear una técnica eficiente para calcular la mediana de carrera , 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 anteriores realizados, por lo que estoy buscando un algoritmo diferente que sea similar (posiblemente) pero que sea más eficiente en el área de las medianas corrientes.

Answer 1

Algoritmo de la mediana de la ventana rodante:

mediana es una matriz ordenada donde le quitas el valor medio.

La implementación simple rodante es con una cola (dqueue) y una ordenada_array (cualquier implementación, árbol binario, skiparray).

d_queue es una matriz en la que puede desplazarse hacia atrás y desplazarse (pop) desde la parte frontal de la matriz.

sorted_array es una matriz donde se inserta por orden en la posición encontrada mediante la búsqueda binaria.

Utilicé una cola (matriz 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 eliminar elementos por fecha y hora o por algún índice en ejecución, es posible agregar otra cola y verificar que el primer elemento sea demasiado antiguo y decidir si quitar el primer valor de ambas colas.

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

1. El inserto:

   • Insertar en el lugar ordenado en la matriz ordenada,
   • y empujar un valor en una cola.

2. El quitar:

   • Si el primer elemento d_queue está fuera de la ventana, o si en otra cola puede tener índices, el índice es demasiado viejo, entonces:
     • eliminar el primer elemento de d_queue (s),
     • y binario búsquelo en la matriz ordenada y elimínelo.

3. Para tener la mediana:

   • Utilice los valores en el medio de la matriz ordenada.
   • Si la longitud de sorted_array es par, use el elemento del medio.
   • Si sorted_array length es impar, use un promedio de dos elementos en el medio.

Answer 2

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

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 3

El Jeff McClintock ejecuta la estimación de la mediana. Requiere mantener solo dos valores. Este ejemplo itera sobre una matriz de valores muestreados (consumo de CPU). Parece que converge relativamente rápido (alrededor de 100 muestras) a una estimación de la mediana. La idea es, en cada iteración, la mediana de las pulgadas hacia la señal de entrada a una velocidad constante. La tasa depende de qué magnitud estimas que sea la mediana. Utilizo 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 alrededor del 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

La mediana de transmisión se calcula utilizando dos montones. Todos los números menores o iguales a la mediana actual están en el montón izquierdo, que se organiza de modo 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 correcto, que se organiza 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 se devuelve como la primera mediana de transmisión. El segundo número en la secuencia de entrada se agrega luego 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 la segunda transmisión. mediana.

Entonces comienza el algoritmo principal. Cada número subsiguiente en la secuencia de entrada se compara con la mediana actual y se agrega a la pila izquierda si es menor que la mediana actual o a la pila derecha 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 conteo más pequeño, o bien a cualquiera de ellas de forma arbitraria si tienen el mismo conteo. Si eso hace que los conteos 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. Luego, la mediana actual se calcula como la raíz del montón más grande, si difieren en el recuento, o el promedio de las raíces de los dos montones, si son del mismo tamaño.

Code in Scheme and Python está disponible en mi blog .

Answer 5

Una solución sería mantener un árbol de estadísticas de orden , insertando cada elemento de la secuencia a su vez, y luego calcular la mediana de los elementos en el árbol.

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

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;
    }
}