Herramientas de usuario
algoritmos-oia:sliding-window-rmq
Diferencias
Muestra las diferencias entre dos versiones de la página.
| Ambos lados, revisión anterior Revisión previa Próxima revisión | Revisión previa | ||
|
algoritmos-oia:sliding-window-rmq [2017/11/24 00:25] santo |
algoritmos-oia:sliding-window-rmq [2017/11/24 22:42] (actual) santo |
||
|---|---|---|---|
| Línea 18: | Línea 18: | ||
| Es muy común trabajar con datos almacenados en un cierto arreglo, de manera tal que la ventana deslizante se refiere a un cierto subarreglo del mismo en cada momento, y querer **mantener cierta información** sobre los datos en la ventana deslizante en todo momento. Por ejemplo, una de las cosas más fáciles de mantener es la suma de sus elementos: para esto basta con tener una variable ''sumaTotal'', inicialmente en 0, y actualizarla ante cada movimiento: cuando se agrega un elemento, se suma su valor a ''sumaTotal'', y cuando se pierde un elemento, se resta su valor a ''sumaTotal'', pudiendo así mover la ventana deslizante en $O(1)$ manteniendo su suma. | Es muy común trabajar con datos almacenados en un cierto arreglo, de manera tal que la ventana deslizante se refiere a un cierto subarreglo del mismo en cada momento, y querer **mantener cierta información** sobre los datos en la ventana deslizante en todo momento. Por ejemplo, una de las cosas más fáciles de mantener es la suma de sus elementos: para esto basta con tener una variable ''sumaTotal'', inicialmente en 0, y actualizarla ante cada movimiento: cuando se agrega un elemento, se suma su valor a ''sumaTotal'', y cuando se pierde un elemento, se resta su valor a ''sumaTotal'', pudiendo así mover la ventana deslizante en $O(1)$ manteniendo su suma. | ||
| - | El problema que trataremos en esta sección es el de mantener **el mínimo**((O el máximo, que es análogo intercambiando $<$ y $>$.)) de la ventana deslizante. El enfoque de utilizar una simple variable ya no sirve, porque no podemos "restar" en este caso, así que no tenemos manera de manejar eficientemente (sin recalcular desde 0) el caso en que se **saca** un elemento. | + | El problema que trataremos en esta sección es el de mantener **el mínimo**((O el máximo, que es análogo intercambiando $<$ y $>$, e INF y -INF.)) de la ventana deslizante. El enfoque de utilizar una simple variable ya no sirve, porque no podemos "restar" en este caso, así que no tenemos manera de manejar eficientemente (sin recalcular desde 0) el caso en que se **saca** un elemento. |
| Supondremos que al comenzar tenemos $A=B=0$, y tendremos que programar 3 operaciones: | Supondremos que al comenzar tenemos $A=B=0$, y tendremos que programar 3 operaciones: | ||
| Línea 244: | Línea 244: | ||
| * El 10 y el 11 son dominados por el 9 | * El 10 y el 11 son dominados por el 9 | ||
| - | Al dejar solo los dominados, nos quedarían (en orden) los elementos ''[2,3,4,5,9]''. ¿Tiene algo de especial esta lista? Sí: todos sus elementos se encuentran en orden estrictamente creciente. | + | Al dejar solo los dominantes, nos quedarían (en orden) los elementos ''[2,3,4,5,9]''. ¿Tiene algo de especial esta lista? Sí: todos sus elementos se encuentran en orden estrictamente creciente. |
| - | Esta es una de las cosas buenas que tiene la eliminación de dominados: generalmente, cuando nos quedamos solamente con los elementos dominantes, ese conjunto resultante tendrá cierto orden o propiedad particular. En este problema, lo que ocurre es que los elementos dominantes tienen que estar sí o sí en orden creciente estricto: Si $x$ estuviera antes que $y$, pero $x \geq y$, entonces $y$ dominaría a $x$, y no podrían ser ambos dominantes. Si $x$ viene antes qye $y$ pero $y$ no lo domina, tiene que ser necesariamente $x < y$. | + | Esta es una de las cosas buenas que tiene la eliminación de dominados: generalmente, cuando nos quedamos solamente con los elementos dominantes, ese conjunto resultante tendrá cierto orden o propiedad particular. En este problema, lo que ocurre es que los elementos dominantes tienen que estar sí o sí en orden creciente estricto: Si $x$ estuviera antes que $y$, pero $x \geq y$, entonces $y$ dominaría a $x$, y no podrían ser ambos dominantes. Si $x$ viene antes que $y$ pero $y$ no lo domina, tiene que ser necesariamente $x < y$. |
| - | Nuestro plan es entonces guardar todo el tiempo los índices del arreglo en donde se encuentran los elementos dominantes de la ventana actual, de izquierda a derecha. Notar que si tenemos los índices, tenemos también los elementos ya que el elemento en el lugar $i$ es $v[i]$. Como ya habíamos dicho, los únicos elementos que importan a la hora de buscar el mínimo son los dominantes, y esos de hecho están ordenados crecientemente, por lo tanto **el mínimo de la ventana siempre es el primer elemento dominante**, lo que llamaremos ''dominantes[0]''. | + | Nuestro plan es entonces guardar todo el tiempo **los índices** del arreglo en donde se encuentran los elementos dominantes de la ventana actual, de izquierda a derecha. Notar que si tenemos los índices, tenemos también los elementos ya que el elemento en el lugar $i$ es $v[i]$. Como ya habíamos dicho, los únicos elementos que importan a la hora de buscar el mínimo son los dominantes, y esos de hecho están ordenados crecientemente, por lo tanto **el mínimo de la ventana siempre es el primer elemento dominante**, lo que llamaremos ''dominantes[0]''. |
| - | ¿Cómo se ve afectado nuestra lista de dominantes al ''avanzarA''? En este caso, se va un único elemento de la ventana, a la izquierda de todo. Hay dos posibilidades: si ese elemento era dominado, entonces absolutamente nada cambia. Si en cambio ese elemento era dominante, era necesariamente el primer dominante, y hay que eliminarlo de la lista. Podemos distinguir ambos casos mirando el índice, ya que el elemento que se va es el de índice $A$: si ''dominantes[0] == A'', hay que borrar dominantes[0], y sino no. | + | ¿Cómo se ve afectada nuestra lista de dominantes al ''avanzarA''? En este caso, se va un único elemento de la ventana, a la izquierda de todo. Hay dos posibilidades: si ese elemento era dominado, entonces absolutamente nada cambia. Si en cambio ese elemento era dominante, era necesariamente el primer dominante, y hay que eliminarlo de la lista. Podemos distinguir ambos casos mirando el índice, ya que el elemento que se va es el de índice $A$: si ''dominantes[0] == A'', hay que borrar dominantes[0], y sino no. |
| Para poder borrar (e insertar) elementos de cualquiera de los dos extremos, guardaremos la lista de índices de los dominantes en un [[cpp-avanzado:deque|deque]], que declaramos con ''deque<int> dominantes;''. | Para poder borrar (e insertar) elementos de cualquiera de los dos extremos, guardaremos la lista de índices de los dominantes en un [[cpp-avanzado:deque|deque]], que declaramos con ''deque<int> dominantes;''. | ||
| Línea 284: | Línea 284: | ||
| \end{array} \mbox{, mínimo=$0$}$$ | \end{array} \mbox{, mínimo=$0$}$$ | ||
| - | ¡**Todos** los elementos que había antes quedan dominados por el 0! Entonces, para procesar el avanzarB debemos sacar de dominantes todos los elementos que queden dominados por el elemento en la posición B, es decir, todos los que sean mayores o iguales que ''v[B]''. Como los dominantes están siempre ordenados, estos elementos que hay que borrar **están todos al final** de la lista de dominantes. Por lo tanto, podemos ir haciendo ''dominantes.pop_back()'' continuamente, mientras el ''dominantes.back()'' sea el índice de un elemento que queda dominado por el de la posición $B$. | + | ¡**Todos** los elementos que había antes quedan dominados por el 0! Entonces, para procesar el ''avanzarB'' debemos sacar de ''dominantes'' todos los elementos que queden dominados por el elemento en la posición $B$, es decir, todos los que sean mayores o iguales que ''v[B]''. Como los dominantes están siempre ordenados, estos elementos que hay que borrar **están todos al final** de la lista de dominantes. Por lo tanto, podemos ir haciendo ''dominantes.pop_back()'' continuamente, mientras el ''dominantes.back()'' sea el índice de un elemento que queda dominado por el de la posición $B$. |
| Lo anterior describe absolutamente todas las ideas de esta implementación. Recomendamos intentar programarla por uno mismo antes de mirar el código de ejemplo que sigue, como práctica de programación. | Lo anterior describe absolutamente todas las ideas de esta implementación. Recomendamos intentar programarla por uno mismo antes de mirar el código de ejemplo que sigue, como práctica de programación. | ||
algoritmos-oia/sliding-window-rmq.1511483159.txt.gz · Última modificación: 2017/11/24 00:25 por santo
Herramientas de la página
Excepto donde se indique lo contrario, el contenido de este wiki esta bajo la siguiente licencia: Public Domain
