23-05-2022

Motivaciones

Necesidad de pensar algoritmos distintos según dónde se almacenan los datos con los que operamos:

Cuando trabajamos con una gran cantidad de datos es posible que la memoria principal no alcance para almacenarlos.

Debido a esto, probablemente debamos trabajar también con memoria secundaria. El acceso a memoria secundaria es mucho más costoso que el acceso a memoria principal (típicamente $10^6$ veces más costoso).

Pensaremos ideas algoritmicas para optimizar el uso de memoria principal, intentando utilizar lo menos posible la memoria secundaria.

→ Queremos minimizar la cantidad de veces que un elemento viaja de la memoria secundaria a la memoria principal.

Comentarios

El tiempo de acceso está dominado por el posicionamiento, por ende conviene acceder a bloques de bytes simultáneamente.

En algunos casos sólo se puede acceder a los elementos en forma secuencial.

Habitualmente pueden haber jerarquías de niveles de memoria.

Ordenación - Fusión

• Muchos métodos hacen pasada sobre el archivo, dividiéndolo en bloques que entren en memoria interna, ordenando esos bloques y luego fusionando.
• El acceso secuencial resulta adecuado para este tipo de dispositivos.
• Objetivo: minimizar número de pasadas por el archivo.

Fusión múltiple equilibrada

Caso en el que los registros sólo pueden ser accedidos secuencialmente (ejemplo cinta).

En memoria hay sólo espacio para un número constante y pequeño de registros, pero disponemos de todas las cintas que necesitemos.

Algoritmo

Mientras haya elementos en la cinta de entrada:

Para $i$ hasta $C$ (donde $C$ es la constante de registros que pueden leerse simultáneamente):

Leer $C$ registros a la vez y escribirlos, ya ordenados, en la cinta $i$.

Mientras haya bloques de $C$ en las $i$ cintas:

Fusionar los primeros bloques de cada cinta en una cinta nueva, armando uno de $i \cdot C$ en cada una de las cintas auxiliares.

Fusionar nuevamente las cintas auxiliares en una.