Cálculo rápido de la mediana en Arduino con Wirth QuickSelect


En esta entrada vamos a ensayar distintos algoritmos en C++ para el cálculo rápido de la mediana un microprocesador como Arduino. El interés que tenemos en el cálculo de la mediana es que, en ciertas aplicaciones, resulta un mejor estadístico frente a otros como la media.

En la entrada muestreo múltiple vimos que para mejorar la precisión en adquisición de datos la práctica habitual es realizar varias mediciones y combinar los distintos elementos en algún cálculo.

El primer candidato que seguramente nos viene a la cabeza es emplear la media, como veremos en su momento al hacer un filtro de media móvil. Sin embargo, la media tiene el problema de verse afectada por el ruido y especialmente por puntos espurios.

Imaginemos que tomamos diez mediciones de un sensor, y obtenemos 9 valores entre de 19.7 a 19.9. Pero una de las mediciones da un punto anómalo con un valor de 1000. Un único valor ha hecho que la media se vaya a casi 58, arruinando toda la serie.

Anuncio:

Si queréis un ejemplo más cotidiano y cercano, 10 personas en una habitación cobran de media 1000 euros. Pero puede ser que 9 estén cobrando 100 euros y el último 9100. Ese es el problema de la media.

En estas circunstancias el uso de un estadístico como la mediana puede ser más representativo de la tendencia. De hecho la “estadística robusta”, una representación alternativa a la estadística clásica centrada en la robustez de los datos, emplea la mediana en lugar de la media como indicador de tendencia.

Uno de los motivos por los que la mediana tradicionalmente ha sido relegada por la media como indicador no es su mayor significación estadística si no que, simplemente, esta última es sencilla y rápida de calcular. Además, es una función que podemos manipular matemáticamente y derivar para emplear en soluciones de optimización.

En oposición, el cálculo de la mediana es un proceso costoso. Además, no es una función con la que podamos operar y no es derivable. Sin embargo, la mediana tiene la ventaja de ser más robusta a la aparición de ruido, especialmente de puntos espurios.

Esto hace que la mediana sea muy común en filtros de adquisición, donde muestra un mejor comportamiento especialmente en filtrado de ruido de tipo sal y pimienta. Veremos esto al aplicar el filtrado de mediana.

Comúnmente se considera que el cálculo de la mediana requiere ordenar los elementos de la muestra y tomar el término medio. Sin embargo, existen algoritmos más eficientes para el cálculo de la mediana.

Aquí vamos a ensayar tres algoritmos distintos con dos muestras de 100 y 500 elementos en un Arduino Nano 16Mhz. Como ya dijimos en la entrada de QuickSort, por sus limitaciones no resulta la máquina más adecuada para cálculos, y si necesitamos estos cálculos deberíamos plantearnos un procesador superior. ¡Pero realizar las pruebas con 10 elementos sería aburrido!

Algoritmo QuickSort

El caso base de estudio es realizar la ordenación del vector de entrada y tomar el punto medio. Para ello usaremos el algoritmo QuickSort que vimos en la última entrada por ser uno de los algoritmos más rápidos para ordenar un vector.

Estos son los resultados.

Lógicamente, los tiempos idénticos a los obtenidos con en la entrada de QuickSort, 1540us para la muestra de 100 elementos, y 9500us para la muestra de 500 elementos.

Algoritmo QuickSelect

El algoritmo QuickSelect que permite obtener el k-ésimo elemento de una lista. Está basado en QuickSort desarrollado por el mismo autor (Tony Hoare) y comparte el sistema de partición y pivotaje. Sin embargo, al prescindir de tener que ordenar toda la lista el orden de QuickSelect baja de O(n log n) de QuickSort a O(n) en QuickSelect, manteniendo en el peor de los casos O(n2).

Los resultados son los siguientes.

El tiempo para la muestra de 100 elementos con QuickSelect es 172us, 8.95 veces más rápido que ordenar la lista. En el caso de la muestra de 500 elementos el tiempo es de 2676us, 3.55 veces más rápido que realizar la ordenación de la lista.

Algoritmo Wirth

El algoritmo desarrollado por Niklaus Wirth es una variación del algoritmo QuickSelect de Hoare que admite una implementación más sencilla y eficiente. Fue presentado en 1976 en el libro “Algorithms + data structures = programs”

Los resultados son los siguientes.

El tiempo para la muestra de 100 elementos es de 172us, 8.95 veces más rápido que QuickSort y exactamente igual que el algoritmo QuickSelect. En el caso de la muestra de 500 elementos es de 1480us, 6.42 veces más rápido que ordenar la lista, y 1.80 veces más rápido que QuickSelect.

QuickMedian en una librería

¿Y si lo metemos en una librería para que sea más cómodo de usar? Por supuesto que sí, aquí tenéis los algoritmos en una librería de QuickMedian para Arduino. ¡A disfrutar!

Si te ha gustado esta entrada y quieres leer más sobre Arduino puedes consultar la sección tutoriales de Arduino

Anuncio:

Previous Librería Arduino QuickSort
Next Librería Arduino QuickMedian
1000