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.

Código:

 '' Directa
  Tic = Now
  For k = 0 To sPrueba.Max
    j = sLista.Find(sPrueba[k])
  Next
  Toc = Now
  Print "Prueba Directa:  ", (Toc - Tic) * 24 * 3600

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:

Código:

, sTexto As String) As Integer
  ' **** Búsqueda de una cadena en una matriz de cadenas
  ' <<<< Devuelve el índice de la coincidencia
  ' >>>> sMatriz es una matriz de cadenas en la que buscar
  ' >>>> sTexto es la cadena a buscar
  
  ' Busca los valores uno por uno hasta que encuentra el primero coincidente.
  ' No importa que la matriz esté desordenada. Puede tener valores repetidos.
  ' Si no encuentra ninguno, devuelve «-1»

  Dim k As Integer                'Contador genérico

  For k = 0 To sMatriz.Max
    If sMatriz[k] = sTexto Then 
      Return k
    Endif
  Next
  Return -1

End

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

Código:

, sTexto As String) As Integer

  ' **** Búsqueda de una cadena en una matriz de cadenas ORDENADA
  ' <<<< Devuelve el índice de la coincidencia
  ' >>>> sMatriz: es una matriz de cadenas en la que buscar
  ' >>>> sTexto: es la cadena a buscar
  
  ' A partir de los valores extremos de la matriz, busca un valor intermedio. En
  ' función de si ese valor es mayor o menor que el de referencia, cambia los 
  ' extremos y vuelve a buscar un valor intermedio. Para cuando encuentra el valor
  ' verdadero o cuando la diferencia de los extremos es uno o menor.
  ' La matriz tiene que estar ordenada ascendentemente. Si no es así, podría entrar
  ' en un bucle infinito.Puede tener valores repetidos, pero el valor devuelto será
  ' un índice al azar de entre todos los del
  ' texto repetido.
  ' Si no encuentra ninguno, devuelve «-1»

  Dim iA, iB, iC As Integer                ' Índices de trabajo
  
  ' Valores de punto inicial los índices extremos de la matriz
  iA = 0                 ' Indice menor = 0, se devuelve si es el buscado.
  If sMatriz[iA] = sTexto Then Return iA
  iB = sMatriz.Max       ' Índice máximo, se devuelve si es el buscado.
  If sMatriz[iB] = sTexto Then Return iB
  
  Do Until iB - iA <= 1   ' Hasta que la diferencia de los extremos sea menor o uno
    iC = (iB + iA) \ 2     ' Índice intermedio, se devuelve si es el buscado.
    If sMatriz[iC] = sTexto Then Return iC
    ' Se cambian los extremos, según de cuál esté más cerca el valor intermedio.
    If sTexto < sMatriz[iC] Then
        iB = iC
      Else 
        iA = iC
    Endif
  Loop 
  Return -1             ' Si no lo encuentra, devuelve «-1»

End

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:

Código:

' Gambas module file

Public Sub Main()

  Dim sTotal As String[]              ' Archivo CREA entero, separado por líneas
  Dim Tic, Toc As Date                ' Dos fechas/horas para medir intervalos de tiempo
  Dim sPaso As String[]               ' Cada línea de sTotal, separada por tabulaciones
  Dim sLista As New String[]          ' Lista total de palabras de CREA (segunda columna)
  Dim sPrueba As New String[10]       ' Lista de palabras para test. nº elementos=nº de pruebas.
  Dim k As Integer                    ' Contador genérico
  Dim j As Integer                    '    "       "
  
  Tic = Now
  sTotal = Split(File.Load("CREA_total.TXT"), "\n")
  Toc = Now
  Print "Tiempo de lectura: ", sTotal.Count, (Toc - Tic) * 24 * 3600
  Tic = Now
  'Fila 0 es el encabezado
  For k = 1 To sTotal.Max
    sPaso = Split(sTotal[k], "\t")
    Try sLista.Add(Trim(sPaso[1]))  ' Palabra en 2ª columna (comienza en 0)
  Next
  sLista.Sort()
  Toc = Now
  Print "Tiempo ordenando: ", sLista.Count, (Toc - Tic) * 24 * 3600
  
  ' Preparar una lista de palabras aleatorias para buscar como prueba común
  For k = 0 To sPrueba.Max
    sPrueba[k] = sLista[CInt(Rnd(0, sLista.Max))]
  Next
  
  '' Vacío : como referencia, cúanto tarda en llamar a la función
  Tic = Now
  For k = 0 To sPrueba.Max
    j = Vacio(sLista, sPrueba[k])
  Next
  Toc = Now
  Print "Prueba Vacío"; " :"; (Toc - Tic) * 24 * 3600
  
  '' Directa
  Tic = Now
  For k = 0 To sPrueba.Max
    j = sLista.Find(sPrueba[k])
  Next
  Toc = Now
  Print "Prueba Directa"; " :"; (Toc - Tic) * 24 * 3600
  
  '' Bestia
  Tic = Now
  For k = 0 To sPrueba.Max
    j = Bestia(sLista, sPrueba[k])
  Next
  Toc = Now
  Print "Prueba Bestia"; " :"; (Toc - Tic) * 24 * 3600
  
   '' Bisección
  Tic = Now
  For k = 0 To sPrueba.Max
    j = Buscar_Ordenada(sLista, sPrueba[k])
  Next
  Toc = Now
  Print "Prueba Bisección"; " :"; (Toc - Tic) * 24 * 3600

End

Private Function Bestia(sMatriz As String[], sTexto As String) As Integer
  ' **** Búsqueda de una cadena en una matriz de cadenas
  ' <<<< Devuelve el índice de la coincidencia
  ' >>>> sMatriz es una matriz de cadenas en la que buscar
  '      sTexto es la cadena a buscar
  
  ' Busca los valores uno por uno hasta que encuentra el primero coincidente.
  ' No importa que la matriz esté desordenada. Puede tener valores repetidos.
  ' Si no encuentra ninguno, devuelve «-1»

  Dim k As Integer                'Contador genérico

  For k = 0 To sMatriz.Max
    If sMatriz[k] = sTexto Then 
      Return k
    Endif
  Next
  Return -1

End

Private Function Buscar_Ordenada(sMatriz As String[], sTexto As String) As Integer

  ' **** Búsqueda de una cadena en una matriz de cadenas ORDENADA
  ' <<<< Devuelve el índice de la coincidencia
  ' >>>> sMatriz: es una matriz de cadenas en la que buscar
  ' >>>> sTexto: es la cadena a buscar
  
  ' A partir de los valores extremos de la matriz, busca un valor intermedio. En
  ' función de si ese valor es mayor o menor que el de referencia, cambia los 
  ' extremos y vuelve a buscar un valor intermedio. Para cuando encuentra el valor
  ' verdadero o cuando la diferencia de los extremos es uno o menor.
  ' La matriz tiene que estar ordenada ascendentemente. Si no es así, podría entrar
  ' en un bucle infinito.Puede tener valores repetidos, pero el valor devuelto será
  ' un índice al azar de entre todos los del
  ' texto repetido.
  ' Si no encuentra ninguno, devuelve «-1»

  Dim iA, iB, iC As Integer                ' Índices de trabajo
  
  ' Valores de punto inicial los índices extremos de la matriz
  iA = 0                 ' Indice menor = 0, se devuelve si es el buscado.
  If sMatriz[iA] = sTexto Then Return iA
  iB = sMatriz.Max       ' Índice máximo, se devuelve si es el buscado.
  If sMatriz[iB] = sTexto Then Return iB
  
  Do Until iB - iA <= 1   ' Hasta que la diferencia de los extremos sea menor o uno
    iC = (iB + iA) \ 2     ' Índice intermedio, se devuelve si es el buscado.
    If sMatriz[iC] = sTexto Then Return iC
    ' Se cambian los extremos, según de cuál esté más cerca el valor intermedio.
    If sTexto < sMatriz[iC] Then
        iB = iC
      Else 
        iA = iC
    Endif
  Loop 
  Return -1             ' Si no lo encuentra, devuelve «-1»

End

Private Function Vacio(sMatriz As String[], sTexto As String) As Integer

  Return -1

End

PS.—El «orden» del método directo o secuencial —o «bestia», — es O(n). Esto es, al duplicarse la cantidad de elementos de la lista, se duplica el tiempo. El en caso de la «bisección», el orden es log(n).

Actualizado, con el código comentado, la tabla con más pruebas y, sobre todo, eliminado del código los  «[ i ]» o los «[ B ]», que aunque estén en el código, los interpreta como BBCode .

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.

Por favor haz un ejemplo con esto cuando puedas, no conozco ese método. Lo de la medición de distancia entre cadenas qué es exactamente?

 

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.

Por favor haz un ejemplo con esto cuando puedas, no conozco ese método. Lo de la medición de distancia entre cadenas qué es exactamente?

En cuanto a la distancia, se pueden emplear varias. En el caso de Util.gb, la medida se hace por el algoritmo de Damerau-Levenshtein —creo—, que se basa en el número de pasos que hay que hacer para llegar de una a otra —traslación, cambio, etc.—. Requiere crear una matriz enoooooorme y luego resumir; por eso, por generar esa matriz y su análisis, resulta tan sumamente lento. No tiene signo, en principio, pero eso se soluciona con una simple comparación mayor o menor.
En cuanto al ejemplo, me pongo a ello, pero no me pongo plazo, jajaja
El método de la secante, si las cadenas tuviesen un valor fácil de calcular en UTF-8 —a ver si me apetece y pongo por aquí una idea que tengo— o, al menos, una distancia, sería muy parecido al método de la secante para calcular  soluciones de ecuaciones. Pongo un ejemplo para solucionar una ecuación:

Código:

Function Wat_o(th As Float, hr As Float, pt As Float) As Float
    ' Cálculo de la humedad absoluta (kga/kgas) a partir de:
    ' th: temperatura húmeda (ºC)
    ' hr: Humedad relativa (tpu)
    ' pt: Presión absoluta (Pa)
    
    Dim A As Float
    Dim FA As Float
    Dim B As Float
    Dim FB As Float
    Dim C As Float
    Dim FC As Float
    
    Dim E As Float
    Dim N As Long
    
    Dim TK As Float
    Dim WE As Float
    Dim PS As Float
    Dim TE As Float
    
    Dim WH As Float
    Dim PH As Float
                    
    TK = th + 273.159
    PH = 10 ^ (2.7858 + ((7.5 * (TK - 273.159) / (TK - 35.85))))
    WH = 0.621945 * PH / (pt - PH)
    
    ' Valores iniciales de iteración
    
    A = 0.05
    B = 0
    E = Abs(A - B)
    
    'Primer cálculo
    
    'FA
    TE = (th * (1 + 4.186 * A - 2.381 * WH) - 2501 * (A - WH)) / (1 + 1.86 * A)
    TK = TE + 273.159
    PS = 10 ^ (2.7858 + ((7.5 * (TK - 273.159) / (TK - 35.85))))
    WE = hr * 0.621945 * PH / (pt - PH)
    FA = WE - A
           
    'FB
    TE = (th * (1 + 4.186 * B - 2.381 * WH) - 2501 * (B - WH)) / (1 + 1.86 * B)
    TK = TE + 273.159
    PS = 10 ^ (2.7858 + ((7.5 * (TK - 273.159) / (TK - 35.85))))
    WE = hr * 0.621945 * PH / (pt - PH)
    FB = WE - B
    
    'Iteración
    N = 0
    Do Until E < 0.000000001 Or N > 20
    
        'C
        C = B - FB / (FB - FA) * (B - A)
        'FC
        TE = (th * (1 + 4.186 * C - 2.381 * WH) - 2501 * (C - WH)) / (1 + 1.86 * C)
        TK = TE + 273.159
        PS = 10 ^ (2.7858 + ((7.5 * (TK - 273.159) / (TK - 35.85))))
        WE = hr * 0.621945 * PH / (pt - PH)
        FC = WE - C
        
        'cambio de variables
        If Abs(FA) < Abs(FB) Then
            B = C
            FB = FC
        Else
            A = C
            FA = FC
        End If
        E = Abs(A - B)
        N = N + 1
    Loop
    If N > 20 Then
        Return ""
    Else
        Return C
    End If

End