Estructura de Datos : Vectores

Los vectores son estructuras de datos similares a los arreglos, pero más desarrollados, ya que entre otras cosas, crecen y decrecen dinámicamente, según se necesite. En algunos lenguajes, el tamaño de un arreglo queda fijo en tiempo de compilación. En otros lenguajes, la dimensión del arreglo, queda fijada en tiempo de ejecución. No obstante, una vez fijada, no puede alterarse. La real necesidad es que la estructura de datos pueda ajustar su capacidad dinámicamente durante todo el tiempo de ejecución. En ingles esta estructura de datos es vectors.

La estructura de datos que puede crecer y decrecer dinámicamente, en todo momento, según las exigencias de ejecución se llama vector. La estructura de datos vector representa un conjunto de objetos. El conjunto de objetos es de tamaño variable. Se incorporan objetos hasta colmar la capacidad total del vector. Cuando se requiera incorporar un nuevo objeto en un vector lleno, el vector se expande automáticamente, según la capacidad incremental definida. La capacidad inicial, por default, es 10. La capacidad incremental, por default, es el doble de la existente en el momento de la expansión. Si no se desea este crecimiento exponencial, se puede especificar la capacidad incremental, y en esa capacidad crecerá el vector cada vez que se expanda. Cuando la capacidad del vector está agotada, el vector se redimensiona y se reubica automáticamente. La redimensión del vector acontece como se mencionó más arriba, según se haya explicitado o nó una capacidad incremental. En el momento de la redimensión se crea un nuevo vector. A continuación se reubican todos los elementos del vector viejo, copiandolos en el nuevo, para finalmente ubicar el nuevo elemento que provocó la expansión, en el vector nuevo.

Reparar que la estructura de datos vector es absolutamente general al almacenar objetos. En comparación, los arreglos son estructuras de datos de un solo tipo, por ejemplo un arreglo de enteros. Los vectores, al ser conjuntos de objetos pueden contener objetos de los más diversos tipos. Así podemos definir a un vector como el almacenamiento de una secuencia de objetos.

Representaciones

|<------------------------------------ Capacidad ------------------------------------>|
                                         Total

|<------------------------------ Capacidad ---------------------------->|< Capacidad >|
                                   Usada                                     Libre

|<---------------- Capacidad ---------------->|<--- Capacidad --->|<--- Capacidad --->|
                    Inicial                        Incremental         Incremental

*-------------------------------------------------------------------------------------*
|X|X|X|X|X|X|X|X|X|X|X|X|X|X|X|X|X|X|X|X|X|X|X|X|X|X|X|X|X|X|X|X|X|X|X|X| | | | | | | |
*-------------------------------------------------------------------------------------*
                          A                                             A
                          |                                             |
      Indice -------------+         X = Elemento        Posicion -------+
                                                         Libre

Interfases

Interfase 1

crearVector(vector)
      crearVector(capacidadInicial, vector)
      crearVector(capacidadInicial, capacidadIncremental, vector)

      averiguarCapacidadTotal(vector, capacidad)
      averiguarCapacidadUsada(vector, capacidad)
      averiguarCapacidadLibre(vector, capacidad)

      averiguarVectorVacio(vector, boolean)

      modificarCapacidadTotal(vector, capacidad, vector)
      modificarCapacidadIncremental(vector, capacidad, vector)

      agregarElementoComienzo(vector, elemento, vector)
      agregarElementoFinal(vector, elemento, vector)
      agregarElementoPosicion(vector, posicion, elemento, vector)

      eliminarElementoComienzo(vector, vector)
      eliminarElementoPosicion(vector, posicion, vector)
      eliminarElementoFinal(vector, vector)
      eliminarElementoRango(vector, posicionDesde, cantidad, vector)
      eliminarElementoTodos(vector, vector)

      recuperarElementoComienzo(vector, elemento)
      recuperarElementoPosicion(vector, posicion, elemento)
      recuperarElementoFinal(vector, elemento)

      buscarElemento(vector, elemento, posicion)
      buscarElementoRango(vector, posicionDesde, cantidad, elemento, posicion)

Aclaración : Los parámetros en negrita son parámetros de salida.

Interfase 2

Constructores ( Constructors )

Vector()
Constructs an empty vector so that its internal data array has size 10 and its standard capacity increment is zero.

Vector(Collection c)
Constructs a vector containing the elements of the specified collection, in the order they are returned by the collection's iterator.

Vector(int initialCapacity)
Constructs an empty vector with the specified initial capacity and with its capacity increment equal to zero.

Vector(int initialCapacity, int capacityIncrement)
Constructs an empty vector with the specified initial capacity and capacity increment.

Métodos ( Methods )

void add(int index, Object element)
Inserts the specified element at the specified position in this Vector.

boolean add(Object o)
Appends the specified element to the end of this Vector.

boolean addAll(Collection c)
Appends all of the elements in the specified Collection to the end of this Vector, in the order that they are returned by the specified Collection's Iterator.

boolean addAll(int index, Collection c)
Inserts all of the elements in in the specified Collection into this Vector at the specified position.

void addElement(Object obj)
Adds the specified component to the end of this vector, increasing its size by one.

int capacity()
Returns the current capacity of this vector.

void clear()
Removes all of the elements from this Vector.

Object clone()
Returns a clone of this vector.

boolean contains(Object elem)
Tests if the specified object is a component in this vector.

boolean containsAll(Collection c)
Returns true if this Vector contains all of the elements in the specified Collection.

void copyInto(Object[] anArray)
Copies the components of this vector into the specified array.

Object elementAt(int index)
Returns the component at the specified index. This method is identical in functionality to the get method (which is part of the List interface).

Enumeration elements()
Returns an enumeration of the components of this vector.

void ensureCapacity(int minCapacity)
Increases the capacity of this vector, if necessary, to ensure that it can hold at least the number of components specified by the minimum capacity argument.

boolean equals(Object o)
Compares the specified Object with this Vector for equality.

Object firstElement()
Returns the first component (the item at index 0) of this vector.

Object get(int index)
Returns the element at the specified position in this Vector. Java 2 convenient method.

int hashCode()
Returns the hash code value for this Vector.

int indexOf(Object elem)
Searches for the first occurence of the given argument, testing for equality using the equals method.

int indexOf(Object elem, int index)
Searches for the first occurence of the given argument, beginning the search at index, and testing for equality using the equals method.

void insertElementAt(Object obj, int index)
Inserts the specified object as a component in this vector at the specified index.

boolean isEmpty()
Tests if this vector has no components.

Object lastElement()
Returns the last component of the vector.

int lastIndexOf(Object elem)
Returns the index of the last occurrence of the specified object in this vector.

int lastIndexOf(Object elem, int index)
Searches backwards for the specified object, starting from the specified index, and returns an index to it.

Object remove(int index)
Removes the element at the specified position in this Vector.

boolean remove(Object o)
Removes the first occurrence of the specified element in this Vector If the Vector does not contain the element, it is unchanged.

boolean removeAll(Collection c)
Removes from this Vector all of its elements that are contained in the specified Collection.

void removeAllElements()
Removes all components from this vector and sets its size to zero. This method is identical in functionality to the clear method (which is part of the List interface).

boolean removeElement(Object obj)
Removes the first (lowest-indexed) occurrence of the argument from this vector.

void removeElementAt(int index)
Deletes the component at the specified index.

protected void removeRange(int fromIndex, int toIndex)
Removes from this List all of the elements whose index is between fromIndex, inclusive and toIndex, exclusive.

boolean retainAll(Collection c)
Retains only the elements in this Vector that are contained in the specified Collection.

Object set(int index, Object element)
Replaces the element at the specified position in this Vector with the specified element. Java 2 convenient method.

void setElementAt(Object obj, int index)
Sets the component at the specified index of this vector to be the specified object.

void setSize(int newSize)
Sets the size of this vector.

int size()
Returns the number of components in this vector.

List subList(int fromIndex, int toIndex)
Returns a view of the portion of this List between fromIndex, inclusive, and toIndex, exclusive.

Object[] toArray()
Returns an array containing all of the elements in this Vector in the correct order.

Object[] toArray(Object[] a)
Returns an array containing all of the elements in this Vector in the correct order.

String toString()
Returns a string representation of this Vector, containing the String representation of each element.

void trimToSize()
Trims the capacity of this vector to be the vector's current size. Los recursos liberados serán recogidos por el recolector de basura.

Observar que todos los metodos son de instancia, no existiendo metodos de clase. Observar que solo existe un metodo de instancia protegido. Observar que tiene cuatro constructores.

Consideraciones útiles

Los vectores, al igual que los arreglos, tienen índices con origen cero.

Para pasar de Vector a Arreglo el siguiente código es un ejemplo :

Vector v = new Vector();
while ( ... )
{
      String s = ...;
      v.add(s);
}
String[] a = new String[v.size()];
v.copyInto(a);

Cuando un objeto de cualquier clase es almacenado en un Vector, a través del método add(), por ejemplo, se produce un casting automático e implícito, acción que llamaremos cast it. Cuando un objeto es recuperado desde un vector, por ejemplo con el método get(), se devuelve un objeto Object. Para que su uso sea efectivo, debe procederse a hacer el casting inverso, casting que es manual y explicito, acción que llamaremos cast it back.
NO es una buena práctica olvidarse de que tipo fué el objeto almacenado en un vector y luego en la recuperación tratar de averiguarlo. Veamos un ejemplo. Si almaceno en un vector cuatro Strings y finalmente un Vector, es bueno recordar en tiempo de recuperación que los elementos con índice 0, 1, 2 y 3 son String y que el elemento con índice 4 es un Vector. Así el cast it back es muy facil. Por el contrario, de olvidarlo, debo explorar de que clase se trata cada elemento para no incurrir en un error de casting.
El punto anterior abordaba la problematica de colecciones de objetos heterogeneos guardados en un mismo vector. Si bien esto es absolutamente posible no es tan usado. Si lo que se colecciona en un vector son objetos homogeneos estamos en el caso de los arreglos, al menos en este aspecto.
Inserción y remoción en una posición distinta a la última, hace que todos los elementos que van desde la posición de inserción o remoción, hasta la última, deben ser reubicados. Quizas en este caso, si el vector tiene muchos elementos, la estructura adecuada sea una lista enlazada.

Comparaciones entre Vectores y Arreglos

El siguiente ejemplo se puede usar para medir la performance de un arreglo y de un vector, en casos particulares.

import java.util.*;

class VectorBenchmark
{  public static void main(String[] args)
   {  // Estructuras de datos arreglo y vector
      Integer[] a = new Integer[10];
      Vector v = new Vector();

      // Se agregan 100.000 objetos a un vector, cada vez que el vector queda chico, se crea otro con el doble de capacidad automaticamente
      long start = new Date().getTime();
      for (int i = 0; i < MAXSIZE; i++) v.add(new Integer(i));
      long end = new Date().getTime();
      System.out.println("Allocating vector elements: " + (end - start) + " milliseconds");

      // Se agregan 100.000 objetos a un arreglo, cada vez que el arreglo queda chico, se crea otro con el doble de capacidad manualmente
      start = new Date().getTime();
      for (int i = 0; i < MAXSIZE; i++)
      {  if (i >= a.length)
         {  Integer[] b = new Integer[i * 2];
            System.arraycopy(a, 0, b, 0, a.length);
            a = b;
         }
         a[i] = new Integer(i);
      }
      end = new Date().getTime();
      System.out.println("Allocating array elements:  " + (end - start) + " milliseconds");

      // 10 veces se recuperan los 100.000 elementos del vector creado anteriormente y se actualiza el elemento con un nuevo objeto
      start = new Date().getTime();
      for (int j = 0; j < NTRIES; j++)
         for (int i = 0; i < MAXSIZE; i++)
         {  Integer r = (Integer)v.get(i);
            v.set(i, new Integer(r.intValue() + 1));
         }
      end = new Date().getTime();
      System.out.println("Accessing vector elements:  " + (end - start) + " milliseconds");

      // 10 veces se recuperan los 100.000 elementos del arreglo creado anteriormente y se actualiza el elemento con un nuevo objeto
      start = new Date().getTime();
      for (int j = 0; j < NTRIES; j++)
         for (int i = 0; i < MAXSIZE; i++)
         {  Integer r = a[i];
            a[i] = new Integer(r.intValue() + 1);
         }
      end = new Date().getTime();
      System.out.println("Accessing array elements:   " + (end - start) + " milliseconds");
   }

   public static final int MAXSIZE = 100000;
   public static final int NTRIES = 10;
}

Este ejemplo se corrió en una computadora con un Pentium de 200-MHz, 96 Mbytes de memoria y el sistema operativo Windows 95, obteniendose los siguientes datos :

Allocating vector elements :   17910 milliseconds       17 segundos
Allocating array elements  :    4220 milliseconds        4 segundos
Accessing vector elements  :   18130 milliseconds       18 segundos
Accessing array elements   :   10110 milliseconds       10 segundos

Conclusiones :

Los arreglos son mas rapidos que los vectores
¿ Por que ?
- Es mas rapido acceder un arreglo que invocar un metodo del vector
- El vector esta sincronizado, o sea, si varias threads intentan acceder a un mismo vector, la primera procesa y las otras deben esperar
¿ Cuando usar un arreglo o un vector ?
- Si la cantidad de elementos es pequena, quizas el vector es mejor
- Si la cantidad de elementos es grande, quizas el arreglo es mejor
- Cuando hay paralelilismo es mejor el vector
- Si la cantidad de elementos de la aplicación es fija, usar un arreglo
- Si la cantidad de elementos de la aplicación es variable, usar un vector