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 22:39] santo |
algoritmos-oia:sliding-window-rmq [2017/11/24 22:42] (actual) santo |
||
|---|---|---|---|
| Línea 248: | Línea 248: | ||
| 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$. | 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 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. | ¿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. | ||
| 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.1511563162.txt.gz · Última modificación: 2017/11/24 22:39 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
