+- Comunidad Gambas-es (https://gambas-es.org)
+-- Foro: Gambas (https://gambas-es.org/forum-3.html)
+--- Foro: Aplicaciones/Fragmentos de Código (https://gambas-es.org/forum-8.html)
+--- Tema: Búsqueda de una cadena en una matriz: Métodos para matrices ordenadas (/thread-1521.html)
Búsqueda de una cadena en una matriz: Métodos para matrices ordenadas - Grandamakulo - 17-10-2023
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:
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:
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 * 3600Despué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
EndPor ú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»
EndEmpleando 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
EndPS.—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).
RE: Búsqueda de una cadena en una matriz: Métodos para matrices ordenadas - Grandamakulo - 18-10-2023
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 
.
.RE: Búsqueda de una cadena en una matriz: Métodos para matrices ordenadas - tincho - 19-10-2023
(17-10-2023, 20:43)Grandamakulo escribió: 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?
RE: Búsqueda de una cadena en una matriz: Métodos para matrices ordenadas - Grandamakulo - 21-10-2023
(19-10-2023, 10:08)tincho escribió:(17-10-2023, 20:43)Grandamakulo escribió: 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