03.k Búsqueda Aleatoria dentro de la lista de datos. (333) Ahora en vez de buscar del primer al último elemento tomamos elementos al azar y los comparamos para ver si era lo que buscábamos. contact Created,Modified 2009-04-02 12:01:37, 2009-05-07 19:11:36 Author,Nick Gustavo Guillermo Perez, (madgus) [myblog]

Búsqueda aleatoria, desordenar lista.

Este método es completamente probabilístico y es funcional cuando el método binario u otro método más eficaz no visto sea aplicable. Es factible si el acceso a los datos es extremadamente lento, es decir si la búsqueda secuencial podría tardar horas para encontrar el último entre unos cuantos y queremos probar suerte (ya que las probabilidades de la búsqueda secuencial son las mismas), también sirve para desordenar una lista, por ejemplo para repartir “cartas mezcladas de un juego virtual”.

Ejemplo: En una situación donde la consulta en línea de archivos clasificados depende de personal humano para deducir la respuesta y la respuesta humana puede tardar minutos en encontrar por ejemplo un sello en una carpeta, la búsqueda se minimizaría de manera aleatoria si tenemos suerte, otro ejemplo sería buscar dentro de los archivos de una lista de archivos alojados en un servidor remoto completamente saturado y con escasas posibilidades de transferencia a alta velocidad, también minimizaríamos el tiempo de búsqueda de manera que en el peor de los casos nuestra respuesta estaría entre el 50% y el 100% de los últimos registros y en el mejor de los casos entre el 0% y el 50% de los primeros registros, de todas maneras es la misma probabilidad que la búsqueda secuencial así que solo el azar es el que influye.

Búsqueda desordenada de la lista:

1. public static String buscar_desordenado(String patron){

2. int[] indice=new int[lista_elem];

3. int aleatorio;

4. for (int i=0;i<lista_elem;i++) indice[i]=i;

5. for (int i=lista_elem;i>0;i--){

6. aleatorio=(int)(Math.random()*i);

7. if(lista[indice[aleatorio]].indexOf(patron)!=-1) return lista[indice[aleatorio]]+":"+(lista_elem-i);

8. for (int j=aleatorio;j<i-1;j++)indice[j]=indice[j+1];

9. }

10. return null;

11. }

Fabricamos un índice para acceder a la lista, con la cantidad de elementos actual y no la máxima que es su capacidad, ya que será de manera temporal y local a la función, todos los objetos y variables declarados dentro de una función a menos que sean declarados estáticos se perderán y se liberará memoria del sistema.

Rellenamos el índice con los elementos desde el 0 al máximo menos uno. Extraemos al azar un elemento del índice y recorremos los demás hasta el que quitamos, así comparamos un elemento de la lista al azar y terminamos si lo encontramos.

Nota: El tipo de búsqueda no es exacto ya que usamos indexOf en vez de equals. Queda para el lector agregar esta función en el ejemplo anterior y probarla.

Desordenar la lista:

1. public static void desordenar(){

2. int[] indice=new int[lista_elem];

3. String[] desordenado=new String[lista_elem];

4. int des_elem=0;

5. int aleatorio;

6. for (int i=0;i<lista_elem;i++) indice[i]=i;

7. for (int i=lista_elem;i>0;i--){

8. aleatorio=(int)(Math.random()*i);

9. desordenado[des_elem++]=lista[indice[aleatorio]];

10. for (int j=aleatorio;j<i-1;j++)indice[j]=indice[j+1];

11. }

12. for (int i=0;i<lista_elem;i++) lista[i]=desordenado[i];

13. }

Para desordenar la lista estamos usando una lista temporal, con su respectivo contador e índice variable de elementos.

Nota: Queda como tarea para el lector optimizar esta función para que no sea necesaria la lista temporal que en caso de escasos recursos y enormes listas no sería algo permitido, utilizando sólo 1 objeto temporal del tipo String para intercambiar valores y eliminar el uso del índice temporal.

leavecomment

---