Procesamiento de Datos Masivos

Objetivos: Mostrar como se resuelven los problemas de procesamiento de datos, cuando estos no caben en la memoria del computador.

Temas:

Organización de datos en archivos

Hasta el momento hemos supuesto que los datos que maneja una aplicación no son tan voluminosos y por lo tanto caben en memoria. Cuando recurrimos a archivos se debe a la necesidad de conservar datos después de que termina un programa, por ejemplo para apagar el computador.

Sin embargo, existen problemas en donde el volumen de datos es tan grande que es imposible mantenerlos en memoria. Entonces, los datos se almacenan en un conjunto de archivos, los que forman una base de datos. Una base de datos es por lo tanto un conjunto de archivos que almacenan, por ejemplo, datos con respecto al negocio de una empresa.

Cada archivo se forma en base a un conjunto de líneas y cada línea esta formada por campos de información. Todas las líneas de un mismo archivo tienen la misma estructura, es decir los mismos campos de información. Diferentes archivos poseen estructuras distintas, i.e. campos de información.

Por ejemplo, el archivo de postulantes post.dat, visto en capítulos anteriores, tiene la siguiente información:

El archivo de puntajes de matemáticas mat.dat contiene los siguientes campos:

En lo que sigue supondremos que ambos archivos son lo suficientemente grandes como para que no quepan en la memoria del computador. A continuación resolveremos eficientemente el problema de generar un archivo con los tres campos de información, sin colocar previamente el contenido de un archivo en un arreglo.

Definición de clases de apoyo

Manipular los campos de información en un programa leyéndolos individualmente puede llegar a ser muy frágil. Es fácil equivocarse y olvidar un campo y se termina leyendo información errada. Por otra parte, aún cuando el programa funcione, más tarde puede ser necesario modificar la estructura del archivo agregando nuevos campos de información. Esto obliga a tener que cambiar todos los programas que usan ese archivo. Si se nos olvida cambiar uno, los resultados de ese programa estarán equivocados.

Por ello es conveniente definir para cada archivo una y sólo una clase que representa la información contenida en una línea del archivo. Para cada uno de los campos del archivo, la clase tiene una variable de instancia con su contenido. Los objetos se construyen a partir de un archivo o a partir de los valores de los campos. La clase suministra un método escribir para colocar el contenido del objeto en un archivo.

Por ejemplo, la clase Post permite representar el contenido de una línea del archivo post.dat:

    class Post {
      String ci= ""; // Los campos de una línea
      String nombre= "";
      Post(String ci, String nombre) {
        this.ci= ci;
        this.nombre= nombre;
      }
      // Lee del archivo los campos en el formato
      // ci:nombre
      Post(TextReader lect) {
        if (lect.eofReached())
          this.ci= null;
        else {
          this.ci= lect.readString();
          this.nombre= lect.readString();
          lect.skip();
        }
      }
      // Escribe los campos en el formato ci:nombre:cuenta
      void escribir(TextWriter escr) {
        escr.print(ci);
        escr.println(nombre);
      }
    }
Todos los programas que usen archivos con estos mismos campos usarán esta clase. Si se agregan o quitan campos a estos archivos, basta cambiar la definición de la clase para que la mayoría de los programas que usan esta estructura de archivos ya puedan usar el nuevo formato. Solo será necesario cambiar los programas que usan los campos que fueron suprimidos o que requieren utilizar los que se hayan agregado.

Ejercicio:

Escriba una clase similar para el archivo mat.dat. La clase se debe llamar Mat.

Bases de Datos

Una base de datos es un conjunto de archivos como los que hemos usado en los ejemplos. Cada archivo consiste en un conjunto de líneas y cada línea es un string con campos de información delimitados por un separador como ":". El número de campos es fijo.

Se elige esta organización porque todo problema de representación de información se puede llevar a una base de datos. Además cualquier problema de manipulación de la información se puede reducir a una combinación de los siguientes patrones:

Problemas más complejos se pueden resolver combinando estos patrones. Por ejemplo, si se necesita reunir la información que aparece en tres archivos, se hace primero un pareo entre los dos primeros y luego un pareo entre el resultado del primer pareo con el tercer archivo.

Ejemplo de selección:

Se necesita un archivo mat450.dat con el carnet de identidad y puntaje de las personas que obtuvieron más de 450 puntos en la prueba de matemáticas:

    TextReader lect= new TextReader("mat.dat", ":");
    TextWriter escr= new TextWriter("mat450.dat", ":");
    while (!lect.eofReached()) {
      Mat mat= new Mat(lect);
      if (mat.ptje>=450)
        mat.escribir(escr);
    }
    lect.close();
    escr.close();
Ejemplo de Proyección:

Los carnet de identidad y nombre de los alumnos que aparecen en post-mat.dat:

    TextReader lect= new TextReader("post-mat.dat", ":");
    TextWriter escr= new TextWriter("post-mat-proy.dat", ":");
    while (!lect.eofReached()) {
      PostMat postMat= new PostMat(lect);
      Post post= new Post(postMat.ci, postMat.nombre);
      post.escribir(escr);
    }
    lect.close();
    escr.close();

Pareo de archivos

El problema consiste en leer secuencialmente los archivos post.dat y mat.dat y producir un archivo post-mat.dat que contenga una línea por cada postulante que da la prueba de matemáticas con su nombre y su puntaje. La restricción más importante es que ninguno de los archivos cabe en la memoria del computador.

Archivo Campos Clase
post.dat ci, nombre Post
mat.dat ci, ptje Mat
post-mat.dat ci, nombre, ptje PostMat

El programa que realiza el pareo es:

    TextReader postLect= new TextReader("post.dat", ":");
    TextReader matLect= new TextReader("mat.dat", ":");
    TextWriter escr= new TextWriter("post-mat.dat", ":");
    Post post= new Post(postLect);
    Mat mat= new Mat(matLect);
    while (post.ci!=null && mat.ci!=null) {
      int cmp= compare(post.ci, mat.ci);
      if (cmp<0)
        post= new Post(postLect);
      else if (cmp>0)
        mat= new Mat(postMat);
      else {
        PostMat postMat=
          new PostMat(post.ci, post.nombre, mat.ptje);
        postMat.escribir(escr);
        post= new Post(postLect);
        mat= new Mat(matLect);
      }
    }
    escr.close();
    postLect.close();
    postLect.close();
(El programa completo se encuentra en Pareo.java. Los archivos de prueba son post.dat y mat.dat.)

Este programa lee una y solo una vez cada línea de los archivos de entrada y por lo tanto toma tiempo proporcional a la suma de las líneas en ambos archivos.

El problema que dejaremos pendiente es cómo ordenar este tipo de archivos. Todos los algoritmos de ordenamiento que hemos visto hasta el momento trabajan con arreglos. Luego veremos un algoritmo que permite ordenar archivos sin tener que leer todo su contenido en la memoria del computador.

Desde luego, en muchas ocasiones se pueden combinar los patrones sin tener que pasar por archivos intermedios. Por ejemplo se puede hacer un pareo que incorpore una selección y una proyección en una sola lectura de los archivos. Sin embargo, el acumular demasiados patrones puede hacer un programa completamente ilegible. ¡Nunca intente ahorrar líneas de programa combinando dos pareos en un sólo ciclo!

Eliminación de duplicados

No siempre los archivos contienen información consistente. Por ejemplo, es común encontrarse con archivos de cuentas en donde una persona aparece 2 o más veces. En algunas organizaciones esto no tiene sentido y es necesario programar herramientas que permitan detectar este tipo de situaciones.

El siguiente programa lee el archivo post.dat y produce 2 archivos: uno contiene las personas que aparecen una sola vez (unicos.dat) y el otro almacena las que aparecen 2 o más veces (dups.dat). Por ejemplo si el archivo fuese:

post.dat
------------
10000:Pedro
20000:Diego
20000:Diego
30000:Juan
60000:Sutano
80000:Megano
80000:Megano
Los archivos producidos serán:

unicos.dat            dups.dat
----------            --------
10000:Pedro           20000:Diego
30000:Juan            20000:Diego
60000:Sutano          80000:Megano
                      80000:Megano
El programa supone que el archivo está ordenado por carnet de identidad.

        TextReader lect= new TextReader("post.dat");
        TextWriter escr= new TextWriter("unicos.dat");
        TextWriter escrDup= new TextWriter("dups.dat");
        Post post= new Post(lect);
        while (post.ci!=null) {
          Post sgte= new Post(lect);
          if (sgte.ci==null || compare(post.ci, sgte.ci)!=0)
            post.escribir(escr);
          else {
            post.escribir(escrDup);
            while(sgte.ci!=null && compare(post.ci, sgte.ci)==0) {
              sgte.escribir(escrDup);
              sgte= new Post(lect);
            }
          }
          post= sgte;
        }
        lect.close();
        escr.close();
        escrDup.close();

Ejercicio propuesto:

Escriba completamente uno o más programas que entreguen los nombres de los 20000 mejores puntajes en la prueba de matemáticas. Su programa debe ser eficiente en tiempo de ejecución.

Indicación: