Cálculo de una mediana móvil en C++
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é.
Muhammad Adil is a seasoned programmer and writer who has experience in various fields. He has been programming for over 5 years and have always loved the thrill of solving complex problems. He has skilled in PHP, Python, C++, Java, JavaScript, Ruby on Rails, AngularJS, ReactJS, HTML5 and CSS3. He enjoys putting his experience and knowledge into words.
Facebook