Ordenamiento de archivos voluminosos

Objetivos: Mostrar cómo se ordenan archivos de datos cuando sus tamaños impiden mantener todo su contenido en memoria. El problema permite además apreciar el manejo de arreglos de lectores de archivos.

Temas:


Ordenamiento de archivo que no caben en la memoria del computador

Los algoritmos de ordenamiento vistos en capítulos anteriores parten del supuesto que los datos que se deben ordenar se encuentra en un arreglo (o en una cola). Estas estructuras de datos están siempre residentes en la memoria principal de computador (memoria RAM) y por lo tanto el tamaño de los datos que se desea ordenar está acotado por la cantidad de memoria del computador.

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:

La primera parte del problema es conceptualmente sencilla. La mezcla de los archivos es más complicada, pero al mismo tiempo interesante. A modo de ejemplo, supongamos que se desea ordenar por carnet de identidad el archivo clientes.dat con millones de clientes y dejar el resultado en clientesxci.dat. La clase Cliente permite manipular las líneas de estos archivos.

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.

    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();
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.

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:

    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();
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.

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.