¿Algoritmos para calcular la mediana en funcionamiento?

Question

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

Answer 1

Como ha mencionado la clasificación sería O(n·log n) para una ventana de longitud n . Hacer esta mudanza añade otro l=vectorlength haciendo que el coste total O(l·n·log n) .

La forma más sencilla de empujar esto es manteniendo una lista ordenada de los últimos n elementos en memoria al pasar de una ventana a la siguiente. Como quitar/insertar un elemento de/a una lista ordenada son ambos O(n) esto supondría unos costes 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)

Answer 2

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

El remediador con base b procede calculando medianas de grupos de b observaciones, y luego medianas de estas medianas, hasta que sólo queda una única estimación. Este método sólo necesita k matrices de tamaño b (donde n = b^k)...

Answer 3

Utilicé este Biblioteca C++ de RunningStats en una aplicación embebida. Es la biblioteca de estadísticas de funcionamiento más sencilla que he encontrado hasta ahora.

Del enlace:

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