Introduction
One of my projects is to solve a problem of database searching speed. The first version of the application uses ADOCE. My client wants to convert flat text file from PC to Pocket PC database via ActiveSync. We kept getting calls from them complaining about the speed of conversion after the first version was released.
Then I did some testing on a 5000 records small database. It took around 20 minutes to do that. That was unacceptable. Therefore, I decided to use a flat text file as database container since our application uses it as read only.
The first thing we have to do is to sort our text file. The demo project includes a testing database (MyFile.txt). It is a pure flat text file. Each line has two columns separated by the “|” letter. (You can define your own separation letter.) The first column will be the searching index.
Click the Load button, the system will open MyFile.txt, sort it and load it into your system memory. I use Fast Quick Sort algorithm (see List1 and List 2) for sorting. The result is stored in a retarray
variable, and uses binary searching algorithm to perform the searching function (see List3).
I was very much satisfied with the result. It only took 30 seconds to transfer the text file from PC to PPC and another 30 seconds to sort it. The binary searching algorithm is very efficient. The demo project will display the searching time and how many items searched during one search.
List1
Private Function QuickSort(l As Integer, r As Integer)
Dim M, i, j, v
M = 4
If (r - l) > M Then
i = (r + l) / 2
If getkey(retarray(l)) > getkey(retarray(i)) Then
swap l, i End If
If getkey(retarray(l)) > getkey(retarray(r)) Then
swap l, r
End If
If getkey(retarray(i)) > getkey(retarray(r)) Then
swap i, r
End If
j = r - 1
swap i, j
i = l
v = retarray(j)
Do While (True)
i = i + 1
Do While (getkey(retarray(i)) < getkey(v))
i = i + 1
Loop
j = j - 1
Do While (getkey(retarray(j)) > getkey(v))
j = j - 1
Loop
If (j < i) Then
Exit Do
End If
swap i, j
Loop
swap i, r - 1
QuickSort l, j
QuickSort i + 1, r
End If
End Function
List 2
Private Function InsertionSort(lo0 As Integer, hi0 As Integer)
Dim i1, j1, v1
For i1 = lo0 + 1 To hi0
v1 = retarray(i1)
j1 = i1
Do While ((j1 > lo0))
If (getkey(retarray(j1 - 1)) > getkey(v1)) Then
retarray(j1) = retarray(j1 - 1)
j1 = j1 - 1
Else
Exit Do
End If
Loop
retarray(j1) = v1
Next
End Function
List3
Function bisearch(Target As String, ByRef bk, _
ByRef totalrec, ByRef searchcount)
Dim midone, first, last, ret, temp
Dim i
ret = False
first = 0
last = UBound(retarray) - 1
totalrec = last
i = 0
Do While (first <= last)
midone = Round((first + last) / 2)
temp = retarray(midone)
temp2 = Split(temp, "|")
If UCase(Trim(temp2(0))) = UCase(Trim(Target)) Then
ret = True
bk = temp
Exit Do
End If
If UCase(Trim(temp2(0))) > UCase(Trim(Target)) Then
last = midone - 1
Else
first = midone + 1
End If
i = i + 1
Loop
searchcount = i
bisearch = ret
End Function