Temas:
Cuando se desea ordenar datos que se encuentran en un archivo, lo que se hace normalmente es leer todas las líneas de datos y colocarlas en un arreglo. Luego se ordena el arreglo y el resultado se graba en un archivo. Por lo tanto, el tamaño del archivo no debe exceder la memoria del computador.
En esta sección veremos como ordenar archivos cuando su tamaño excede la memoria del computador. El algoritmo en palabras es el siguiente:
Ordenamiento del archivo por fracciones
El siguiente código realiza el fraccionamiento del archivo en archivos de nombre auxn, cada uno con a lo más 100000 líneas.
El resultado es que n almancena el número de archivos que se
escribieron y cada uno de estos archivos se encuentra ordenado
por carnet de identidad. La simple concatenación de estos archivos
normalmente no está ordenada.
int MAXL= 100000;
TextReader lect= new TextReader("cuentas.dat");
// Se crea un arreglo para mantener MAXL cuentas
Cuenta[] cuentas= new Cuenta[MAXL];
int n= 0;
while (true) {
// Se leen MAXL líneas y se colocan en el arreglo de cuentas
int lin= 0;
while (lin<MAXL) {
Cuenta cue= new Cuenta(lect);
// El último archivo producido contendrá menos de MAXL líneas
if (lect.eofReached())
break;
cuentas[lin]= cue;
lin= lin+1;
}
if (lin==0)
break;
// Se ordenan las líneas que se leyeron
ordenarxci(cuentas, lin);
// Se escribe el resultado en un archivo con nombre "aux"+n
TextWriter escr= new TextWriter("aux"+n);
int i= 0;
while (i<lin) {
cuentas[i].escribir(escr);
i= i+1;
}
escr.close();
// Se examina si se debe producir un nuevo archivo
n= n+1;
}
lect.close();
Mezcla de los archivos
La idea es crear un arreglo de n lectores de archivos y mantener en memoria una línea de cada archivo. El algoritmo busca el menor cliente (según el criterio de ordenamiento) y lo escribe en el archivo final. Luego lee en el archivo al que pertenecía ese cliente un nuevo cliente. El algoritmo itera hasta acabar todos los archivos auxiliares. El programa que realiza esta mezcla es:
La versión completa de este programa está en Merge.java.
El programa Fabrica.java fabrica un archivo
de prueba para Merge. La clase Cuenta.java es
la clase para manipular las líneas del archivo cuentas.dat.
TextWriter escr= new TextWriter("cuentasxci.dat");
TextReader[] lectores= new TextReader[n];
cuentas= new Cuenta[n];
// Crear los lectores y leer una cuenta en cada archivo
int i= 0;
while (i<n) {
lectores[i]= new TextReader("aux"+i);
cuentas[i]= new Cuenta(lectores[i]);
i= i+1;
}
// Mientras queden archivos por leer
while (n>0) {
// Se determina el índice de la menor cuenta en el arreglo de n cuentas
i= buscarMin(cuentas, n);
// Se graba en el archivo de salida
cuentas[i].escribir(escr);
// Leer una nueva cuenta de lectores[i]
cuentas[i]= new Cuenta(lectores[i]);
if (lectores[i].eofReached()) {
// Si no hay más cuentas en ese archivo se descarta, colocando
// en su lugar el último lector en la i-ésima posición
lectores[i].close();
n= n-1;
lectores[i]= lectores[n];
cuentas[i]= cuentas[n];
}
}
escr.close();
Una ineficiencia de este programa es que la búsqueda del mínimo se hace secuencialmente y por lo tanto toma tiempo O(n), en donde n es el número de archivos. Este no es un problema grave porque normalmente n es pequeño. De todas formas, existen algoritmos que permiten mejorar esta ineficiencia del programa.