veloce, ad esempio O (log2 (N)), algoritmo mediano scorrevole

Vedi link per un'implementazione di una mediana mobile che utilizza un heap min-max per elaborare ogni nuovo campione in O (LGN). L'heap mantiene i dati liberamente suddivisi in due gruppi, uno più grande della mediana, uno più piccolo. Per ciascun nuovo campione, scambia l'elemento più vecchio nell'heap con quello più recente. Il riequilibrio dell'heap richiede fino a 2 O (lgN) passi: un set-up per assicurarsi che il nuovo oggetto sia più vicino alla mediana di qualsiasi altro genitore, e magari un set-down per spingerlo giù dall'altra parte.

Assumiamo N = 100. Hai i valori grezzi in ordine cronologico raw [1], ..., raw [100] e hai la lista ordinata degli stessi valori ordinata [1], ..., ordinata [100]. Qual è la mediana? La mediana sarà (ordinata [50] + ordinata [51]) / 2.

Ora sposta la finestra di una posizione in modo che i dati grezzi siano grezzi [2], ..., non elaborati [101]. Come si genera un elenco aggiornato per ordinato [1], ..., ordinato [100]? Semplice. Esegui una ricerca binaria per il valore raw [1] nell'array ordinato (ordinato [1], ..., ordinato [100]) e rimuovilo dall'elenco. Sto presupponendo un albero di ricerca binario o l'implementazione di un elenco di skip, quindi non è necessario spostare tutti i valori più alti di raw [1] di una posizione in basso. Ora fai un'altra ricerca binaria per il valore grezzo [101] nell'array ordinato e aggiungilo all'elenco. Sto assumendo di nuovo un albero di ricerca binario o un elenco di salti in modo che non sia necessario spostare tutti i valori più alti rispetto a raw [101] di una posizione in alto.

Come calcoli la mediana ora? Allo stesso modo di prima, sarà (ordinato [50] + ordinato [51]) / 2. Ma ora ordinato [50] e ordinato [51] possono essere diversi valori ora.

Quindi la mediana scorrevole è O (Log (N)) perché è quello che una ricerca binaria prende, che è ciò che stai cercando. Sì, è necessario ordinare i primi valori N, ma una volta fatto, mantieni i numeri ordinati mentre scorri i valori cronologici (segnale). A lungo termine, il tempo impiegato per ordinare quei primi valori sarà semplicemente diluito.

Per alcuni tipi di dati, puoi ottenere filtraggio mediano a tempo costante (Perreault et al, 2007) .

Questo documento descrive il filtro mediano 2D sulle immagini, assumendo che i pixel siano numeri interi a 8 bit.

Si noti che "tempo costante" si riferisce al tempo costante nella dimensione della finestra; non è un tempo costante nella dimensione dei dati o nella precisione (bit) dei dati. Come spiegato di seguito, l'utilizzo di questo algoritmo con dati di alta precisione aumenterà drasticamente l'utilizzo della memoria dall'algoritmo, a causa dell'istogramma.

In primo luogo è necessario comprendere gli istogrammi a più livelli.

• Quando l'alfabeto (il set di valori di pixel consentiti) ha 256 simboli, l'istogramma ha 256 bin.
• Un istogramma multi-livello per 256 bin avrà due livelli. Il primo livello avrà 16 bin e il secondo livello avrà i 256 contenitori completi.
• Ciascuno dei 16 contenitori di primo livello corrisponde a circa 16 contenitori consecutivi nel secondo livello, nel modo più diretto.
• Ogni operazione di incremento (add-sample) incrementerà il bin al secondo livello, nonché uno dei 16 bin al primo livello.
• Allo stesso modo, l'operazione di decremento (rimozione-campione) ridurrà un bin sia sul primo che sul secondo livello.
• Quando è necessario cercare la mediana, si cercherà prima tra i raccoglitori di primo livello, poiché ce ne sono meno. Una volta trovato il raccoglitore di primo livello corretto, uno cercherà tra i 16 bidoni di secondo livello, dove è garantito che uno di quelli conterrà la mediana.
• Da questo, puoi capire perché la complessità temporale dell'algoritmo è proporzionale al numero di bit nella precisione dei dati.

• Quindi, per ogni dimensione di dati, manterrai l'istogramma per una finestra scorrevole, ogni volta aggiungendo un campione e rimuovendo un campione.
• Se i dati hanno più dimensioni, sarà necessario mantenere una matrice di istogrammi (pari a quella dell'ingresso nella prima dimensione).

Ovviamente questo cresce rapidamente per dimensioni maggiori, ma per alcune combinazioni di dimensioni di input e dimensioni delle finestre, questo schema risulta avere prestazioni migliori rispetto agli approcci precedentemente noti.

Se questo algoritmo può essere utilizzato nella tua applicazione dipenderà dal tipo di dati che devi ordinare.

Ad esempio, se i tuoi dati contengono numeri interi a 32 bit e tutti i 2^32 di valori diversi hanno ugualmente probabilità di apparire nei dati, allora avrai bisogno di un istogramma con 2^32 bin, che è un requisito un po 'folle, ma potrebbe essere ancora fattibile. Se i tuoi dati contengono valori in virgola mobile a precisione doppia IEEE e probabilmente tutti i valori di 1023 * 2^52 si verificano, l'istogramma apparentemente non si adatta a nessun tipo di computer attualmente disponibile.

Puoi ridurre il numero di contenitori di istogrammi necessari abbassando la risoluzione (precisione) dei tuoi dati.