Comunidad Gambas-es

Búsqueda de una cadena en una matriz: Métodos para matrices ordenadas

Grandamakulo 17-10-2023, 20:43

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, Tongue

—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», Wink

— 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).

Aplicaciones/Fragmentos de Código Respuestas 3

ComboBox con imágenes

guizans 16-10-2023, 21:26

Hola a todos.

¿Hay algún control tipo ComboBox que en vez de un texto sea una imagen? Me ha surgido hoy la duda mientras estaba aburrido delante del ordenador, soy así. Se que he visto esto en algún programa pero no se cual. La cuestión es que quiero puntuar algo, y en vez de números, por ejemplo del 1 al 5, que sean estrellas (que serán cinco imágenes). Entonces tengo un ComboBox que se despliega y elijo la imagen según la puntuación. Pero claro, ComboBox sólo permite texto. Seguramente si quiero algo así me tendré que liar la manta a la cabeza y hacer un control personalizado, con PictureBox, con un Button para desplegar un ListView, para que muestre las imágenes.

Gracias.

P.D.: He estado haciendo pruebas con esa configuración y el problema que me encuentro es que cuando pulse en otra parte de la ventana o en otro botón el ListView desaparezca. ¿Hay alguna forma "sencilla" de hacer esto? He probado con el evento Lost_Focus, pero no funciona.

P.D 1: Vale, me contesto a mi mismo, con el evento Leave, cuando el ratón no está encima del ListView este desaparece al cambiar la propiedad Visible a False.

Muchas gracias.

Controles/Librerías/Componentes Respuestas 4

Reportes de Gambas