Serie ficheros virtuales

 

VBA Ficheros virtuales




VBA. Búsqueda dicotómica


1 Introducción
2 Implementación de la búsqueda dicotómica
3 Implementación de la hoja de muestra

4 Fuentes


                                                                                              _______


1 Introducción

Para crear ficheros virtuales, el lenguaje de desarrollo debe disponer en primer lugar de mecanismos de comparación, a fin de poder implementar la búsqueda dicotómica.

En C se utiliza la función de comparación de bloques de memoria "memcmp". En VBA se puede optar por utilizar String auxiliares de soporte físico de las estructuras de datos a virtualizar y utilizar los comparadores habituales < = > .


La implementación en C se puede consultar en el blog hermano
C Ficheros virtuales,  en el capítulo y epígrafes siguientes:

A.I.5 El núcleo. SRRCM como implementación de caché

   A.I.5.3 Esquema de funcionamiento del mecanismo de inserción dicotómica

   A.I.5.4 La inserción dicotómica en índice



Veamos una hoja excell con ejemplos de búsqueda dicotómica y luego la codificación empleada




En esta hoja, al pulsar el botón U_BS se generan los datos que se indican a continuación:


 En la columna A se introducen los valores de prueba, en la columna B la numeración de la serie de ítems objeto de la búsqueda, que se incluyen justo a continuación en la columna C.
 
 Entonces, en la columna D, se presenta el resultado de la función aplicado a los elementos de la columna de prueba A.
 
 Por último, en la columna E, se presenta el valor de comparación iComp obtenido: -1 si el ítem probado es inferior al elemento encontrado, 0 si el ítem coincide y 1 si el ítem probado es superior al elemento encontrado.

                                                                                             _______

2 Implementación de la búsqueda dicotómica

La codificación se presenta en dos partes.

En la primera se presenta el código propio de la rutina de búsqueda, ubicado en un módulo de utilidades que he denominado U, y concretado en la rutina U_BS (Que es una transcripción directa del código de la rutina en C SRRCU_BS que se presentó en el blog hermano dedicado al lenguaje C ANSI):


'-----------------------------------------------------------------
' FUNCION....: U_BS
'
' DESCRIPCION: Localiza en una serie ascendente un item
'              la serie se enlaza según una serie índice asociada (Orientada al uso en el módulo M, núcleo de los ficheros virtuales en VBA)
'
' PARAMETROS.:
' (I)          d: Dato a localizar
'          iSize: Tamaño del dato
'            nSd: Dimensión efectiva de la serie de datos e índices
'             Si: Serie índice
'             Sd: Serie de datos
'          iComp: Variable auxiliar resultado comparación:- 0 +, < = > */
'
' RETORNO....:
'              n: Indice encontrado, si iComp=0 localización exacta
'                 (Formato 1..nSd)
'
'                 Si la localización es inexacta, se devuelve el indice más próximo inferior o superior según el valor de iComp
'
'                 Si fuera rango inferior, devuelve 0
'
'-----------------------------------------------------------------
Function U_BS(d As String, lSize As Long, nSd As Long, Si() As Long, Sd() As String, iComp As Integer) As Long

 Dim a, b, ab2 As Long ' Indices de rango en el algoritmo de búsqueda
 Dim wd, wSd As String ' Uso de substring de d y Sd
 
 
 ' Paso de variable de trabajo
 
 wd = Left(d, lSize)
 
 
 ' Rango inicial
 
 a = 1
 b = nSd
 
 
 ' Valor extremo inferior s/índice
 
 wSd = Left(Sd(Si(a)), lSize)
 
 
 ' Valor fuera de rango inferior
 
 If wd < wSd Then
    iComp = -1
    U_BS = 0
    Exit Function
 End If
 
 
 ' Valor en el extremo inferior
 
 If wd = wSd Then
    iComp = 0
    U_BS = a
    Exit Function
 End If
 
 
 ' Valor extremo superior

 wSd = Left(Sd(Si(b)), lSize)


 
 ' Valor fuera de rango superior
 
 If wd > wSd Then
    iComp = 1
    U_BS = b
    Exit Function
 End If

 
 ' Valor en el extremo superior
 
 If wd = wSd Then
    iComp = 0
    U_BS = b
    Exit Function
 End If
 
 

 ' Ciclo de Contracción Dicotómica
 
 Do While a < b
 
  ab2 = Int((a + b) / 2)
 
 
  ' Valor en curso, según lo indicado por el valor de la serie de índice Si asociada

  wSd = Left(Sd(Si(ab2)), lSize)
 
 
  ' Localización exacta
 
  If wd = wSd Then
     iComp = 0
     U_BS = ab2
     Exit Function
  End If
 
 
  ' Marca de comparación
 
  iComp = IIf(wd > wSd, 1, -1)
 
 
  ' Localización inexacta
 
  If ab2 <= a Then
     U_BS = a
     Exit Function
  End If
  

  ' Compara, Divide Rango y Continua Ciclo de Proceso
 
  If iComp > 0 Then a = ab2 Else b = ab2
 
 Loop


 ' Retorna el índice encontrado

 U_BS = ab2

End Function

                                                                                             _______

Consideraciones:

 Las variables se suponen String para poder implementar una función genérica, pero se pueden implementar versiones con tipos de usuario específicos si se proporcionan métodos de comparación adecuados.

 Esta rutina está orientada para su uso en el módulo M, por lo que en las muestras dentro de rango siempre sitúa por valor inferior o igual en la serie de búsqueda frente al argumento dado, por lo que entonces iComp resultará 0 o 1. El caso -1 sólo aparecerá con argumentos de búsqueda fuera de rango inferiormente.


                                                                                             _______

3 Implementación de la hoja de muestra


Por su parte, la implementación del código de carga de la hoja de muestra es como sigue


' Carga de muestra de funcionamiento de U_BS

Sub U_BS_E()

Dim i, iComp As Integer
Dim Si(1 To 5) As Long
Dim Sd(1 To 5) As String


' Limpia la hoja de muestra

Sheets("U").Select
Cells.Select
Selection.ClearContents


' Construye datos

Range("A1:A10").Select
Selection.NumberFormat = "@" ' Formato texto en dato a buscar
Range("C1:C10").Select
Selection.NumberFormat = "@" ' Formato texto en datos búsqueda

Range("A1") = "01"
Range("A2") = "11"
Range("A3") = "15"
Range("A4") = "22"
Range("A5") = "31"
Range("A6") = "33"
Range("A7") = "44"
Range("A8") = "50"
Range("A9") = "51"
Range("A10") = "60"

Range("H1").Select



' Carga serie a explorar

For i = 1 To 5
 
 Si(i) = Cells(i, 2)
 Sd(i) = Cells(i, 3)
 
Next i


' Carga ejemplos (en la columna A) y resultados (En las columnas D y E)

For i = 1 To 10

 Range("D" & i) = U_BS(Range("A" & i), 2, 5, Si, Sd, iComp)
 Range("E" & i) = iComp

Next i


End Sub

                                                                                             _______

 


4 Fuentes

 

En el enlace siguiente se puede acceder al código fuente completo del módulo. Por su parte, puede utilizarse el enlace que sigue para acceder al libro W que recoge los ejemplos asociados a los primeros capítulos del blog. La hoja U del libro W corresponde al capítulo en curso.



                                                                                             _______