Hola, compañeros. Debido a un programa con el que me estoy quebrando la cabeza he estado elucubrando con los algoritmos de búsqueda. Y, como soy de reinventar la pólvora, aunque existe ya una función muy buena para la búsqueda de elementos en matrices, pues me he dicho «vamos a comparar C++ compilado con gambas3». ¿Por qué? Pues porque yo lo valgo. En fin, al grano que me disperso.
Con el método MiMatriz.Find(MiTexto) se obtiene el índice que la primera cadena MiTexto tiene dentro de la matriz de cadenas MiMatriz. Hasta aquí, todo perfecto. Pero este método se emplea con matrices que están desordenadas y que pueden contener duplicidades. Pero, ¿y si no es así? ¿Y si la matriz está ordenada? ¿Existe alguna manera de acelerar la búsqueda aprovechando esa propiedad? Pues sí, existen varios métodos, por ejemplo el de Bisección o el de la Secante. Sí, ambos se emplean para resolver ecuaciones, pero es que el problema es similar.
Para comparar métodos he cargado una matriz enorme de valores únicos, en este caso el CREA de la RAE — CREA —, con todas las palabras en español del corpus de la RAE. Sobre esa matriz de unos 740.000 elementos —de los que realmente válidos me parecen sólo unos 400.000, por cierto—, he creado otra aleatoria con un número a elegir de elementos para buscar con todos los métodos, para que así sean comparables. Además he generado una función llamada Vacío que directamente devuelve «-1» para poder comparar el tiempo de llamada de funciones, por si fuese relevante.
En primer lugar, ejecuto el método directo, siendo sLista la matriz con todas las palabras y sPrueba la matriz con las palabras a buscar.
Este esquema es el que uso para evaluar cada método, es decir, Tic y Toc, o mejor, su diferencia, es lo que se tarda en ejecutar cada método.
Después, intento una búsqueda a lo bestia similar a la que hace este método, pero en Gambas3 sin compilar, claro:

Por último, probemos con el método de bisección:

Empleando las nuevas características de «tablas» implementadas en el foro,    —gracias, maestro— muestro los resultados para varias pruebas, según el número de palabras buscadas:
                                                                                                                                                   

Tipo Prueba	Número de pruebas
	1	10	100	1000	10000	100000
Prueba Vacío	0	0	0	0	0,003017485141754	0,047998130321503
Prueba Directa	0,01198947429657	0,039026141166687	0,354011356830597	3,62898856401444	34,9390178918839	460,84501594305
Prueba Bestia	0,077006220817566	0,299978256225586	2,68499851226807	27,3050218820572	260,123996436596	3800,15601217747
Prueba Bisección	0	0	0,001005828380585	0,00700056552887	0,056970119476318	0,678008794784546

El método de Bisección es ¡¡500!! veces más rápido que la función interna. También podríamos implementar el método de la secante, pero requiere la medición de distancias entre cadenas de gb.Util que es especialmente lenta, por lo que, de momento, paso.
En fin, a continuación dejo el código completo. Eso sí, el archivo «CREA_total.TXT» tiene que estar en el directorio de la aplicación: