PDF de programación - Tema III Clasificación en memoria secundaria - Estructura de datos y Algoritmos

Estructura de datos y
Algoritmos

Tema III
Clasificación en memoria secundaria

3.1. Clasificación externa basada en mezcla
3.1.1. Mezcla directa.
3.1.2. Mezcla natural.
3.1.3. Mezcla balanceada múltiple.
3.1.4. Clasificación polifásica.
3.2. Archivos Indexados
3.3 Tablas de dispersión (Hashing)

3.1. Clasificación externa
basada en mezcla
 Problema: Los datos a ordenar no caben todos en

memoria principal , están almacenados en
dispositivos periféricos de acceso secuencial:
 Cinta: TDA secuencia
 Disco: TDA archivo

 Restricciones en el proceso de clasificación:

 Acceso secuencial a cada uno de los elementos de una

secuencia.

 No permite aplicar los métodos de clasificación sobre

arreglos en los que el acceso a cualquier elemento
implicaba el mismo coste.

Tipos de técnicas de clasificación
externa basadas en Mezcla:
 Mezcla directa
 Mezcla directa de una fase
 Mezcla natural
 Mezcla balanceada múltiple
 Clasificación polifásica

Definiciones:

 Mezcla:

 Tarea de combinar varias secuencias en una sola, mediante la

selección repetida de los componentes accesibles en cada
momento.

 Es una operación auxiliar previa utilizada como estrategia para

desarrollar la tarea de clasificación.

 Fase:

 Cada operación que trata un conjunto completo de datos.

Ejemplos: distribución, mezcla.

 Pase (etapa):

 El proceso más corto que, por repetición, forma parte del
proceso de clasificación. Ejemplo: distribución + mezcla.

 Cinta: cada una de las secuencias necesarias en el proceso de

clasificación.

3.1.1. Mezcla directa
 Tomar como fuente la secuencia original c1
 Dividir la fuente en dos mitades, en las cintas

destino c2 y c3

 Mezclar c2 y c3 combinando cada elemento

accesible en pares ordenados, en c1

 Repetir el proceso:

 Se obtiene una cinta con cuádruplos ordenados.

 Repetir el proceso hasta que toda la cinta esté

ordenada

 Cada pase o etapa consta de dos fases,

 Una de división y
 Otra de mezcla, por ello se denomina mezcla de dos fases

o mezcla de tres cintas.

Análisis de clasificación por
mezcla directa

 En las mezclas el número de comparaciones es de poco interés
práctico frente a la penalización de tiempo que supone el realizar
movimientos.

 La complejidad es parecida a la de los algoritmos avanzados de

clasificación en memoria principal.

3.1.2 Mezcla Directa de una Fase
(Mezcla directa balanceada)

 Debemos observar que la fase de división no aporta nada a la

clasificación y sin embargo tiene un coste computacional
significativo

 Las fases de división de la mezcla directa pueden eliminarse

combinando la fase de división con la de mezcla
 Mejora el método de mezcla directa

 En vez de mezclar en una sola cinta,que posteriormente será

dividida, puede irse directamente separando en dos, de manera que
en el siguiente pase ya estarán divididas (se elimina la distribución).

 Análisis

 Se producen el entero mayor de log n pases, por tanto el

número de movimientos es:

 El número de comparaciones es inferior ya que en las

operaciones de copiado de cabos no se produce ninguna.

3.1.2. Mezcla natural

 Aprovecha el hecho de que entre los elementos de la secuencia

original, algunos elementos consecutivos ya se encontrarán
ordenados entre sí.

 La mezcla natural se basa en la combinación de subsecuencias
ordenadas. Las subsecuencias ordenadas de la cinta fuente, se
distribuyen en dos cintas destino auxiliares a y b. Seguidamente se
mezcla una subsecuencia ordenada de cada cinta auxiliar.
 Fuente c
 Distribuir las subsecuencias ordenadas de la fuente en las cintas destino

a y b

 Mezclar a y b en c, combinando subsecuencias ordenadas de cada cinta

auxiliar.

 Cada pase en la mezcla natural consta de dos fases, una de

distribución y otra de mezcla.

Análisis mezcla natural

 En el peor caso el número de movimientos

es de orden nlog n, e inferior en el caso
promedio.

 El número de comparaciones es mucho

mayor, pero al ser el coste de una
comparación muy inferior al de un
movimiento, este incremento no resulta
significativo.

3.1.3 Mezcla Balanceada
Múltiple

 Persigue reducir el número de movimientos (copias) para

reducir el número de pases.

 Se consigue:

 Realizando la distribución entre más de dos cintas (mezcla

múltiple)

 En la mezcla se combinan más de dos subsecuencias

ordenadas (una por cinta)
 La mezcla se realiza en una sola fase, sobre varias

cintas auxiliares

 Se elimina la fase de distribución, salvo la inicial

Análisis balanceada múltiple

 Hay una cinta inicial con m subsecuencias ordenadas
 Supóngase que se utilizan N cintas destino en la fase de

distribución.
 Una vez hecha la primera distribución, hay que mezclar las m

subsecuencias ordenadas que están distribuidas
uniformemente en N cintas

 En una primera fase de mezcla, una subsecuencia ordenada de
m/N subsecuencias ordenadas, en la segunda de m/N2 y en la
k-ésima m/Nk.

 El número total de pases necesarios para clasificar n

subsecuencias ordenadas con N cintas será, en el peor de los
casos

 Como cada pase necesita n copias, el número total de copias

vendrá dado por

3.1.4.- Clasificación
polifásica.
 Mejora el rendimiento de la mezcla balanceada.
 Las cintas fuente y destino no son establecidas a

priori, sino como consecuencia de la mezcla
realizada.
 En el proceso de mezcla, dos hacen de fuente y

la tercera de destino,

 Al finalizar las combinaciones hará de cinta

destino aquella que se haya agotado, la cual sólo
podrá ser identificada tras la mezcla.

 La clasificación polifásica aprovecha al máximo las
cintas ya que con N cintas realiza mezclas de N-1
subsecuencias ordenadas.

 Lo que se pretende es que al final haya una sola
subsecuencia ordenada en una cinta y las demás
estén agotadas. Esto no siempre es posible.

 En el ejemplo hay dos cintas vacías y a otra todavía

le quedan dos subsecuencias

Construcción de
la clasificación
polifásica
satisfactoria de
tres cintas

+

Conclusión:

 La clasificación polifásica con 3 cintas será

satisfactoria si la distribución inicial de
subsecuencias ordenadas entre las cintas
fuentes es tal que son números
consecutivos de Fibonacci.

Condición generalizada para
n cintas
 Para que una clasificación polifásica con N

cintas sea satisfactoria (o perfecta) el número
de subsecuencias ordenadas iniciales tiene
que ser suma de cualquier N-1, N-2,...1
sumas de números de Fibonacci de orden
N-2.

3.2.- Archivos indexados

 Las implementaciones de secuencias en algunos dispositivos de memoria

secundaria, tales como discos duros, permiten un acceso cuasialeatorio
(fichero):
 Acceso aleatorio al sector + Offset de acceso secuencial

 El método de clasificación mediante archivos indexados se basa en
considerar, asociado a cada llave, la dirección física del registro que
caracteriza.

 Se crea un segundo archivo, archivo de índices, en el que se almacenan

pares (dirección, llave).

Indexados
 Las operaciones de clasificación y búsqueda suelen
realizarse en memoria principal sobre el archivo de
índices y no sobre el archivo de datos.

 Indexado de índice denso

 Cuando el archivo índice contiene la dirección de cada

registro de la llave

 Indexado de Indice disperso

 Cuando el archivo índice contiene grupos de llaves
 Está formado por grupos de pares (x, b) donde b es la
dirección física del bloque en el cual el primer registro
tiene la llave de valor x.

 La búsqueda se realiza por bloques lo que evita
comparar con todos y cada uno de los elementos.

3.4.- Tablas de dispersión
(Hashing)
 La idea básica consiste en transformar las
llaves en direcciones de memoria mediante
una función de transformación.

 Las tablas de dispersión se aplican cuando el
conjunto de llaves posibles es mucho mayor
que el de llaves reales a almacenar.
 Los alumnos de una clase por su DNI

Definiciones I
 Dado un conjunto de llaves posibles X, y un

conjunto de direcciones de memoria D, una función
de transformación H(x), es una aplicación
suprayectiva del conjunto de llaves posibles en el
conjunto de direcciones de memoria: H: X -> D
 El TDA tabla de dispersión es un tipo de datos

homogéneo, denominadas celdas, de tamaño fijo,
Ttabla, compuesto por un número fijo de
componentes a las que se accede mediante una
dirección de memoria resultante de una función de
transformación. Sobre este TDA se definen los
operadores Insertar, Buscar y Eliminar.

 Dos llaves distintas x1 y x2 son sinónimas si H(x1)

= H(x2)

 Cuando una nueva llave se aplica a una dirección de

memoria completamente ocupada,

 Cuando dos llaves distintas se aplican sobre la misma

Definiciones II
 Desbordamiento

 Colisión

celda.

 Densidad de llaves

 El cociente entre el número de llaves en uso, m, y el

número total de llaves posibles, nx

 Factor de carga (o densidad de carga),α,

 Al cociente entre el número de llaves en uso y el número
total de registros almacenables en la tabla de dispersión:
 α = m / (s*b); donde s es el número de registros por bloque y

b el número de bloques que hay en la tabla de dispersión.

Ejemplo:

por bloque.

 Tabla de dispersión que consta de mil bloques con dos registros

 El conjunto de llaves posibles es el conjunto de números del DNI

(00000000 al 99999999) y

 La función de dispersión se define tal que los tres primeros
dígitos del DNI asignan la dirección de memoria (000 a 999).

3.4.1 Funciones Hash

 Elección de una Función de Transformación

 Requisitos básicos de una función de transformación:

 La dirección de memoria debe ser calculada con sencillez
 Distribución de llaves uniforme

 Que se produzcan el menor número posible de colisiones.

 Función Resto de División: f(x) = X mod M
 Función plegado:

 La dirección se obtiene dividiendo la llave en partes iguales y

sumando todas ellas.

 Plega