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
...
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.
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:
class Post {
String ci;
String nombre;
int ptje;
}
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).
Post post= new Post();
post.ci= "11478387-1";
post.nombre= "Fuenzalida Perez Alberto";
post.ptje= 715;
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.
Post[] posts= new Post[100];
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:
En este caso, los paréntesis son (), pues se desea crea un objeto.
int i=0;
while (i<100) {
posts[i]= new Post();
i= i+1;
}
El siguiente programa lee el archivo post.dat y construye un arreglo con la información:
Las 5 líneas primeras líneas del ciclo while se pueden escribir también
de la siguiente forma:
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;
}
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.
posts[i]= new Post();
posts[i].ci= lect.readString();
posts[i].nombre= lect.readString();
posts[i].ptje= lect.readInt();
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:
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.
Post aux= posts[i];
posts[i]= posts[j];
posts[j]= aux;
También se podría haber hecho:
Pero esto es claramente más trabajo que lo anterior.
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;
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 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;
}
}
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;
}
}
Por ejemplo, la clase Cuenta permite representar el contenido de una línea del archivo cuentas.dat:
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.
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);
}
}
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();
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:
Los archivos producidos serán:
cuentas2.dat
------------
10000:Pedro:100
20000:Diego:104
20000:Diego:104
30000:Juan:101
60000:Sutano:107
80000:Megano:109
80000:Megano:110
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.
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
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();