C++ Calcolo efficiente di una mediana in esecuzione

Question

Quelli di voi che hanno letto le mie precedenti domande sono a conoscenza del mio lavoro di comprensione e implementazione di quicksort e quickselect, oltre ad alcuni altri algoritmi di base.

Quickselect viene utilizzato per calcolare il kesimo elemento più piccolo in un elenco non ordinato e questo concetto può anche essere utilizzato per trovare la mediana in una lista non ordinata.

Questa volta, ho bisogno di un aiuto nell'elaborazione di una tecnica efficace per calcolare la mediana esecuzione, perché quickselect non è una buona scelta in quanto ha bisogno di ricalcolare ogni volta che l'elenco viene modificato. Poiché quickselect deve riavviarsi ogni volta, non può trarre vantaggio dai calcoli precedenti, quindi sto cercando un algoritmo diverso che sia simile (probabilmente) ma che sia più efficiente nell'area delle mediane in esecuzione.

Answer 1

Il numero streaming median viene calcolato utilizzando due heap. Tutti i numeri minori o uguali alla mediana corrente sono nell'heap sinistro, che è organizzato in modo che il numero massimo sia alla radice dell'heap. Tutti i numeri maggiori o uguali alla mediana corrente sono nell'heap destro, che è organizzato in modo che il numero minimo sia alla radice dell'heap. Notare che i numeri uguali alla mediana corrente possono essere in uno dei due heap. Il conteggio dei numeri nei due heap non differisce mai di oltre 1.

All'inizio del processo i due heap sono inizialmente vuoti. Il primo numero nella sequenza di input viene aggiunto a uno degli heap, non importa quale e viene restituito come prima mediana di streaming. Il secondo numero nella sequenza di input viene quindi aggiunto all'altro heap, se la radice dell'heap destro è inferiore alla radice dell'heap di sinistra, i due heap vengono scambiati e la media dei due numeri viene restituita come secondo streaming mediano.

Quindi inizia l'algoritmo principale. Ogni numero successivo nella sequenza di input viene confrontato con la mediana corrente e aggiunto all'heap sinistro se è inferiore alla mediana corrente o all'heap destro se è maggiore della mediana corrente; se il numero di input è uguale alla mediana corrente, viene aggiunto a qualsiasi heap abbia il conteggio più piccolo, oppure a uno heap arbitrario se hanno lo stesso conteggio. Se questo fa sì che i conteggi dei due heap differiscano di più di 1, la radice dell'heap più grande viene rimossa e inserita nell'heap più piccolo. Quindi la mediana corrente viene calcolata come radice dell'heap più grande, se differiscono per il conteggio, o la media delle radici dei due heap, se hanno le stesse dimensioni.

Il codice in Schema e Python è disponibile al mio blog.

Answer 2

Una soluzione potrebbe essere quella di mantenere un order statistic tree, inserendo ogni elemento della sequenza a sua volta, quindi calcolare la mediana degli elementi nell'albero.

Questo richiederà O (lg n) tempo per inserimento e O (lg n) volta al mediano, per un totale di O (n lg n) tempo, più O (n) spazio.

Answer 3

La stima mediana della corsa di Jeff McClintock. Richiede di mantenere solo due valori. Questo esempio scorre su una serie di valori campionati (consumo della CPU). Sembra convergere in tempi relativamente brevi (circa 100 campioni) in una stima della mediana. L'idea è ad ogni iterazione dei pollici medi verso il segnale di ingresso ad una velocità costante. Il tasso dipende da quale grandezza si stima che la mediana sia. Io uso la media come stima della grandezza della mediana, per determinare la dimensione di ciascun incremento della mediana. Se hai bisogno della tua mediana accurata a circa l'1%, usa un passo-passo di 0.01 * la media.

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

Ecco un C++ struttura ad albero bilanciato che offre la possibilità di interrogare dal indice nella lista ordinata. Poiché mantiene tutti i valori ordinati, questo non è abbastanza efficiente come l'approccio a due heap, ma offre una certa flessibilità aggiuntiva. Ad esempio, potrebbe anche darti un quartile in esecuzione.

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 di rotolamento mediana della finestra:

mediana è un array ordinato dove si prende da essa il valore centrale.

implementazione semplice rolling è con una coda (dqueue) e una matrice_ordinata (qualsiasi implementazione, albero binario, skiparray).

d_queue è un array in cui è possibile spingere in coda e spostare (pop) dalla parte anteriore dell'array.

array_ordinato è un array in cui si inserisce per ordine alla posizione trovata utilizzando la ricerca binaria.

Ho utilizzato una coda (matrice first-in-first-out) per tenere traccia dell'ordine dei valori aggiunti per sapere quali elementi rimuovere dall'array mediano, quando la coda è più lunga della dimensione desiderata. per eliminare gli elementi per data o alcuni indici in esecuzione, è possibile aggiungere un'altra coda e verificare che il primo elemento sia troppo vecchio e decidere se rimuovere il primo valore da entrambe le code.

Per calcolare una mediana in modo efficiente, utilizzo una tecnica di matrice ordinata. è quando si inseriscono nuovi oggetti nella sua posizione ordinata, quindi l'array viene sempre ordinato.

1. L'inserto:

   • Inserire al posto ordini in sorted_array,
   • e spingere un valore in una coda.

2. Rimuovi:

   • Se d_queue primo elemento è fuori dalla finestra, o se in un un'altra coda si può avere con gli indici, l'indice è troppo vecchio, quindi:
     • rimuovi il primo elemento da d_queue (s),
     • e esegui una ricerca binaria nell'array ordinato e rimuovilo.

3. Per avere la mediana:

   • Utilizzare il valore (s) in mezzo al sorted_array.
   • Se la lunghezza della matrice_ordinata è pari, utilizzare l'elemento nel mezzo.
   • Se la lunghezza della matrice_ordinata è dispari, utilizzare una media di due elementi nel mezzo.

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