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:15] 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 233: | Línea 233: | ||
| Esto ocurrió porque tenemos en la ventana un número 1, **que es menor o igual** que el número 2, y **está a su derecha**. Siempre que tengamos un número menor o igual a nuestra derecha, "no somos un número importante", puesto que el otro es "al menos tan bueno como nosotros", pero "nosotros nos vamos antes". | Esto ocurrió porque tenemos en la ventana un número 1, **que es menor o igual** que el número 2, y **está a su derecha**. Siempre que tengamos un número menor o igual a nuestra derecha, "no somos un número importante", puesto que el otro es "al menos tan bueno como nosotros", pero "nosotros nos vamos antes". | ||
| - | La observación del párrafo anterior nos lleva a definir un elemento como *dominado*, cuando tiene otro a su derecha que es menor o igual. La idea es la que comentamos antes: Un elemento dominado tiene otro que es siempre mejor opción, así que se puede ignorar en favor del otro que lo domina. A los elementos que no son dominados por ningún otro, para ponerles algún nombre, los llamaremos los elementos *dominantes*. | + | La observación del párrafo anterior nos lleva a definir un elemento como //dominado//, cuando tiene otro a su derecha que es menor o igual. La idea es la que comentamos antes: Un elemento dominado tiene otro que es siempre mejor opción, así que se puede ignorar en favor del otro que lo domina. A los elementos que no son dominados por ningún otro, para ponerles algún nombre, los llamaremos los elementos //dominantes//. |
| La idea será guardar únicamente los elementos dominantes de la ventana, es decir, aquellos que no tengan a su derecha ningún elemento menor o igual. En nuestra ventana de ejemplo, los elementos dominantes son el 1 y el 3. Observemos que el elemento de la derecha de todo de la ventana **siempre es dominante**: Ya que no tiene ningún elemento a su derecha, y por lo tanto nadie puede dominarlo. Esto es lógico, ya que si a partir de ahora hiciéramos todo ''avanzarA'', quedaría ese elemento solo, y se llegaría a convertir en el mínimo, que es algo que no debería nunca pasarle a un dominado. | La idea será guardar únicamente los elementos dominantes de la ventana, es decir, aquellos que no tengan a su derecha ningún elemento menor o igual. En nuestra ventana de ejemplo, los elementos dominantes son el 1 y el 3. Observemos que el elemento de la derecha de todo de la ventana **siempre es dominante**: Ya que no tiene ningún elemento a su derecha, y por lo tanto nadie puede dominarlo. Esto es lógico, ya que si a partir de ahora hiciéramos todo ''avanzarA'', quedaría ese elemento solo, y se llegaría a convertir en el mínimo, que es algo que no debería nunca pasarle a un dominado. | ||
| 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.1511482538.txt.gz · Última modificación: 2017/11/24 00:15 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
