Algoritmos para calcular la mediana en ejecución?

En tamaños de ventana más pequeños, la n log nordenación podría funcionar. ¿Hay algún algoritmo mejor para lograr esto?

Es una mala forma ordenar una matriz para calcular una mediana. Las medianas (y otros cuantiles) generalmente se calculan utilizando el algoritmo de selección rápida , con complejidad .$O(n)$

También es posible que desee ver mi respuesta a una pregunta relacionada reciente aquí .

Aquí hay un artículo que describe un algoritmo posible. Código fuente incluido y una aplicación bastante seria (detección de ondas gravitacionales basada en interferometría láser), por lo que puede esperar que se pruebe bien.

Si está dispuesto a tolerar una aproximación, existen otros métodos. Por ejemplo, una aproximación es un valor cuyo rango está dentro de una distancia (especificada por el usuario) de la mediana real. Por ejemplo, la mediana tiene un rango (normalizado) de 0.5, y si especifica un término de error del 10%, desearía una respuesta que tenga un rango entre 0.45 y 0.55.

Si tal respuesta es apropiada, existen muchas soluciones que pueden funcionar en ventanas deslizantes de datos. La idea básica es mantener una muestra de los datos de cierto tamaño (aproximadamente 1 / término de error) y calcular la mediana en esta muestra. Se puede demostrar que con alta probabilidad, independientemente de la naturaleza de la entrada, la mediana resultante satisface las propiedades que mencioné anteriormente.

Por lo tanto, la pregunta principal es cómo mantener una muestra continua de los datos de cierto tamaño, y hay muchos enfoques para eso, incluida la técnica conocida como muestreo de yacimientos. Por ejemplo, este documento: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.24.7136

Si mantiene una ventana de datos de longitud k como una lista doblemente ordenada, entonces, mediante una búsqueda binaria (para insertar cada elemento nuevo a medida que se desplaza en la ventana) y una matriz circular de punteros (para ubicar inmediatamente elementos que debe eliminarse), cada cambio de la ventana requiere un esfuerzo O (log (k)) para insertar un elemento, solo un esfuerzo O (1) para eliminar el elemento desplazado fuera de la ventana, y solo un esfuerzo O (1) para encontrar la mediana (porque cada vez que se inserta o elimina un elemento en la lista, puede actualizar un puntero a la mediana en el tiempo O (1)). Por lo tanto, el esfuerzo total para procesar una matriz de longitud N es O ((nk) log (k)) <= O (n log (k)). Esto es mejor que cualquiera de los otros métodos propuestos hasta ahora y no es una aproximación, es exacto.

Como mencionó, la clasificación sería O(n·log n)por una ventana de longitud n. Hacer esta mudanza agrega otra l=vectorlengthhaciendo el costo total O(l·n·log n).

La forma más sencilla de impulsar esto es mantener una lista ordenada de los últimos n elementos en la memoria al pasar de una ventana a la siguiente. Como eliminar / insertar un elemento de / en una lista ordenada son ambos, O(n)esto generaría costos de O(l·n).

Pseudocódigo:

l = length(input)
aidvector = sort(input(1:n))
output(i) = aid(n/2)
for i = n+1:l
    remove input(i-n) from aidvector
    sort aid(n) into aidvector
    output(i) = aid(n/2)

Aquí hay una solución O (1) para encontrar la mediana actual, y O (log n) para agregar un nuevo número http://www.dsalgo.com/RunningMedian.php

Si puede vivir con una estimación en lugar de la mediana real, el Algoritmo Remedian (PDF) es de una pasada con bajos requisitos de almacenamiento y precisión bien definida.

El remedio con base b procede calculando medianas de grupos de observaciones b, y luego medianas de estas medianas, hasta que solo quede una estimación. Este método simplemente necesita k matrices de tamaño b (donde n = b ^ k) ...

Usé esta biblioteca RunningStats C ++ en una aplicación incrustada. Es la biblioteca de estadísticas de ejecución más simple que he encontrado hasta ahora.

Desde el enlace:

El código es una extensión del método de Knuth y Welford para calcular la desviación estándar en una pasada a través de los datos. Calcula asimetría y curtosis también con una interfaz similar. Además de solo requerir una pasada a través de los datos, el algoritmo es numéricamente estable y preciso.