HOWTO · C++
Cálculo de una mediana móvil en C++
La mediana de transmisión se calcula utilizando dos montones. Todos los valores menores o iguales a la mediana actual están en el montón izquierdo. Y todos aquellos mayores o iguales a la mediana actual están en el montón correcto.
Este es un tutorial sobre cómo calcular la mediana móvil de manera eficiente. Comenzaremos con una descripción detallada de la mediana móvil, seguida de un algoritmo y algunas consideraciones de implementación.
Correr mediana
La mediana móvil es una forma eficiente de calcular una secuencia de números. La intuición detrás de esto es que si estamos interesados en la mediana, entonces no necesitamos conocer todos los valores en la secuencia, sino que podemos hacer un seguimiento de cuántos valores están por encima o por debajo de ella.
Si hay un número par de valores, tomaremos el promedio (o la media) de ambas mitades y lo usaremos como nuestro nuevo valor medio.
La mediana móvil comienza con la observación en el medio de la lista ordenada. La siguiente observación se compara con esta observación del medio; si es más grande o más pequeño, se convierte en el nuevo punto medio.
Este proceso continúa hasta que no quedan más observaciones en la lista ordenada.
Cálculo de una mediana móvil en C++
La mediana móvil se calcula utilizando dos montones. Todos los valores menores o iguales a la mediana actual están en el montón izquierdo.
Todos aquellos mayores o iguales a la mediana actual están en el montón derecho.
La mediana móvil se actualiza intercambiando cada número en estos dos montones. Para mantener un número constante de intercambios, necesitamos una forma de saber cuándo uno de estos dos montones se vacía.
Cuando uno de estos dos montones se vacía, significa que todos los valores menores o iguales a la mediana actual se han procesado y todos los valores mayores o iguales se han procesado. En este punto, podemos intercambiar con un valor de cualquier montón que no esté vacío, que siempre será el montón izquierdo o el montón adecuado, dependiendo de cuál se vació primero.
Necesitamos una estructura de datos que admita la inserción y eliminación eficientes en ambos extremos para que este algoritmo funcione. Esta estructura de datos también debería poder aprovechar la localidad de caché.
