*Algoritmos en línea*. Competividad. Adaptividad.
Jérémy Barbay 12 Oct 201012/10/10 a las 14:08 hrs.2010-10-12 14:08:12
+ *Algoritmos en línea*. Competividad. Adaptividad.
- List Accessing
REFERENCIA: Capitulo 1 en "Online Computation and Competitive
Analysis", de Allan Borodin y Ran El-Yaniv
1) "List Accessing"
- Considera la secuencia de búsqueda de tamaño $n$, en un
diccionario de tamaño $\sigma$:
"1,1,1,1,1,1,2,2,2,3,3,3,4,4,4,5,5,5,6,6,6,..."
- Cual es el rendimiento de una estructura de diccionario
*estática* (tal que AVL) en este secuencia?
- $n\lg\sigma$
- Se puede mejorar?
- si, utilizando la *localidad* de las consultas, en
*estructuras de datos dinámicas*.
2) Soluciones
1. MTF ("Move To Front"):
- pone las llaves en un arreglo desordenado
- buscas secuencialmente en el arreglo
- muda la llave encontrada en frente
2. TRANS ("Transpose"):
- pone las llaves en un arreglo desordenado
- buscas secuencialmente en el arreglo
- muda la llave encontrada de una posición mas cerca del frente
3. FC ("Frequency Count"):
- mantiene un contador para la frecuencia de cada elemento
- mantiene la lista ordenada para frecuencia decreciente.
4. Splay Trees (y otras estructuras con propiedades de localidad)
([www.dcc.uchile.cl/ ... tes/Diccionario/#8b])
3) Estos son "Algoritmos en Linea"
- algoritmo de optimización
- que conoce solamente una parte de la entrada al tiempo t.
- se compara a la competitividad con el algoritmo offline que
conoce toda la instancia.
- Como se puede medir su complejidad?
- cada algoritmo ejecuta O(n) comparaciones para cada
búsqueda en el peor caso!!!!
- tiene de considerar instancies "fáciles" y "difíciles"
- una medida de dificultad
- e.g. el rendimiento del *mejor algoritmo "offline"*
4) Competitive Analysis: instancias "difíciles" o "fáciles"
- Las estructuras de datos dinámicas pueden aprovechar de
secuencias "fáciles" de consultas: eso se llama "online".
- pero para muchos problemas online, todas las heurísticas se
comportan de la misma manera en el peor caso.
- Por eso se identifica una medida de dificultad de las
instancias, y se comparan los rendimientos de los
algoritmos sobre instancias que tienen una valor fijada de
este medida de dificultad.
- Tradicionalmente, esta medida de dificultad es el
rendimiento del mejor algoritmo "offline": eso se llama
*competitive analysis*, resultando en el *competitive
ratio*, el ratio entre la complejidad del algoritmo ONLINE
y la complejidad del mejor algoritmo OFFLINE.
- por ejemplo, veamos que MTF tiene un competitive ratio de
2
- Pero todavía hay algoritmos con performancia practicas muy
distintas que tienen el mismo competitive ratio. Por eso se
introduce otras medidas de dificultadas mas sofisticadas, y
mas especialidades en cada problema.
5) Competitividad
* Optimización/aproximación
- A es *k(n) competitiva* para un problema de *minimización* si
- \exist b, \forall n,x |x|=n
- C_A(x) - k(n) C_{OPT}(x) \leq b
- A es *k(n) competitiva* para un problema de *maximización* si
- \exist b, \forall n,x |x|=n
- C_{OPT}(x) - k(n) C_{A}(x) \leq b
* Competitiva Ratio
- an algoritmo en linea es *c-competitiva* si
- \exists \alpha, \forall I
- ALG(I) \leq c OPT(I) + \alpha
- an algoritmo en linea es *estrictamente c-competitiva* si
- \forall I
- ALG(I) \leq c OPT(I)
6) Sleator-Tarjan sobre MTF
- costo de una búsqueda negativa (la llave NO esta en el
diccionario)
- $\sigma$
- costo de una búsqueda positiva (la llave esta en el
diccionario)
- la posición de la llave, no mas que $\sigma$
- en promedio para una distribución de probabilidad fijada:
- $MTF \leq 2 OPT$,
- Prueba: (from my notes in my CS240 slides)
How does MTF compare to the optimal ordering?
- Assume that:
- the keys $k_1,\ldots,k_n$ have probabilities
$p_1 \ge p_2 \ge \ldots \ge p_n \ge 0$
- the list is used sufficiently to reach a steady state.
- Then:
$$C_{MTF} < 2\cdot C_{OPT}$$
- Proof:
\begin{eqnarray*}
C_{OPT} & = & \sum_{j=1}^{n} jp_j
C_{MTF} & = & \sum_{j=1}^{n} p_j(\mbox{cost of finding $k_j$})
& = & \sum_{j=1}^{n} p_j(1+\alert{\mbox{number of keys before } k_j})
\end{eqnarray*}
- To compute the average number of keys before $k_j$:
\begin{eqnarray*}
\Pr[\mbox{ $k_i$ before $k_j$}] &=& \frac{p_i}{p_i+p_j}
E(\mbox{ \alert{number of keys before $k_j$}}) &=&
\sum_{i\neq j} \frac{p_i}{p_i+p_j}
\end{eqnarray*}
- $k_i$ is before $k_j$ if and only if
$k_i$ was accessed more recently than $k_j$.
- Consider the last time either $k_i$ or $k_j$ was looked up. What is the probability that it was $k_i$?
\begin{eqnarray*}
P(k_i \textrm{ before } k_j) &=
%& P(k_i \textrm{ chosen }|\ k_i \textrm{ or }k_j\textrm{ chosen }) \\ &=
& \frac{P(k_i \textrm{ chosen })}{P(k_i \textrm{ or } k_j \textrm{ chosen })}
&=& \frac{p_i}{p_i+p_j}
\end{eqnarray*}
- Therefore,
\begin{eqnarray*}
C_{MTF} & = & \sum_{j=1}^{n} p_j (1+\sum_{i\not = j} \frac{p_i}{p_i+p_j})
\mbox{\hspace{.5cm} (Joining both previous formulas.)}
& = & 1 + 2 \sum_{j=1}^n \sum_{i0 y S=
p_1^l,p_2^l,\ldots,p_{k-1}^l,(p_k,p_{k+1})^{l-1}
- Después de las (k-1)l primeras consultas, LFU va a tener
un miss cada consulta, cuando LFD solamente dos.
5. Que tal de FWF?
- MRU=LIFO es un poco estúpido, su mala rendimiento no es
una sorpresa.
- FWF es un algoritmo muy ingenuo también, pero vamos a
ver que no tiene un rendimiento tan mal "en teoría".
5) BONUS: Competive Analysis: Algoritmos a Marcas
1. $k$-fases particiones
Para cada secuencia $S$, partitionala en secuencias
$S_1,\ldots,S_\delta$ tal que
- $S_0 = \emptyset$
- $S_i$ es la secuencia Maxima después de $S_{i-1}$ que
contiene al máximum $k$ consultas distintas.
- Llamamos "fase $i$" el tiempo que el algoritmo considera
elementos de la subsecuencia $S_i$.
- Nota que eso es independiente del algoritmo considerado.
2. Algoritmo con marcas
- agrega a cada pagina de memoria lenta un bit de marca.
- al inicio de cada fase, remuda las marcas de cada
pagina en memoria.
- a dentro de una fase, marca una pagina la primera vez
que es consultada.
- un algoritmo a marca ("marking algorithm") es un
algoritmo que nunca remuda una pagina marcada de su
cache.
3. Un algoritmo con marcas es $k$-competitiva
- En cada fase,
- un algoritmo ONLINE con marcas performa al máximum $k$ miss.
- Un algoritmo OFFLINE (e.g. LFD) performa al mínimum
$1$ miss.
- QED
4. LRU, CLOCK y FWF son algoritmos con marcas
5. LRU, CLOCK y FWF tienen un ratio competitivo ÓPTIMO
6) Mas resultados:
1. La análisis se puede generalizar al caso donde el
algoritmo offline tiene h paginas, y el algoritmo online
tiene $k\geq h$ paginas.
- Cada algoritmo *con marcas* es
$\frac{k}{k-h+1}$-competitiva.
2. Definición de algoritmos (conservadores) da resultado
similar para FIFO (que no es con marcas pero es
conservador).
4. En practica, sabemos que LRU es mucho mejor que FWF (for
instancia). Había mucha investigación para intentar de
mejorar la análisis por 20 anos, ahora parece que hay una
análisis que explica la mejor rendimiento de LRU sobre
FWF, y de variantes de LRU que pueden saber $x$ pasos en
el futuro (Reza Dorrigiv y Alex Lopez-Ortiz).
+ Conclusion Unidad 3
SCHEDULED: <2010-10-07 Thu 12:00-13:30>
* Resultados de Aprendisajes de la Unidad
- Comprender las tecnicas de algoritmos de
- costo amortizado,
- uso de finitud, y
- algorimos competitivos
- Ser capaz de diseñar y analzar algoritmos y estructuras de
datos basados en estos principios.
- conocer algunos casos de estudio relevantes
* Principales casos de estudio:
- estructuras para union-find,
- colas binomiales
- splay trees,
- búsqueda por interpolacíon
- radix sort
- árboles de van Emde Boas
- árboles de sufijos
- técnica de los cuatro rusos,
- paginamiento
- búsqueda no acotada (unbounded search, doubling search)
- List Accessing
REFERENCIA: Capitulo 1 en "Online Computation and Competitive
Analysis", de Allan Borodin y Ran El-Yaniv
1) "List Accessing"
- Considera la secuencia de búsqueda de tamaño $n$, en un
diccionario de tamaño $\sigma$:
"1,1,1,1,1,1,2,2,2,3,3,3,4,4,4,5,5,5,6,6,6,..."
- Cual es el rendimiento de una estructura de diccionario
*estática* (tal que AVL) en este secuencia?
- $n\lg\sigma$
- Se puede mejorar?
- si, utilizando la *localidad* de las consultas, en
*estructuras de datos dinámicas*.
2) Soluciones
1. MTF ("Move To Front"):
- pone las llaves en un arreglo desordenado
- buscas secuencialmente en el arreglo
- muda la llave encontrada en frente
2. TRANS ("Transpose"):
- pone las llaves en un arreglo desordenado
- buscas secuencialmente en el arreglo
- muda la llave encontrada de una posición mas cerca del frente
3. FC ("Frequency Count"):
- mantiene un contador para la frecuencia de cada elemento
- mantiene la lista ordenada para frecuencia decreciente.
4. Splay Trees (y otras estructuras con propiedades de localidad)
([www.dcc.uchile.cl/ ... tes/Diccionario/#8b])
3) Estos son "Algoritmos en Linea"
- algoritmo de optimización
- que conoce solamente una parte de la entrada al tiempo t.
- se compara a la competitividad con el algoritmo offline que
conoce toda la instancia.
- Como se puede medir su complejidad?
- cada algoritmo ejecuta O(n) comparaciones para cada
búsqueda en el peor caso!!!!
- tiene de considerar instancies "fáciles" y "difíciles"
- una medida de dificultad
- e.g. el rendimiento del *mejor algoritmo "offline"*
4) Competitive Analysis: instancias "difíciles" o "fáciles"
- Las estructuras de datos dinámicas pueden aprovechar de
secuencias "fáciles" de consultas: eso se llama "online".
- pero para muchos problemas online, todas las heurísticas se
comportan de la misma manera en el peor caso.
- Por eso se identifica una medida de dificultad de las
instancias, y se comparan los rendimientos de los
algoritmos sobre instancias que tienen una valor fijada de
este medida de dificultad.
- Tradicionalmente, esta medida de dificultad es el
rendimiento del mejor algoritmo "offline": eso se llama
*competitive analysis*, resultando en el *competitive
ratio*, el ratio entre la complejidad del algoritmo ONLINE
y la complejidad del mejor algoritmo OFFLINE.
- por ejemplo, veamos que MTF tiene un competitive ratio de
2
- Pero todavía hay algoritmos con performancia practicas muy
distintas que tienen el mismo competitive ratio. Por eso se
introduce otras medidas de dificultadas mas sofisticadas, y
mas especialidades en cada problema.
5) Competitividad
* Optimización/aproximación
- A es *k(n) competitiva* para un problema de *minimización* si
- \exist b, \forall n,x |x|=n
- C_A(x) - k(n) C_{OPT}(x) \leq b
- A es *k(n) competitiva* para un problema de *maximización* si
- \exist b, \forall n,x |x|=n
- C_{OPT}(x) - k(n) C_{A}(x) \leq b
* Competitiva Ratio
- an algoritmo en linea es *c-competitiva* si
- \exists \alpha, \forall I
- ALG(I) \leq c OPT(I) + \alpha
- an algoritmo en linea es *estrictamente c-competitiva* si
- \forall I
- ALG(I) \leq c OPT(I)
6) Sleator-Tarjan sobre MTF
- costo de una búsqueda negativa (la llave NO esta en el
diccionario)
- $\sigma$
- costo de una búsqueda positiva (la llave esta en el
diccionario)
- la posición de la llave, no mas que $\sigma$
- en promedio para una distribución de probabilidad fijada:
- $MTF \leq 2 OPT$,
- Prueba: (from my notes in my CS240 slides)
How does MTF compare to the optimal ordering?
- Assume that:
- the keys $k_1,\ldots,k_n$ have probabilities
$p_1 \ge p_2 \ge \ldots \ge p_n \ge 0$
- the list is used sufficiently to reach a steady state.
- Then:
$$C_{MTF} < 2\cdot C_{OPT}$$
- Proof:
\begin{eqnarray*}
C_{OPT} & = & \sum_{j=1}^{n} jp_j
C_{MTF} & = & \sum_{j=1}^{n} p_j(\mbox{cost of finding $k_j$})
& = & \sum_{j=1}^{n} p_j(1+\alert{\mbox{number of keys before } k_j})
\end{eqnarray*}
- To compute the average number of keys before $k_j$:
\begin{eqnarray*}
\Pr[\mbox{ $k_i$ before $k_j$}] &=& \frac{p_i}{p_i+p_j}
E(\mbox{ \alert{number of keys before $k_j$}}) &=&
\sum_{i\neq j} \frac{p_i}{p_i+p_j}
\end{eqnarray*}
- $k_i$ is before $k_j$ if and only if
$k_i$ was accessed more recently than $k_j$.
- Consider the last time either $k_i$ or $k_j$ was looked up. What is the probability that it was $k_i$?
\begin{eqnarray*}
P(k_i \textrm{ before } k_j) &=
%& P(k_i \textrm{ chosen }|\ k_i \textrm{ or }k_j\textrm{ chosen }) \\ &=
& \frac{P(k_i \textrm{ chosen })}{P(k_i \textrm{ or } k_j \textrm{ chosen })}
&=& \frac{p_i}{p_i+p_j}
\end{eqnarray*}
- Therefore,
\begin{eqnarray*}
C_{MTF} & = & \sum_{j=1}^{n} p_j (1+\sum_{i\not = j} \frac{p_i}{p_i+p_j})
\mbox{\hspace{.5cm} (Joining both previous formulas.)}
& = & 1 + 2 \sum_{j=1}^n \sum_{i0 y S=
p_1^l,p_2^l,\ldots,p_{k-1}^l,(p_k,p_{k+1})^{l-1}
- Después de las (k-1)l primeras consultas, LFU va a tener
un miss cada consulta, cuando LFD solamente dos.
5. Que tal de FWF?
- MRU=LIFO es un poco estúpido, su mala rendimiento no es
una sorpresa.
- FWF es un algoritmo muy ingenuo también, pero vamos a
ver que no tiene un rendimiento tan mal "en teoría".
5) BONUS: Competive Analysis: Algoritmos a Marcas
1. $k$-fases particiones
Para cada secuencia $S$, partitionala en secuencias
$S_1,\ldots,S_\delta$ tal que
- $S_0 = \emptyset$
- $S_i$ es la secuencia Maxima después de $S_{i-1}$ que
contiene al máximum $k$ consultas distintas.
- Llamamos "fase $i$" el tiempo que el algoritmo considera
elementos de la subsecuencia $S_i$.
- Nota que eso es independiente del algoritmo considerado.
2. Algoritmo con marcas
- agrega a cada pagina de memoria lenta un bit de marca.
- al inicio de cada fase, remuda las marcas de cada
pagina en memoria.
- a dentro de una fase, marca una pagina la primera vez
que es consultada.
- un algoritmo a marca ("marking algorithm") es un
algoritmo que nunca remuda una pagina marcada de su
cache.
3. Un algoritmo con marcas es $k$-competitiva
- En cada fase,
- un algoritmo ONLINE con marcas performa al máximum $k$ miss.
- Un algoritmo OFFLINE (e.g. LFD) performa al mínimum
$1$ miss.
- QED
4. LRU, CLOCK y FWF son algoritmos con marcas
5. LRU, CLOCK y FWF tienen un ratio competitivo ÓPTIMO
6) Mas resultados:
1. La análisis se puede generalizar al caso donde el
algoritmo offline tiene h paginas, y el algoritmo online
tiene $k\geq h$ paginas.
- Cada algoritmo *con marcas* es
$\frac{k}{k-h+1}$-competitiva.
2. Definición de algoritmos (conservadores) da resultado
similar para FIFO (que no es con marcas pero es
conservador).
4. En practica, sabemos que LRU es mucho mejor que FWF (for
instancia). Había mucha investigación para intentar de
mejorar la análisis por 20 anos, ahora parece que hay una
análisis que explica la mejor rendimiento de LRU sobre
FWF, y de variantes de LRU que pueden saber $x$ pasos en
el futuro (Reza Dorrigiv y Alex Lopez-Ortiz).
+ Conclusion Unidad 3
SCHEDULED: <2010-10-07 Thu 12:00-13:30>
* Resultados de Aprendisajes de la Unidad
- Comprender las tecnicas de algoritmos de
- costo amortizado,
- uso de finitud, y
- algorimos competitivos
- Ser capaz de diseñar y analzar algoritmos y estructuras de
datos basados en estos principios.
- conocer algunos casos de estudio relevantes
* Principales casos de estudio:
- estructuras para union-find,
- colas binomiales
- splay trees,
- búsqueda por interpolacíon
- radix sort
- árboles de van Emde Boas
- árboles de sufijos
- técnica de los cuatro rusos,
- paginamiento
- búsqueda no acotada (unbounded search, doubling search)
| Compartir | |
|---|---|
| Última Modificación | 12 Oct 201012/10/10 a las 14:08 hrs.2010-10-12 14:08:12 |
| Vistas Únicas | 8 |
