String Addition (Optimization)

[SMcNeill]

Code: (Select All)

Const limit = 200000

Dim Shared NumStr(limit) As String



MakeNumsStrings

t# = Timer(0.001)

o$ = AddStrings 'time how long it takes to add those strings together

t1# = Timer(0.001)

o1$ = MidStrings(Len(o$)) 'and time how long it takes to just mid$ those strings, if you know the size

t2# = Timer(0.001)



Print "Results:"

Print "First 50: "; Left$(o$, 50)

Print "First 50: "; Left$(o1$, 50)

Print "Last  50: "; Right$(o$, 50)

Print "Last  50: "; Right$(o$, 50)

Print

Print

Print Using "It took ###.### seconds to AddStrings"; t1# - t#

Print Using "It took ###.### seconds to MidStrings"; t2# - t1#



Sub MakeNumsStrings

    For i = 1 To limit

        NumStr(i) = _Trim$(Str$(i))

    Next

End Sub



Function AddStrings$

    For i = 1 To limit

        temp$ = temp$ + NumStr(i)

    Next

    AddStrings = temp$

End Function



Function MidStrings$ (size)

    temp$ = Space$(size)

    p = 1 'position in full string

    For i = 1 To limit

        Mid$(temp$, p) = NumStr(i)

        p = p + Len(NumStr(i))

    Next

    MidStrings = temp$

End Function

I think the code above helps showcase one of QB64's and QB64PE's greatest flaws -- the time it takes to do anything substantial with strings!

The above simply makes a list of strings, by using the numbers from 1 to whatever LIMIT we set, and then it adds those strings all into one massive string.   Basicially "1" + "2" + "3" +... = "123..." -- a simple process, but all that is needed to showcase how slow this process can become. 

In the above, I've made use of two different methods for speed comparison, for folks.  

The first method is what we see a lot in our programs:  temp$ = temp$ + num$.  It simply adds the strings together over and over until it's finished.

The second method is much more efficient:  mid%(temp$, p) = num$.  This has to pre-allocate the proper size of the string, create the string, and then it simply uses mid$ to swap out the proper portion of that string with num$ as it goes along.

I won't post my times on this, as I'd prefer for folks to run this code at least once themselves and see what the difference in speed might be on their own system, with whatever compiler flags/optimizations they might be using.  Let's just say that I'm certain folks should be able to see a noticeable difference here.

NOTE:  And one important thing to note here -- the larger the strings involved, the greater the difference becomes.  The difference here isn't a static, "it takes 0.1 seconds to perform X additions to the string".  Change that limit and you can see for yourself.  A limit of 100000 takes X seconds.  A limit of 110000 takes 2 * x seconds.  A limit of 120000 takes 4 * x seconds.  Exponential time increases as string length increases!!  (Though not quite as bad as the * 2 modifier I just tossed out as an example to the left there.   )

---

Take away from all this??

If you're going to be doing a lot of string addition, you'd probably be better served by running it through two loops, instead of just adding the strings together in one.

Loop 1:   Count the total size of the string
FOR i = 1 TO limit
    totalSize = totalSize + len(num$(i))
NEXT

Allocate the output string first:   
temp$ = SPACE$(totalSize)

Loop 2: Mid$ the string together instead of adding it
p = 1
FOR i = 1 TO limit
    mid$(temp$, p) = num(i)
    p = p + len(num(i))
NEXT

---

It's thinking outside the box, and it's not the way that most folks tend to do things, but I'd think the above showcases WHY this might be an important concept to keep under your hat, if you're ever doing any serious string work in your projects.

(And feel free to post your own times below.  I'd love to see how large a difference such a simple approach makes for most people on their own systems.  I just don't want to spoil the surprise by posting my own times here, and you guys might not want to read below this post until you run the code for yourself once, just for the "pop factor" of the figures.  )