Ordenamiento en memoria secundaria
Jérémy Barbay 7 Sep 201007/09/10 a las 10:23 hrs.2010-09-07 10:23:07
[EDIT: UCursos tiene problemas con el LaTeX de mis apuntes. Publique en el material Docente una version pdf de estas apuntes (Seccion "Apuntes "Imprimidas"): www.u-cursos.cl/ ... ocente/objeto/315338 ]
2.2 Ordenamiento en memoria secundaria: Mergesort. Cota inferior.
======================================================================
1. Un modelo mas fino
1) Cuantos paginas quedan en memoria local?
- no tan importante para busqueda
- muy importante para applicaciones de computacion con mucho
datos.
2) Nuevas notaciones
- B = Tamano pagina
- N = cantidad de elementos en total
- n = cantidad de paginas con elementos = N/B
- M = cantidad de memoria local
- m = cantidad de paginas locales = M/B
- mnemotechnique:
- N,M,B en # palabras maquinas (=bytes?)
- n,m en # paginas
- n< kB )
* para Ordenar
(corrige y adapte la prueba de [www.daimi.au.dk/~large/ioS06/Alower.pdf] )
- en modelo RAM de comparaciones
- n \lg n
- en modelo Memoria Externa con n/B paginas de tamaño B
* \Omega( N/B \frac{ \lg(N/B) }{ \lg(M/B) } )
* que se puede notar mas simplamente \Omega( n\lg_m n )
- Prueba:
* en vez de considerar el problema de ordenamiento,
supponga que el arregla sea una permutacion y
considera el problema (equivalente en ese caso) de
identificar cual permutacion sea.
* inicialemente, pueden ser n! permutaciones.
- supponga que cada bloque de B elementos sea ya
ordenado (impliqua un costo de al maximo n=N/B
accessos a la memoria externa).
- queda N! / ( n \times (B!) ) permutaciones
posibles.
* para cada accesso a una pagina de memoria externo,
cuantos permutaciones potenciales podemos eliminar?
- con M entradas en memoria primaria
- B nuevas entradas se pueden quedar de \choose{M}{B}
= \frac{M!}{B!(M-B)!} maneras distintas
- calcular la union de los M+B elementos reduce la
cuantidad de permtuaciones por un factor de
1 / \choose{M}{B}
- despues de t accessos (distintos) a la memoria
externa, se reduci la cuantidad de permutaciones a
N! / ( n \times (B!) ( \choose{M}{B} )^t )
* cuanto accessos a la memoria sean necesarios para que
queda al maximo una permutacion?
- N! / ( n \times (B!) ( \choose{M}{B} )^t ) debe ser al maximo uno.
- usamos las formulas siguientes:
- \log(x!) \approx x\log x
- \log \choose{M}{B} \approx B \lg \frac{M}{B}
N! \leq n (B!) (\choose{M}{B})^t
---------+-------------+---------------------------------
N \lg N \leq n B \lg B + t B \lg \frac{M}{B}
---------+-------------+---------------------------------
t \geq \frac { N\lg N - nB \lg B }
{ B \lg(M/B) }
---------+-------------+---------------------------------
\geq \frac { N \lg(N/B) }
{ B \lg(M/B) }
---------+-------------+---------------------------------
\geq \frac { n \lg n }
{ \lg m }
---------+-------------+---------------------------------
\geq n \log_m n
* BONUS: Para ordenar strings, un caso particular (donde la
comparacion de dos elementos tiene un costo variable):
[www.brics.dk/ ... rs/stringsstoc97.pdf]
- \Omega( N_1/B \log_{M/B}(N_1/B) + K_2 \lg_{M/B} K_2 + N/B )
- donde
- N_1 es la suma de los tamanos de las caldenas mas cortas que B
- K_2 es la cuantidad de caldenas mas largas que B
3. Ordenar en Memoria Externa N elementos (en n=N/B paginas)
[en.wikipedia.org/wiki/External_sorting]
* Usando dictionarios o colas de prioridades en memoria externa
- N \lg N / \lg B = N \log_B N
- No es "tight" con la cota inferior
- impliqua
- o que hay un mejor algoritmo
- o que hay una mejor cota inferior
* Queda un algoritmo de ordenamiento: MergeSort
- usa la fusion de $m-1$ arreglos ordenados en memoria
externa:
1) carga en memoria principal $m-1$ paginas, cada una la
primera de su arreglo.
2) calcula la union de estas paginas en la pagina $m$ de
memoria principal,
- botando la pagina cuando llena
- cargando una nueva pagina (del mismo arreglo) cuando
vacilla
3) La complejidad es $n$ accessos.
- Algoritmo:
1) ordena cada de las $n$ paginas -> $n$ accessos
2) Cada nodo calcula la union de $m$ arreglos y escribe su
resultado, pagina por pagina, en la memoria
externa.
- Analisis:
- Cada nivel de recurencia costa $n$ accessos
- Cada nivel reduce por $m-1$ la cantidad de arreglos
- la complejidad total es de orden $n\log_m n$ accessos. (tight)
4. *BONUS* Ahora, cual es la cota inferior para una cola de
prioridad?
- una cola de prioridad se puede usar para ordenar (con $N$ accessos)
- hay una cota inferior para ordernar de $n \log_m n$
- entonces????
2.2 Ordenamiento en memoria secundaria: Mergesort. Cota inferior.
======================================================================
1. Un modelo mas fino
1) Cuantos paginas quedan en memoria local?
- no tan importante para busqueda
- muy importante para applicaciones de computacion con mucho
datos.
2) Nuevas notaciones
- B = Tamano pagina
- N = cantidad de elementos en total
- n = cantidad de paginas con elementos = N/B
- M = cantidad de memoria local
- m = cantidad de paginas locales = M/B
- mnemotechnique:
- N,M,B en # palabras maquinas (=bytes?)
- n,m en # paginas
- n< kB )
* para Ordenar
(corrige y adapte la prueba de [www.daimi.au.dk/~large/ioS06/Alower.pdf] )
- en modelo RAM de comparaciones
- n \lg n
- en modelo Memoria Externa con n/B paginas de tamaño B
* \Omega( N/B \frac{ \lg(N/B) }{ \lg(M/B) } )
* que se puede notar mas simplamente \Omega( n\lg_m n )
- Prueba:
* en vez de considerar el problema de ordenamiento,
supponga que el arregla sea una permutacion y
considera el problema (equivalente en ese caso) de
identificar cual permutacion sea.
* inicialemente, pueden ser n! permutaciones.
- supponga que cada bloque de B elementos sea ya
ordenado (impliqua un costo de al maximo n=N/B
accessos a la memoria externa).
- queda N! / ( n \times (B!) ) permutaciones
posibles.
* para cada accesso a una pagina de memoria externo,
cuantos permutaciones potenciales podemos eliminar?
- con M entradas en memoria primaria
- B nuevas entradas se pueden quedar de \choose{M}{B}
= \frac{M!}{B!(M-B)!} maneras distintas
- calcular la union de los M+B elementos reduce la
cuantidad de permtuaciones por un factor de
1 / \choose{M}{B}
- despues de t accessos (distintos) a la memoria
externa, se reduci la cuantidad de permutaciones a
N! / ( n \times (B!) ( \choose{M}{B} )^t )
* cuanto accessos a la memoria sean necesarios para que
queda al maximo una permutacion?
- N! / ( n \times (B!) ( \choose{M}{B} )^t ) debe ser al maximo uno.
- usamos las formulas siguientes:
- \log(x!) \approx x\log x
- \log \choose{M}{B} \approx B \lg \frac{M}{B}
N! \leq n (B!) (\choose{M}{B})^t
---------+-------------+---------------------------------
N \lg N \leq n B \lg B + t B \lg \frac{M}{B}
---------+-------------+---------------------------------
t \geq \frac { N\lg N - nB \lg B }
{ B \lg(M/B) }
---------+-------------+---------------------------------
\geq \frac { N \lg(N/B) }
{ B \lg(M/B) }
---------+-------------+---------------------------------
\geq \frac { n \lg n }
{ \lg m }
---------+-------------+---------------------------------
\geq n \log_m n
* BONUS: Para ordenar strings, un caso particular (donde la
comparacion de dos elementos tiene un costo variable):
[www.brics.dk/ ... rs/stringsstoc97.pdf]
- \Omega( N_1/B \log_{M/B}(N_1/B) + K_2 \lg_{M/B} K_2 + N/B )
- donde
- N_1 es la suma de los tamanos de las caldenas mas cortas que B
- K_2 es la cuantidad de caldenas mas largas que B
3. Ordenar en Memoria Externa N elementos (en n=N/B paginas)
[en.wikipedia.org/wiki/External_sorting]
* Usando dictionarios o colas de prioridades en memoria externa
- N \lg N / \lg B = N \log_B N
- No es "tight" con la cota inferior
- impliqua
- o que hay un mejor algoritmo
- o que hay una mejor cota inferior
* Queda un algoritmo de ordenamiento: MergeSort
- usa la fusion de $m-1$ arreglos ordenados en memoria
externa:
1) carga en memoria principal $m-1$ paginas, cada una la
primera de su arreglo.
2) calcula la union de estas paginas en la pagina $m$ de
memoria principal,
- botando la pagina cuando llena
- cargando una nueva pagina (del mismo arreglo) cuando
vacilla
3) La complejidad es $n$ accessos.
- Algoritmo:
1) ordena cada de las $n$ paginas -> $n$ accessos
2) Cada nodo calcula la union de $m$ arreglos y escribe su
resultado, pagina por pagina, en la memoria
externa.
- Analisis:
- Cada nivel de recurencia costa $n$ accessos
- Cada nivel reduce por $m-1$ la cantidad de arreglos
- la complejidad total es de orden $n\log_m n$ accessos. (tight)
4. *BONUS* Ahora, cual es la cota inferior para una cola de
prioridad?
- una cola de prioridad se puede usar para ordenar (con $N$ accessos)
- hay una cota inferior para ordernar de $n \log_m n$
- entonces????
| Compartir | |
|---|---|
| Última Modificación | 9 Sep 201009/09/10 a las 15:39 hrs.2010-09-09 15:39:09 |
| Vistas Únicas | 1 |
| Comentarios |
|
