Speed up string operations

canalrun said:

Hello,
I am doing heavy-duty string operations:
CharAt
IndexOf
"RemLet" (my remove letter)

Within a short string (10 characters or less) I have to extract a particular character. Using that character I have to see if it exists in another short string (10 characters or less). And, if it does I have to remove that character from the second string.

I am using the String data type. I see there is also a StringBuilder; it does not have an IndexOf, but it has a Remove. String has an IndexOf but no Remove.

For my Remove, I am basically using:
t = s.SubString2(0, pos) & s.SubString(pos+1)

the operations I'm performing take about 2 min. I would like to speed that up if possible.

Can anyone suggest a faster way to work worth short strings? The key functions are equivalents to: CharAt, IndexOf, and Remove.

Thanks,
Barry.

Click to expand...

Erel said:

Can you post your algorithm code?

Click to expand...

tr(2).srt = DateTime.Now

     For i=0 To ScrList.Size-1 ' for each list word
       If (i Mod 1000 = 0) Then ' update progressbar
        k = 2 + 98 * (i/ScrList.Size)
        pbrPB1.Progress = k
      End If
      
        DoEvents
      If (fSrchCancel = True) Then
         PgShow = 0
         pnlSwap(pnlMain, pnlMain)
        Return
      End If

        s = ScrList.Get(i)
      s = s.ToUpperCase
      l = s.Length
      
tr(3).srt = DateTime.Now

      For j=0 To l2-1 ' for each let match check if it has remainder
          ts = s ' temp word
          p1 = ts.IndexOf(s2.CharAt(j))
        
          If (p1 >= 0) Then
          ts = RemLet(ts, p1) ' remove first occurrence of let form word
        Else
          Continue ' try next let. word must have let
        End If
         
          fmtch = True
          ts1 = s1 ' temp letters
         
 tr(4).srt = DateTime.Now

         For k=0 To ts.Length-1 ' check if each let of temp word is in letters
            p1 = ts1.IndexOf(ts.CharAt(k))
           
            If (p1 >= 0) Then
              RemLet(ts1, p1) ' letter used in match
            Else
                fmtch = False
                Exit ' word let not in letters
            End If
          Next
         
tr(4).end = DateTime.Now
tr(4).tot = tr(4).tot + (tr(4).end - tr(4).srt)

          If (fmtch = True) Then ' add word to results table
            v(0) = ScrList.Get(i)
            v(1) = ScoreWord(v(0))
            v(2) = v(0).Length
            SQL1.ExecNonQuery2("INSERT INTO restmp (mword, mscore, mlen) VALUES (?, ?, ?)", v)
          End If
        Next

tr(3).end = DateTime.Now
tr(3).tot = tr(3).tot + (tr(3).end - tr(3).srt)

     Next ' next word

tr(2).tot = DateTime.Now - tr(2).srt

Log("*** tr2 = " & tr(2).tot)
Log("*** tr3 = " & tr(3).tot)
Log("*** tr4 = " & tr(4).tot)

   End If

Sub RemLet(str As String, pos As Int) As String
  Dim l As Int
  Dim s, t As String

  l = str.Length
  s = str
  
  If (l <= 1) Then
    t = ""
  Else
    If (pos >= l) Then
     t = s
   Else
      If (pos = 0) Then
       t = s.SubString(1)
     Else
        If (pos = l-1) Then
        t = s.SubString2(0, l-1)
      Else
          t = s.SubString2(0, pos) & s.SubString(pos+1)
      End If
     End If
   End If
  End If
  
  Return t  
End Sub

canalrun said:

String has an IndexOf but no Remove.

Click to expand...

kickaha said:

Try this for RemLet

B4X:

Sub RemLet(str As String, pos As Int) As String

Dim l As Int
l = str.Length

If (l = 0) Then Return ""
If (pos >= l) Then Return str
If (pos = 0) Then Return str.SubString(1)
If (pos = l-1) Then Return str.SubString2(0, l-1)
Return str.SubString2(0, pos) & str.SubString(pos+1)  

End Sub

Click to expand...

Erel said:

There is no ByRef in Basic4android.

As Pfriemler wrote above, I recommend you to call DoEvents every 1000 iterations.

Click to expand...

Also avoiding calling Subs in the inner loop will increase performance slightly so inlining RemLet might help.[/QUOTE said:

Inlining RemLet - very good idea.

I might be able to get away with
t - str.SubString2(0, pos) & str.SubString(pos+1)
as long as it does not choke if pos = 0 or pos >= str.Length-1

My algorithm can be thought of as O(NM^2)

I would like to make my algo O(NM). That would probably help alot.

Thanks,
Barry.


Added later ...

I tried inlining. It does not choke so it must be able to handle the two edge cases.
plus I found a small "boo boo"

These two changes saved almost 30 seconds. That is livable for now.

Barry.

Click to expand...