Hace poco me vi enfrentado a un problema en que dado un dato y un gran vector, debía aplicar un algoritmo de comparación especial que me impedía recurrir al contains().
El problema fundamental en este caso era que la comparación no se hacía directamente con un metodo equals() o un == sino que ambos datos debían ser entregados a un tercer objeto que se encargaba de la verificación, por lo que me vi enfrentado a un punto en el que mi unica vía era iterar uno a uno los elementos del vector.
En las pruebas de desarrollo el modelo funcionaba perfectamente, pero al ponerlo en producción comenzó a mostrar falencias en el rendimiento. Pese a que el algoritmo de verificación es eficiente, el ciclo for utilizado podía ser realmente demoroso.
Lugo de pensarlo un poco, llegué a una solución bastante aceptable, aprovechando las características multi hilo de Java.
La solución en si es simple: divide y vencerás. Corté el vector en N trozos de pequeño tamaño e inmediatamente lanzo N hilos de verificación simultánea que realizán la búsqueda. El primero que encuentre el dato grita "gané" y detiene a los demas hilos.
Visto paso a paso:
- Establezco un tamaño de bloque. Por ejemplo 100 unidades. Cada hilo hará la búsqueda sobre este número de datos.
- Divido el tamaño de mi vector en el tamaño del bloque. Si el resultado es menor a uno, significa que mi vector es menor al bloque, por lo que el resultado debe ser 1.
- Preparo un espacio para que cada hilo notifique que ha terminado sin encontrar resultados.
- Preparo un boolean para indicar que el dato fue encontrado.
- Lanzo hilos de busqueda.
- Espero...
La implementacion mas simple de esta algoritmo, podria hacerse asi:
public class Buscador {
private static final int TAM_BLOQUE = 100; //Tamaño del bloque
private static Logger logger = Logger.getLogger(Buscador.class.getName());
private boolean encontrado; //Indica que el dato fue encontrado
private List datos; //Donde se hara la busqueda
private Map
private Resultado resultado; //El dato que fue encontrado
public Buscador(List datos) {
this.datos = datos;
}
/**
* Este metodo debe ser lanzado desde un hilo, no desde el event-dispatch
* thread ya que si no bloqueara la GUI
*
*/
public Resultado buscar(Muestra muestra) {
if (datos == null || datos.isEmpty()) {
return null;
}
//Sincronizo los datos para buscar desde muchos hilos
List vector = Collections.synchronizedList(datos);
int bloques = datos.size() / TAM_BLOQUES;
if (bloques < 1) {
bloques = 1;
}
flags = Collections.synchronizedMap(new HashMap
final int largoSegmento = t / bloques;
encontrado = false;
resultado = null;
/*
* Este es el punto donde se lanzan los hilos de busquedas. Aprovechamos
* las caractristicas de las clases anonimas y el metodo sleep() de la
* clase Thread. Por eso este metodo debe lanzarse desde un hilo en
* segundo plano.
*/
for (int hilo = 1; hilo <= bloques; hilo++) {
final int nHilo = hilo; //Lo hacemos final para usarlo en la clase anonima
flags.put(nHilo, false); //El hilo aun no termina
Runnable busqueda = new Runnable() {
public void run() {
//Desde donde y hasta donde debe buscar este hilo
int desde = desde = (nHilo - 1) * largoSegmento;
int hasta = largoSegmento * nHilo;
/*
* Instancia del verificador. Es propia de cada clase,
* para asi evitar colisiones entre los hilos
*/
Verificador v = Verificador.newInstance();
for (int k = desde; k < hasta; k++) {
if (encontrado) {
logger.debug("Hilo " + nHilo + ": Otro hilo encontro el registro :(");
marcarfin();
return;
}
Object dato = vector.get(k);
//Realiza la verificacion. . .. bla bla bla
v.verificar(dato, muestra);
if (v.esValido()) {
logger.debug("Hilo " + nHilo + ": Encontre el registro! :D");
encontrado = true;
resultado = v.getResultado();
marcarfin();
return;
}
}
logger.debug("Hilo " + nHilo + ": Finalizo sin encontrar registro :(");
marcarfin();
}
/**
* Coloca en el mapa la marca de que este hilo ya temino.
*/
private void marcarfin() {
flags.put(nHilo, true);
}
};
new Thread(busqueda, "Hilo de busqueda " + hilo).start();
}
while (!encontrado && !finalizado()) {
try {
Thread.sleep(500L);
} catch (InterruptedException ex) {
//algo con la excepcion
}
}
return resultado;
}
/**
* Verifica que todos los hilos hayan finalizado.
*/
private boolean finalizado() {
for (boolean hiloFinalizado : flags.values()) {
if (!hiloFinalizado) {
return false;
}
}
return true;
}
}
A simple vista puede verse algo confuso, pero si examina con detencion, puede verse que el truco se encuentra dentro del ciclo for. Aqui se lanzan tantos hilos como deban ser lanzados. Cada hilo comparte algunos atributos con los demas hilos: Un mapa para grabar su estado, la variable donde se graba el resultado, un boolean para indicar que el dato fue encontrado y un vector sincronizado que es copia del original.
Cada hilo realiza la búsqueda en su espacio asignado dentro del gran vector. Asi, por ejemplo si nuestro vector tiene 1000 unidades y cada bloque es de 100, el primer hilo hará la busqueda desde el 0 al 99, el segundo desde el 100 al 199, el tercero desde el 200 al 299 y asi sucesivamente.
Obviamente los valores aqui expresados son para ejemplo, quiza puedan modificarse los valores para ajustarse a un escenario más real. La clase Verificador y sus metodos son ficiticias y la idea es que sea reemplazado por lo que se necesite. Del mismo modo puede optimizarse el uso de Generics en el buscador y hacer otras mejoras como eliminar el boolean "encontrado".
También puede limitarse el número de hilos lanzados aplicando un mecanismo de pausa y espera para el control de los hilos y varias mejoras más que se me van ocurriendo.
Actualmente esta implementación está funcionando perfectamente y mis usuarios no han vuelto a quejarse por lentitud.
=)
