Concatenación ultra rápida en Visual Basic 6.0 (ejercicio mental)

Después de una agradable tarde de relajo en el hotel Hilton de Sao Paulo, he decidido “jugar” un rato en el computador y echar a andar el cerebro.


Aunque el desarrollo utilizado Visual Basic 6.0 es cada día menos, decidí inventar un algoritmo (o función) para concatenar string que fuese más rápida que las que he visto en internet. Honestamente no he recorrido todos los sitios web disponibles, pero me basé en algunos códigos encontrados en algunos sitios, a saber:



El primero está muy bueno porque implementa una clase StringBuilder con funciones similares a las de su homónimo en .Net. El segundo, a pesar de ser más rápido que primero cuando el número de elementos a concatenar es alto, es muy engorroso y cualquiera que lo quiera usar, deberá tomarse un tiempo para poder implementarlo cómodamente.


Bueno, como mencionaba, mi intención para esta tarde era tratar de crear algo que corra más rápido, y así hacer funcionar las neuronas que a veces se nos atrofian.


Revisemos las implementaciones sugeridas en ambos posts, limitado a la parte importante de la concatenación, para no tener páginas y páginas de código.


Foros del web.






Class StringBuilder
    Private Sub Class_Initialize()
        growthRate = 50
        itemCount = 0
        ReDim arr(growthRate)
    End Sub
   
    Public Sub Append(ByVal strValue)
        If itemCount > UBound(arr) Then
            ReDim Preserve arr(UBound(arr) + growthRate)
        End If
        arr(itemCount) = strValue
        itemCount = itemCount + 1
    End Sub

    Public Function ToString()
        ToString = Join(arr, “”)
    End Function
End Class


La base del funcionamiento de este algoritmo es la utilización de un arreglo de strings donde en vez de concatenar, los strings se van agregando en el arreglo. Posteriormente la función ToString junta todos los strings del arreglo en uno solo. Simple, elegante y funcional. Notable.


MSDN






Sub Concat(Dest As String, Source As String)
    Dim L As Long
    L = Len(Source)
    If (ccOffset + L) >= Len(Dest) Then
        If L > ccIncrement Then
            Dest = Dest & Space$(L)
        Else
            Dest = Dest & Space$(ccIncrement)
        End If
    End If
    Mid$(Dest, ccOffset + 1, L) = Source
    ccOffset = ccOffset + L
End Sub
Sub MidConcat(ByVal LoopCount As Long)
    Dim BigStr As String, I As Long
    ccOffset = 0
    For I = 1 To LoopCount
        Concat BigStr, ConcatStr
    Next I
    BigStr = Left$(BigStr, ccOffset)
End Sub


La base del funcionamiento de este algoritmo es la utilización de un buffer donde se va copiando el contenido a concatenar. Este buffer se agranda a medida que se necesita agregar más información. Es bastante interesante, pero muy engorroso.


Desafío


El desafío que me planteé es realizar un algoritmo que fuese más rápido que ambos. Para hacerlo hice una lista con las ventajas y desventajas de cada uno. En este caso, las ventajas no me interesaban mucho ya que no tenia como mejorarlas, pero si mantenerlas en mi implementación, y me interesé en analizar las desventajas.


Entonces, la principal desventaja de cada uno es:




  • Foros del web: si la concatenación es con muchos strings, el arreglo crece bastante. Esto hará que la concatenación final no sea óptima. Además, agrandar el arreglo muchas veces también tiene su penalidad.



  • MSDN: cuando se llena el buffer, hace concatenación de strings para agrandarlo.


Entonces, ¿cómo mejorarlo?. Como me interesa la elegancia del primero, utilicé la misma idea, pero en vez de tener un arreglo de muchos strings pequeños, implementé un arreglo de buffers más grandes, en donde se va copiando el contenido con Mid$, sin necesidad de concatenar. La concatenación se hace al final, pero de sólo una cantidad de buffers mucho menor a que si fuesen strings chicos.


Con este algoritmo:



  1. Evito tener un arreglo de muchos elementos que luego hay que concatenar.

  2. Evito la concatenación de strings para agrandar el buffer, ya que cuando se acaba el buffer actual, agrego un nuevo elemento al arreglo de buffers.

Código de mi súper ultra rápida concatenación de strings.






Dim oArrBlocks() As String
Dim cBlocksUsados As Long
Dim iOffset As Long ‘mantiene la posición del último carácter copiado en el último buffer del arreglo
Const cNuevosBlocks As Long = 10
Const cNuevosBlocksLength As Long = 1000

Public Sub Class_Initialize()
    cBlocksUsados = 0 ‘Se define el primer bloque a llenar
    ReDim oArrBlocks(cNuevosBlocks) ‘se crea el arreglo de bloques
    oArrBlocks(0) = Space$(cNuevosBlocksLength) ‘Se llena el primero de espacios
    iOffset = 0
End Sub

Public Sub Append(ByVal sAppend As String)
    Dim iTemp As Long
    Dim iLargoCopiado As Long
    Dim iLargoTexto As Long
   
    iLargoTexto = Len(sAppend)
   
    If (iLargoTexto > 0) Then
        ‘revisar si cabe en el bloque que se está usando como buffer
        If (iLargoTexto + iOffset <= cNuevosBlocksLength) Then
            Mid$(oArrBlocks(cBlocksUsados), iOffset + 1, iLargoTexto) = sAppend
            iOffset = iOffset + iLargoTexto
        Else ‘ si no, hacer ajustes y particionar
            ‘Se copia lo que cabe en el bloque actual
            iLargoCopiado = cNuevosBlocksLength – iOffset
            If (iLargoCopiado > 0) Then
                Mid$(oArrBlocks(cBlocksUsados), iOffset + 1, iLargoCopiado) = Left$(sAppend, iLargoCopiado)
            End If
            ‘se crea un nuevo bloque y se copia el resto ahí.
            ‘Hay espacios disponibles en el arreglo de bloques?
            iTemp = UBound(oArrBlocks)
            If (iTemp = cBlocksUsados) Then
                iTemp = iTemp + cNuevosBlocks
                ReDim Preserve oArrBlocks(iTemp)
            End If
            cBlocksUsados = cBlocksUsados + 1
            iOffset = 0
            oArrBlocks(cBlocksUsados) = Space$(cNuevosBlocksLength)
            ‘Se copia el resto en el nuevo bloque
            iLargoCopiado = iLargoTexto – iLargoCopiado
            Mid$(oArrBlocks(cBlocksUsados), iOffset + 1, iLargoCopiado) = Right$(sAppend, iLargoCopiado)
            iOffset = iLargoCopiado
        End If
    End If
End Sub

Public Function ToString() As String
    oArrBlocks(cBlocksUsados) = Left$(oArrBlocks(cBlocksUsados), iOffset)
    ToString = Join$(oArrBlocks, “”)
End Function


¿Y los resultados?


Para concatenaciones pequeñas de caracteres, cualquiera de los tres es bastante eficiente. Sin embargo, cuando la cantidad de elementos a concatenar supera varias decenas de miles, se empieza a notar la diferencia. La unidad de medición para la prueba son los ticks, tomados antes y después de cada simulación. Para ser justos con la concatenación bruta (str = str & str2), en los otros algoritmos se incluyó el tiempo de creación y destrucción de objetos en cada una de las pruebas pertinentes. Cada prueba se realizó 5 veces, ingresando en la próxima tabla, los valores promedio.











































Algoritmo\Cantidad strings 1.000 5.000 10.000 25.000 50.000 100.000
Concatenación bruta 6 216 1.436 38.003 166.180 *
Foros del web 3 6,4 9,4 50 124,75 400
MSDN 0 3 15,4 37,4 105,75 356,2
Mi algoritmo 0 3 3 9,6 27,25 53

Para la prueba de 100.000 concatenaciones decidí excluir la concatenación bruta porque probablemente todavía estaría corriendo. [:)]


El siguiente gráfico muestra una curva con los resultados para los 3 algoritmos. Nuevamente no incluí la concatenación bruta ya que el grafico tendría una sola línea visible. Los otros algoritmos se dibujarían como líneas planas casi pegados a cero.



Conclusión


Sin lugar a dudas, el algoritmo logrado, que combina lo mejor y corrige lo peor de los dos anteriores, posee un mejor rendimiento, en especial, cuando la cantidad de elementos a concatenar es bastante. Para concatenaciones breves, cualquiera de los tres es igual de bueno.


Lamentablemente, hoy en día, este algoritmo no será muy utilizado ya que como comenté al inicio, ya casi no se hace desarrollo sobre Visual Basic 6.0 y para .net existe el objeto StringBuilder.


Como consuelo personal, rescato el ejercicio mental realizado hoy y los resultados obtenidos. Da gusto saber que aún “la neurona” responde.


desde Sao Paulo
Patrick.

6 Replies to “Concatenación ultra rápida en Visual Basic 6.0 (ejercicio mental)”

  1. Me parece excelente, lo voy a probar. Pienso que es muy útil para aplicaciones que todavía no se han migrado a .NET y que se necesita que sean rápidas.

  2. Walter,

    cuéntame como te fue con las pruebas. No tengo registros de que alguien lo haya usado más allá de pruebas experimentales. La información que proveas será muy valiosa.

    Saludos,

    Patrick.

  3. He probado tú código en una aplicación que estoy desarrollando, donde genero una tabla en Html que luego se mostrará en un correo electronico, y la verdad es que funciona perfectamente.
    Saludos y gracias

  4. Car loan calculators are certainly a boon to people are willing to buy a fresh car and
    don’t have any idea in regards to the cost of it cheap avicii tickets because of pressure to trade
    the products, several will head for whatever means necessary to
    satisfy their quotas.

  5. The PA report continues: Lukaku has become in fine form,
    netting seven goals and being preferred to Shane Long because the lone central striker
    in many of the Baggies’ recent matches avicii tickets
    2014 in us (http://getaviciitickets.com) it can be an easy task to get captivated by the atmosphere of the holidays
    and save money than you can afford.

Leave a Reply

Your email address will not be published. Required fields are marked *