Iteración y Conjuntos de Objetos: Arreglos y Vectores en Java (Arrays and Vectors in Java, Spanish only)

La mayoría de veces los programas no trabajan con datos aislados. En este articulo se explican las varias estrategias que podemos utilizar para almacenar y procesar agrupaciones de objetos.

Liked it? !

Antes de leer este artículo se recomienda haber leído Trabajando con Múltiples Objetos: Ciclos.

Índice

1. Ciclo for
2. Indexación Usando Vectores
   1. Introducción
   2. Primer Ejemplo
   3. Búsquedas
   4. Vectores Auto-Organizables: Algoritmos de Reordenamiento
      1. Algoritmo de Mover al Principio
      2. Trasponer
3. Arreglos
   1. Introducción
   2. Declaración y Creación de los Arreglos
   3. Elementos del Arreglo
   4. Ejemplo completo de Arreglos
   5. Vectores o Arreglos?
   6. Arreglos Multidimensionales
4. Sentencia Break y Continue
5. Argumentos desde la Línea de Comandos
6. Hileras e Índices

1. Ciclo for

   Java lo provee como una alternativa al ciclo while. Es utilizado para contar repeticiones. Su forma es:

   for (inicializacion; condición de ciclo; paso) cuerpo

   Supongamos que queramos desplegar los números de 1 a 20:

   int i; for (i=1; i<=20; i++) System.out.println(i);

   La inicialización no necesariamente es una asignación simple. Podemos llevar a cabo varias asignaciones separando estas por comas. Por ejemplo, supongamos que queramos calcular y desplegar la suma de todos los enteros entre 1 y 20:

   int i, suma; for (i=1, suma=0; i<=20; i++) suma+=i; System.out.println(suma);

   El paso no necesariamente es un simple incremento, también puede ser una secuencia de enunciados separados por coma. Por ejemplo, supongamos que queramos desplegar la tabla de potencias de dos entre 0 y 20:

   int i, powOf2; for (i=0, powOf2=1; i<=20; i++, powOf2<<=1) System.out.println(2 + "^" + i + "=" + powOf2);

    

2. Indexación Usando Vectores

   1. Introducción

      Un Vector hace mas que mantener una colección de referencias a objetos, las mantiene en un orden en particular. El primer elemento agregado al Vector se almacena en la posición 0, el siguiente agregado se almacena en la posición 1, el siguiente en la posición 2 y así sucesivamente. Cada una de las posiciones es numerada comenzando desde 0. Ha esta numeración de posiciones se le llama indexación. Un índice es un entero utilizado para indicar la posición de un elemento en una colección como el Vector. Para utilizar la referencia almacenada en una posición en particular, utilizamos el método elementAt de la clase Vector, que recibe el índice como argumento. Por ejemplo si quisiéramos desplegar la referencia almacenada en la posición 2 de un Vector v escribimos el siguiente código:

      System.out.println(v.elementAt(2));

      El objeto Vector lleva la cuenta de los elementos que se van agregando, y se puede acceder a esta información a través del método size de la clase Vector. Por ejemplo, para desplegar el tamaño de un Vector v lo podemos hacer a través de el código:

      System.out.println(v.size());

      Recuerde que la posición del primer elemento del Vector comienza en 0, por lo que la posición del ultimo elemento esta dada por:

      v.size()-1

       

   2. Primer Ejemplo: Encontrando la Mediana

      Supongamos que tenemos un archivo, llamado numeros.txt que contiene una lista de números ordenados ascendentemente. Queremos calcular la mediana de estos números (el numero que esta en medio). Por simpleza, asumamos que hay un numero impar de números.

      Si leemos todos los números del archivo, almacenándolos en un Vector v, podemos calcular el índice del elemento que contiene la mediana como:

      v.size()/2

      Podemos utilizar este valor con elementAt, para acceder e imprimir el elemento de esta posición, que corresponde a la mediana:

      System.out.println(v.elementAt(v.size()/2));

      El programa completo quedaría:

      class Mediana { public static void main (String args[]) throws Exception { BufferedReader br = new BufferedReader (new InputStreamReader(new FileInputStream ("nombres.txt"))); Vector v = new Vector(); String s; while ((s = br.readLine()) != null) v.addElement(s); System.out.println(v.elementAt(v.size()/2)); } }

      Ejercicios de clase:

      1. Reescriba la clase Mediana eliminando la restricción de que sean un numero de valores impares. En vez de esto, cuando el numero de valores es par, la mediana es el promedio de los valores medios.
      2. Dado un Vector v que contiene referencias a hileras, escriba el código para imprimir todas las permutaciones de las hileras.

       

   3. Búsquedas

      El siguiente ejemplo que vamos a desarrollar es la búsqueda de un elemento en una colección. Ya hemos hecho una búsqueda en el método contains de la clase Conjunto, que devolvía verdadero si el elemento estaba en el Conjunto y falso de lo contrario. Habrán dos diferencias con la búsqueda que implementaremos ahora:

      1. En vez de usar un Enumeration, haremos la búsqueda directamente sobre el Vector (usando el método elementAt).
      2. En vez de devolver verdadero o falso si el elemento se encontró devolveremos la posición del elemento si se encuentra y -1 de lo contrario. Podemos usar -1 ya que este no representa ninguna posición real

      La implementación quedaría así:

      private int search (Object o) { int k; for (k=0; k<v.size(); k++) if (o.equals(v.elementAt (k)) return k; return -1; }

      Se pudo también haber utilizado el ciclo while, de la siguiente manera:

      private int search (Object o) { int k; while (k<v.size() && !o.equals(v.elementAt (k))) k++; if (k<v.size()) return k; else return -1; }

      La condición

      k<v.size() && !o.equals(v.elementAt (k))

      no da problema ya que los operadores lógicos se evalúan usando short-circuit evaluation. Si se hubiera tenido por ejemplo:

      k<v.size() & !o.equals(v.elementAt (k))

      si hubiera presentado problema para cuando se hacen búsquedas de elementos que no están en el Vector, ya que después de haber realizado la ultima iteración al verificar la condición de ciclo (cuando k ya es igual a v.size()), aunque la expresión

      k<v.size()

      se evalúa falso, de todos modos evalúa la otra expresión

      !o.equals(v.elementAt (k))

      la cual levantaría una excepción ya que se esta accediendo una posicion del Vector invalida.

      De hecho hay incluso otra forma de estructurar el ciclo, que es utilizando la palabra reservada break. Esta es utilizada para romper un ciclo. Cuando se llega el enunciado al break el control se pasa hacia afuera del ciclo. La búsqueda me quedaría entonces así:

      private int search (Object o) { int k; while (k<v.size()) { if (o.equals(v.elementAt (k)) break; k++; } if (k<v.size()) return k; else return -1; }

      Desarrollaremos el break mas adelante en el tema.

      Ejercicio de clase: Escriba un método vsearch que reciba un Vector de parámetro. El método deberá devolver el índice del elemento en el Vector miembro v que coincida con algún elemento del Vector que recibe de parámetro.

       

   4. Vectores Auto-Organizables: Algoritmos de Reordenamiento

      Generalmente no todos los elementos de una colección se buscan con la misma frecuencia. De hecho, en la vida real la mayoría de elementos los buscamos en raras ocasiones y la mayoría del tiempo buscamos un pequeño subconjunto de los elementos del conjunto.

      Si pudiéramos almacenar los elementos mas requeridos cerca del principio del Vector, esto nos aceleraría muchísimo la búsqueda. El primer paso en el almacenamiento de los elementos mas requeridos del vector cerca del inicio es identificarlos. Una estrategia es que cuando el método search encuentre un elemento, es probable que este sea un candidato a los elementos mas requeridos, por lo que debe ser movido hacia arriba en el Vector. Pero como exactamente llevar a cabo este movimiento?

       

   1. Algoritmo de Mover al Principio

      Una aproximación seria mover el elemento encontrado en la posición k al principio del Vector. Esto requeriría de dos pasos:

      • Insertar una copia de la referencia del elemento en la posición 0. La copia se convertiría en la nueva posición 0, y el resto de elementos se correrían una posición hacia abajo (el elemento de la antigua posición 0 se movería a la posición 1, el elemento de la antigua posición 1 se movería a la posición 2, etc.).
      • Eliminar el elemento encontrado de la posición k (pero ojo, ahora seria k+1, por el corrimiento de todos los elementos)

      La clase Vector provee métodos para llevar a cabo cada paso. Para insertar un elemento en una posición determinada (corriendo el resto de elementos hacia abajo) la clase Vector provee el método insertElementAt. Para eliminar un elemento de una posición especifica la clase Vector provee el método removeElementAt. Podemos entonces escribir el método ayudante para llevar a cabo estas dos acciones:

      private void moveToFront (Vector v, int k) { v.insertElementAt (v.elementAt(k), 0); v.removeElementAt (k+1); }

      Con esto podemos reescribir nuestro metodo search:

      private int search (Object o) { int k; for (k=0; k<v.size(); k++) if (o.equals(v.elementAt (k)) { moveToFront (v, k); return 0; } return -1; }

       

   2. Trasponer

      Una desventaja del esquema de mover al principio es que cuando se accede un elemento relativamente infrecuente, este es movido hacia arriba. Este esquema sobre-reacciona en este sentido. Una alternativa menos drástica para cuando se acceda un elemento, podría ser únicamente trasponerlo al que esta antes de él. De esta forma los elementos mas accedidos van subiendo lentamente y los menos accedidos van bajando lentamente. Por lo que reemplazamos el método ayudante moveToFront por el método ayudante:

      private void transpose (Vector v, int k) { if (k!=0) { v.insertElementAt (v.elementAt (k), k-1); v.removeElementAt (k+1); } }

      Hay un alto costo de correr todos los elementos hacia arriba y hacia abajo (a través de insertElementAt y removeElementAt). Podemos hacer mas eficiente la transposición utilizando el metodo setElementAt de la clase Vector.

      El método setElementAt asigna un elemento a una posición en particular, sin causar que otros elementos se muevan. Este método es verdaderamente una asignación: hace que le caiga encima a lo que estaba antes en esa posición. Modificando el método transpose para incluir esta optimización quedaría:

      private void transpose (Vector v, int k) { if (k!=0) { Object objK = v.elementAt (k); Object objPrevK = v.elementAt (k-1); v.setElementAt (objPrevK, k); v.setElementAt (objK, k-1); } }

      Ejercicios de clase:

      • moveToFront pasa los elementos mas requeridos hacia la parte superior del Vector rápidamente, pero sobre-reacciona moviendo a los elementos referidos ocasionalmente inapropiadamente hacia arriba. traspose no deja que los elementos referidos ocasionalmente provoquen mucho daño pero es lento para mover los elementos requeridos frecuentemente hacia arriba, ya que avanza una posición a las vez. Un intento de obtener lo mejor de ambos enfoques es no subir los elementos mas requeridos hasta arriba ni de uno en uno, sino hasta la mitad. Implemente el método moveHalfwayUp que tome el elemento encontrado en la posición k y que lo mueva a la posición k/2.
      • Que otro enfoque se le ocurre para acelerar el proceso de búsqueda de los elementos mas frecuentes?

    

3. Arreglos

   1. Introducción

      Un arreglo es una estructura que provee el lenguaje que utiliza índices para soportar colecciones de datos. Comparte muchas características con el Vector:

      1. Consiste de una o mas posiciones.
      2. Cada posición esta indexada por un entero.
      3. El índice de la primera posición es 0.
      4. Tiene que ser declarado con el operador new.
      5. Es un objeto.
      6. Es accedido usando una variable de referencia.

      También hay algunas diferencias entre los dos:

      1. Un arreglo no es una clase. No esta definido en la librería de clases. Esta incorporado dentro del lenguaje mismo.
      2. No hay "métodos del arreglo" para trabajar con el arreglo o sus elementos; en vez de esto, el lenguaje nos provee de algunos operadores para permitirnos acceder los elementos del arreglo.
      3. El arreglo tiene un campo llamado length que indica el numero de elementos del arreglo; en contraste con el Vector, que utiliza un método, size, que provee esta información.
      4. Los elementos de un arreglo puede sostener datos primitivos así como referencias a objetos.
      5. El tipo de los elementos de un arreglo debe de ser especificado en la declaración del arreglo. Todo lo que se almacene en sus elementos debe de ser de este tipo.
      6. Los arreglos no pueden crecer. Una vez que el arreglo ha sido creado, tiene un numero fijo de elementos.

       

   2. Declaración y Creación de los Arreglos

      Para declarar variables de referencia a un arreglo, se escribe el tipo del que queremos que sean los elementos, seguido por un par de corchetes vacíos y después el nombre de la variable de referencia. Algunos ejemplos:

      // referencia a un arreglo cuyos elementos son int int [] numerosLoteria; // referencia a un arreglo cuyo elementos son una referencia a un String String [] ganadores;

      De hecho, hemos estado viendo declaraciones de esta forma desde el primer tema: el parámetro de main es String [] args. Estas declaraciones no crean arreglos, solo variables que los pueden referir.

      Para crear un arreglo usamos el operador new, seguido del tipo de los elementos y un par de corchetes encerrando a un entero que representa el numero de elementos que el arreglo va a tener. Por ejemplo si queremos que numerosLoteria haga referencia a un arreglo de 6 posiciones escribimos:

      numerosLoteria = new int[6];

      Ahora la expresion

      numerosLoteria.length

      es 6. Al igual que con vectores, esta no es una posición valida: ya que los arreglos comienzan de 0.

       

   3. Elementos del Arreglo

      Para acceder a los elementos del arreglo, escribimos el nombre del arreglo seguido por la posición que deseamos entre corchetes. Por ejemplo

      numerosLoteria[3] = 12345;

      asigna el numero 12345 a la posición 3 del arreglo referenciado por numerosLoteria.

      Java verifica que el indice este en el rango valido. Si no lo esta genera un ArrayIndexOutOfBoundsException.

       

   4. Ejemplo completo de Arreglos

      Escriba un programa que lea 10 números del teclado y a continuación los despliegue en orden inverso:

      import java.io.*; class EnterosReversa { public static void main(String[] args) throws Exception { BufferedReader keyb = new BufferedReader(new InputStreamReader(System.in)); int[] z = new int [10]; int i; for (i=0; i<10; i++) z[i] = Integer.parseInt (keyb.readLine()); for (i=9; i>=0; i--) System.out.println (z[i]); } }

      Ejercicio de clase: resuelva un sistema de n ecuaciones lineales con n variables utilizando Gauss-Jordan completando los métodos de la clase GaussJordan y Ecuación.

       

   5. Vectores o Arreglos?

      Los arreglos ofrecen tres ventajas sobre el Vector:

      1. Pueden almacenar directamente tipos de datos primitivos como el int.
      2. Sus elementos pueden ser accedidos sin necesidad de mandar un mensaje, por lo que el código es mas rápido que si se usara un Vector
      3. Como los arreglos son tipados, ofrecen una verificación en tiempo de compilación que no la tiene el Vector. Si almacenamos accidentalmente un objeto Nombre en un Vector donde tenemos almacenados objetos de Camion, Java lo permite. Pero Java nos daría un error de compilación si tratamos de almacenar un Nombre en un arreglo de referencias a Camion. A pesar de que no nos guste el error, nos permite encontrar nuestra equivocación tempranamente.

      Sin embargo, los arreglos también presentan algunas desventajas sobre el Vector:

      1. Son de tamaño fijo y no crecerán.
      2. No nos ofrece un conjunto de operaciones ricas como la clase Vector (a través de métodos como insertElementAt).

      Ejercicio de clase

      Escriba un método insertElementAt que reciba de argumentos un arreglo de enteros, un índice y un numero entero. El método deberá devolver un nuevo arreglo de enteros con el numero insertado en la posición recibida de índice (y el resto de numero a partir de esta posición corridos en uno hacia abajo.
      Pista: cree un arreglo nuevo con el numero de posiciones del arreglo original mas uno. Llénelo con los valores apropiados y devuélvalo.

       

   6. Arreglos Multidimensionales

      A pesar que Java no soporta arreglos de mayores dimensiones, si soporta arreglos de arreglos:

      int [][]mat = new int[3][4]; // matriz de 3 filas y cuatro columnas

      Además que se puede pedir memoria para cada columna por separado, inclusive de diferente tamaño!

      int i, [][]triangulo = new int [5][]; for (i=0; i <5; i++) triangulo[i]="new" int[i]; // cada columna de diferente tamano!

      Ejercicio de clase

      • Escriba una clase PascalTriangle que reciba el numero de filas a través del constructor e incluya un método toString() que devuelva el triangulo de pascal correspondiente en una hilera. Por ejemplo, el código: PascalTriangle pt = new PascalTriangle(5); System.out.println (pt);

        Debería desplegar:

        1 1 1 1 2 1 1 3 3 1 1 4 6 4 1 1 5 10 10 5 1

        Pista: internamente almacene el triangulo en un arreglo de arreglos (sin desperdiciar memoria!). Además recuerde que la nueva línea es representado por el caracter '\n'.

      • Resuelva un sistema de n ecuaciones lineales con n variables utilizando Cramer completando los métodos de la clase Cramer.

       

4. Sentencia Break y Continue

   Las palabras reservada break es utilizada para romper un for, while y switch. Hay dos formas de utilizarla. La forma simple pasa el control hacia afuera de la estructura, como fue ilustrado en el ejemplo de búsqueda. También puedo usar el break para salir de varios estructuras anidados a través de la etiquetación. Por ejemplo:

   outaHere: for (i=0; i< RowSize; i++) for (j=0; j<ColSize; j++) { if (denom[i]==0) break outaHere; mat[i][j]/=denom[i]; }

   continue provoca que el flujo de ejecución se lleve a la próxima iteración. Únicamente funciona en el for y el while (no opera en el switch). También puede ser etiquetado y pasaría a la siguiente iteración del ciclo etiquetado.

    

5. Argumentos desde la Línea de Comandos

   En el desarrollo del curso hemos estado declarando el parámetro del método main de las aplicaciones con una referencia a un arreglo de hileras:

   public static void main (String []args)

   El parámetro args corresponde a los argumentos de la linea de comando de la aplicación. Estas son hileras que son proveídas cuando el programa ejecutado. Por ejemplo la ejecución

   java program perro casa camion

   Esto le pediría a la maquina virtual de java que ejecute el program mandándole los argumentos perro, casa y camion. El arreglo args tendrá entonces los siguientes valores:

   args[0] es "perro" args[1] es "casa" args[2] es "camion"

   En un ambiente de línea de comandos, esta es una forma muy conveniente de permitir al usuario proveer información básica a una aplicación o utilitario

   Tomemos como ejemplo un programa que copia las líneas de un archivo a otro, recibiendo el nombre del los archivos desde la línea de comandos:

   import java.io.*; class CopyFile { public static void main (String [] args) throws Exception { if (args.length<2) System.out.println ("Sintaxis: java CopyFile archivo-origen archivo-destino"); else { BufferedReader in = new BufferedReader (new InputStreamReader(new FileInputStream (args[0]))); PrintStream out = new PrintStream (new FileOutputStream (args[1])); String s; while ((s = in.readLine()) != null) out.println (s); } } }

   Ejercicio de clase

   1. Escribir un programa que reciba un argumento desde la línea de comandos que especifica el nombre de un archivo. A continuación el programa deberá eliminar dicho archivo
   2. Escribir un programa que recibe uno o mas argumentos desde la línea de comandos, cada uno el nombre de un archivo. A continuación el programa deberá de desplegar el nombre de cada archivo seguido por el contenido de dicho archivo.

    

6. Hileras e Índices

   Mucho de lo que hemos aprendido en este tema es aplicable para los objetos de tipo String. Esto es porque un String es una secuencia de caracteres cuyas posiciones pueden ser identificadas con un entero. Al igual que con los arreglos y los objetos de tipo Vector, los String son indexados comenzando desde la posición 0.

   La clase String provee un método charAt (análogo a elementAt de la clase Vector) que devuelve el carácter localizado en un índice en particular:

   char c="abcdefg".charAt(3);

   Esto asigna el valor d al char c. El tipo de dato primitivo char nos permite la representación de mas de 64000 caracteres distintos incluidos el alfabeto occidental, numerales, signos de puntuación así como conjuntos de caracteres de todo el mundo (Han, Arábigo, Cirilico, Griego, Hebreo, Katakana, Tamil, Etiopiano, Braille, Cherokee, para mencionar algunos).

   Para ilustrar como podríamos manipular el String a nivel de caracteres, supongamos que queramos determinar el String s1 es prefijo del String s2:

   int k; while (k < s1.length() && k < s2.length() && s1.charAt(k)==s2.charAt(k)) k++; Boolean isAPrefix = k==s1.length();

   No es casualidad de que vea similar la estructura de este ciclo a la búsqueda secuencial en arreglos o vectores. Esto es porque todas estas estructuras son colecciones indexadas.

   Dado que la clase String ya provee un conjunto de métodos tan rico para el procesamiento de hileras, la necesidad de utilizar este tipo de ciclos indexados es mínima. Por ejemplo, el método startsWith hace la mismo que el código que escribimos. El código podría estar res

   boolean isAPrefix = s2.startWith(s2);

Siguiente articulo que se recomienda leer: Extendiendo el Comportamiento de las Clases: Herencia

Etiquetas de technorati: java

Liked it? !