Procesamiento Masivo de Datos

Objetivos: Mostrar como se pueden usar las clases para agrupar datos en una sola entidad que puede ser manipulada como un solo dato compuesto.

Temas:

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

Temas:


Ejercicio

Se tiene un archivo post.dat con los postulantes a las universidades chilenas. Cada línea de este archivo contiene el carnet de identidad (c.i.) y el nombre de un postulante en el siguiente formato:

    11478387-1:Fuenzalida Perez Alberto
    12245894-7:Fernandez Henriquez Pedro
    ...
El archivo se encuentra ordenado por carnet de identidad. El problema consiste en ordenar el archivo por apellidos y nombres de los postulantes, siguiendo el orden lexicográfico.

Primera solución:

Colocar toda la información en dos arreglos de strings. El primero (cis) contiene los carnets de identidad y el segundo (nombres) los nombres. De esta forma nombres[i] es el nombre del postulante con carnet de identidad cis[i]. Es crucial preservar esta relación al realizar el ordenamiento.

Luego, se ordena el arreglo de nombres mediante cualquiera de los algoritmos vistos anteriormente. Para preservar la asociación entre valores en el arreglo nombres y valores en el arreglo cis, cada vez que se hace un intercambio en el arreglo nombres, el mismo intercambio se reproduce en el arreglo cis.

Observe que en este problema, el hecho de que el archivo esté ordenado por carnet de identidad no significa nada. Es lo mismo que el arreglo esté desordenado.

Desventaja:

Supongamos que en el archivo se encuentra también el puntaje en la PAA. Si se desea ordenar el archivo, hay que crear 3 arreglos y al ordenar, hay que intercambiar simultáneamente en los 3 arreglos. Si tenemos n campos de información en el archivo, hay que crear n arreglos e intercambiar en todos los arreglos. Desde luego, esto sería demasiado incómodo. En esta clase veremos una mejor solución.


Uso de objetos como records

Un record es la agrupación de un conjunto de datos en una sola estructura que puede ser manipulada como un solo dato o también a través de sus partes. En Java, estas agrupaciones se realizan mediante la definición de clases. Por ejemplo, para almacenar la información relativa a un postulante se puede definir la siguiente clase:

    class Post {
      String ci;
      String nombre;
      int ptje;
    }
Los objetos de esta clase son records que agrupan la información de un postulante. Para crear un record, procedemos simplemente a crear un objeto de la clase Post e inicializar todos sus variables de instancia:

    Post post= new Post();
    post.ci= "11478387-1";
    post.nombre= "Fuenzalida Perez Alberto";
    post.ptje= 715;
Como veremos a continuación, esto es especialmente útil para ordenar un archivo, porque su información se puede almacenar en un solo arreglo, en donde cada elemento tiene todos los campos de información (no solo uno).


Arreglos de objetos

Así como en Java se pueden crear arreglos de enteros, reales y strings, también es posible crear arreglos de objetos. Por ejemplo:

    Post[] posts= new Post[100];
Crea un arreglo de 100 referencias a objetos de la clase Post. Observe que los paréntesis son [ ]. Si se usara (100), se estaría creando una instancia de Post, no un arreglo.

Por otra parte, así como post referencia un objeto, posts[i] también referencia un objeto. Por lo tanto, si se desea usar este arreglo, es necesario crear 100 objetos. Por ejemplo:

    int i=0;
    while (i<100) {
      posts[i]= new Post();
      i= i+1;
    }
En este caso, los paréntesis son (), pues se desea crea un objeto.

El siguiente programa lee el archivo post.dat y construye un arreglo con la información:

    int npost= ...; // el numero de postulantes en el archivo
    Post[] posts= new Post[npost];
    TextReader lect= new TextReader("post.dat", ":");
    int i= 0;
    while (!lect.eofReached()) {
      Post post= new Post();
      post.ci= lect.readString();
      post.nombre= lect.readString();
      post.ptje= lect.readInt();
      posts[i]= post;
      lect.skip();

      i= i+1;
    }
Las 5 líneas primeras líneas del ciclo while se pueden escribir también de la siguiente forma:

    posts[i]= new Post();
    posts[i].ci= lect.readString();
    posts[i].nombre= lect.readString();
    posts[i].ptje= lect.readInt();
La variable posts es un arreglo de objetos de la clase Post. Dado que la clase en sí no posee métodos ni constructores, en este caso diremos que la clase es simplemente un record. Su único objetivo es agrupar información para manejarla como un todo.

Por ejemplo, si se desea intercambiar el postulante que se encuentran en la i-ésima posición con el que se encuentra en la j-ésima posición basta ejecutar:

    Post aux= posts[i];
    posts[i]= posts[j];
    posts[j]= aux;
Es decir se realiza un solo intercambio. Esto se puede hacer porque posts[i] es un objeto compuesto por de 3 ítemes: c.i., nombre y puntaje. Pero este objeto se puede manipular como un solo dato.

También se podría haber hecho:

    String aux= posts[i].ci;
    posts[i].ci= posts[j].ci;
    posts[j].ci= aux;
    aux= posts[i].nombre;
    posts[i].nombre= posts[j].nombre;
    posts[j].nombre= aux;
    int aux2= posts[i].ptje;
    posts[i].ptje= posts[j].ptje;
    posts[j].ptje= aux;
Pero esto es claramente más trabajo que lo anterior.


Ordenamiento de arreglos de objetos

Ahora, procedemos a ordenar el arreglo de postulantes por nombre. Para realizar este ordenamiento, no es necesario pensar un nuevo algoritmo. Sólo se modifica ligeramente cualquiera de los algoritmos anteriores. Por ejemplo, podemos partir del algoritmo de la burbuja:

    void burbuja(int[ ] a, int n) {
      int iult= n-1;
      boolean cambio= true;
      while (cambio) {
        int i= 0;
        cambio= false;
        while (i<iult) {
          if (a[i]>a[i+1]) {
            // intercambiar
            int aux= a[i];
            a[i]= a[i+1];
            a[i+1]= aux;
            cambio= true;
          }
          i= i+1;
        }
        iult= iult-1;
      }
    }
Lo único que hay que cambiar son las partes que están remarcadas. Es decir el tipo del arreglo que se debe ordenar, la comparación entre los elementos del arreglo y el tipo de la variable auxiliar que se usa para intercambiar dos elementos:

  
    void ordenaPosts(Post[ ] a, int n) {
      int iult= n-1;
      boolean cambio= true;
      while (cambio) {
        int i= 0;
        cambio= false;
        while (i<iult) {
          if (compare(a[i].nombre,a[i+1].nombre)>0) {
            // intercambiar
            Post aux= a[i];
            a[i]= a[i+1];
            a[i+1]= aux;
            cambio= true;
          } 
          i= i+1;
        }   
        iult= iult-1;
      }   
    }     

Definición de clases de apoyo

A menudo varios archivos poseen la misma estructura, es decir los mismos campos. Para simplificar la manipulación de estos archivos es conveniente definir para cada estructura distinta de 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 Cuenta permite representar el contenido de una línea del archivo cuentas.dat:

    class Cuenta {
      String ci= ""; // Los campos de una línea
      String nombre= "";
      String cuenta= "";
      Cuenta(String ci, String nombre, String cuenta) {
        this.ci= ci;
        this.nombre= nombre;
        this.cuenta= cuenta;
      }
      // Lee del archivo los campos en el formato
      // ci:nombre:cuenta
      Cuenta(TextReader lect) {
        String lin= lect.readLine();
        if (!lect.eofReached()) {
          FieldParser decod= new FieldParser(lin, ":");
          ci= decod.readString();
          nombre= decod.readString();
          cuenta= decod.readString();
        }
      }
      // Escribe los campos en el formato ci:nombre:cuenta
      void escribir(TextWriter escr) {
        escr.println(ci+":"+nombre+":"+cuenta);
      }
    }
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.

Solución para el pareo de archivos

El problema consiste en leer secuencialmente los archivos cuentas.dat y saldos.dat y producir un archivo saldos-cuentas.dat que contenga las cuentas que aparecen en ambos archivos. La siguiente tabla muestra para cada archivo los campos que contiene y la clase que permite manipular sus líneas:

Archivo Campos Clase
cuentas.dat ci, nombre, cuenta Cuenta
saldos.dat cuenta, saldo Saldo
cuentas-saldos.dat ci, nombre, cuenta, saldo CuentaSaldo

El programa que realiza el pareo es:

    TextReader lect= new TextReader("cuentas.dat");
    TextReader saldosLect= new TextReader("saldos.dat");
    TextWriter escr= new TextWriter("cuentas-saldos.dat");
    Saldo sal= new Saldo(saldosLect);
    Cuenta cuen= new Cuenta(lect);
    while (!lect.eofReached() && ! saldosLect.eofReached()) {
      int cmp= compare(cuen.cuenta, sal.cuenta);
      if (cmp<0)
        cuen= new Cuenta(lect);
      else if (cmp>0)
        sal= new Saldo(saldosLect);
      else {
        CuentaSaldo cuenSal=
          new CuentaSaldo(cuen.ci, cuen.nombre,
                          cuen.cuenta, sal.saldo);
        cuen.escribir(escr);
        cuen= new Cuenta(lect);
        sal= new Saldo(saldosLect);
      }
    }
    escr.close();
    lect.close();
    saldosLect.close();

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 cuentas.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:

cuentas2.dat
------------
10000:Pedro:100
20000:Diego:104
20000:Diego:104
30000:Juan:101
60000:Sutano:107
80000:Megano:109
80000:Megano:110
Los archivos producidos serán:

unicos.dat                dups.dat
----------                --------
10000:Pedro:100           20000:Diego:104
30000:Juan:101            20000:Diego:104
60000:Sutano:107          80000:Megano:109
                          80000:Megano:109
El programa supone que el archivo está ordenado por carnet de identidad. Más tarde examinaremos cómo es posible ordenar archivos cuando caben en memoria.

        TextReader lect= new TextReader("cuentas2.dat");
        TextWriter escr= new TextWriter("unicos.dat");
        TextWriter escrDup= new TextWriter("dups.dat");
        Cuenta cuen= new Cuenta(lect);
        while (!lect.eofReached()) {
          Cuenta sgte= new Cuenta(lect);
          if (compare(cuen.ci, sgte.ci)!=0)
            cuen.escribir(escr);
          else {
            cuen.escribir(escrDup);
            while(compare(cuen.ci, sgte.ci)==0) {
              sgte.escribir(escrDup);
              sgte= new Cuenta(lect);
            }
          }
          cuen= sgte;
        }
        lect.close();
        escr.close();
        escrDup.close();