Wath is the best performance to use an array, and fast find string in it?
dictionarary, collection or join&instr
Printable View
Wath is the best performance to use an array, and fast find string in it?
dictionarary, collection or join&instr
If you're starting with an array, then the fastest solution is looping through the array. You have to access every element to set up the other options you're considering.
What size are the data sets you're talking about? For small sets, the only appreciable difference is going to be the internal exception that is raised when a string is not found in the collection index.
For 99% of purposes, regular VB functions will be more than fast enough. If you're in one of those rare situations where VB isn't keeping up,
http://www.xbeat.net/vbspeed
*rubs chin beard* really? Can you explain that? I'm not sure I completely agree with those two statements.Quote:
Originally Posted by ahenry
-tg
For a 1D-Array of Strings there is always the Filter-Function https://www.automateexcel.com/vba/fi...rays-function/
When the array is sorted then you can use a binary search on the array.
That's quite fast.
Quote:
Originally Posted by Arnoutdv
True, but it would return only the first match.
As for dictionary and collection: to work reasonably quick finding a string, the added strings have to be both: Key and Value
limiting both (Dic and Col) to no duplicates and exact matches.
The Filter-Function for 1D-StringArray can do partial match, case-(in)sensitive and even negation
here with Instr
but as usuall you never show what you tried to code yourself, so here another Code for HDDCode:Private FileName As String
Private cCol As Collection
Private Sub Command1_Click()
Dim s As String
On Error GoTo Fehler
s = Text1.Text & " = " & cCol(Text1.Text)
MsgBox s
On Error GoTo 0
Exit Sub
Fehler:
MsgBox Text1.Text & " not found"
On Error GoTo 0
End Sub
Private Sub Form_Load()
FileName = "E:\TestFolder\Luca.txt"
'create TestFile
WriteFile
ReadFileInCollection
Text1.Text = "Apple"
End Sub
Private Sub WriteFile()
Dim FNr As Integer
FNr = FreeFile
Open FileName For Output As #FNr
Print #FNr, "'comment = whatever"
Print #FNr, "Apple = green"
Print #FNr, "Tomato = red"
Print #FNr, "Banana = yellow"
Close #FNr
End Sub
Private Sub ReadFileInCollection()
Dim FNr As Integer
Dim s As String, s1() As String
Dim i As Long
Set cCol = Nothing
Set cCol = New Collection
FNr = FreeFile
Open FileName For Input As #FNr
Do While Not EOF(FNr)
Line Input #FNr, s
i = InStr(1, s, "'")
If i > 0 Then
'remove comment in File
s = Left$(s, i - 1)
End If
If InStr(1, s, "=") > 0 Then
'= found
s1() = Split(s, "=")
cCol.Add Trim(s1(1)), Trim(s1(0))
End If
Loop
Close #FNr
End Sub
In my opinion it depends on what problem you are trying to solve. Could you please perhaps elaborate.
Each of the things you mention have their own strengths and weaknesses.
thanks
That is precisely correct.Quote:
Originally Posted by vbwins
Collections are very nice in that they're organized as a binary tree (if you supply keys) for quick searching/finding. They also have these features:
- Their creation class is built into VB6.
- You can iterate them with the For Each syntax.
- Their data item is a Variant so pretty much anything can be stored in them.
- They also have forward and backward index pointers for looped access.
- Additions and (more importantly) deletions are trivial.
- There is "balancing" code for the binary tree when adding items.
When I have a list of items that's going to be massaged, I find Collections extremely useful.
There is also the Dictionary object. Compared to Collections, it has one upside and one downside. The upside is that it uses a hash table for key lookups, so it's faster at that. The downside is that it's not a VB6 built-in class.
---------
I suppose, the downside of Collections compared to regular arrays is that there's a bit more overhead, specifically in two areas: 1) Each item takes a structure (see below), and 2) The data is a Variant rather than the specific data type you wish to store. Regarding #2, I've gotten very comfortable with Variants through the years, and find that small amount of overhead very acceptable (just look up the VT and then fetch the data out of the Variant's remaining 14 bytes, no biggie). Regarding #1, here's the structure of each Collection's item.
Collection Item structure:
And each instantiated Collection has the following header:Code:
Private Type VbCollectionItem
Data As Variant ' Ox00
Key As String ' Ox10
pPrevIndexedItem As Long ' Ox14
pNextIndexedItem As Long ' Ox18
pvUnknown As Long ' Ox1C
pParentItem As Long ' Ox20
pRightBranch As Long ' Ox24
pLeftBranch As Long ' Ox28
bFlag As Boolean ' Ox2C
End Type ' Ox30 ' Length. (boolean padded to 4)
With that information, we could essentially "roll our own" pretty easily if we wanted. Possibly a part a bit more complex is the "tree balancing" that the VB6 Collection Class performs, but that's only run on an Add item.Code:
Private Type VbCollectionHeader
pInterface1 As Long ' Ox00
pInterface2 As Long ' Ox04
pInterface3 As Long ' Ox08
lRefCounter As Long ' Ox0C
Count As Long ' Ox10
pvUnk1 As Long ' Ox14
pFirstIndexedItem As Long ' Ox18
pLastIndexedItem As Long ' Ox1C
pvUnk4 As Long ' Ox20
pRootTreeItem As Long ' Ox24 ' This is actually a pointer to what's typically thought of as the root.
pEndTreePtr As Long ' Ox28 ' This is effectively an EOF marker for the tree (bottom of it). It points to the end of the VbCollectionHeader (HdrPtr + &h30)
pvUnk5 As Long ' Ox2C
End Type ' Ox30 ' Length.
downsides for collections when used that way (using the Key):
no duplicates allowed
no partial match
no case-insensivity
Don‘t get me wrong: i use collections all the time, we just shouldn’t forget the downsides
Zvoni, you are correct but the plusses and minuses of lookup keys is another whole discussion. I guess another approach to a list is to create a memory-based ADO recordset. Doing that, we'd have all the search power allowed for SQL SELECT statements. We would have the ADO reference, but that's no biggie. Also, setting up those memory-based ADO recordsets does take a bit of doing, but also, no biggie. Someone should create a class for that and post it in the codebank. I haven't searched, maybe it's already done.Quote:
Originally Posted by Zvoni
2/3 of those can be eliminated by using Olaf's CHashD class: https://www.vbforums.com/showthread....lass-(no-APIs). As an added bonus, it's faster than the VB6 Collection class for adds & lookups.Quote:
Originally Posted by Zvoni
Tks tò the all.
But really my problem Is the numbers of item in my dataset, Is approx 120.xxx items.
And if i use a loop with a for next, i think not Is a good solution, for a find,or not?
Luca,
are those items „unique“ as in: no duplicates?
if yes, a collection is your best bet.
and you mention „dataset“: by any chance, is there a database in play?
I just did a test of 466550 words stored in both an Array and in a CHashD object. I performed 1000 look-ups for randomly selected Keys. The array looping lookups took around 6 seconds (compiled with all optimizations). The CHashD lookups took about 6 milliseconds.
In The data Not possibile duplicate Key! SureQuote:
Originally Posted by Zvoni
Then an sorted array with a binary search should be the fastest method
Not necessarily.Quote:
Originally Posted by Arnoutdv
When you have (as mentioned by the OP) about 120,000 entries -
then a binary-search (on a sorted Array) will need about 16-17 "full string-coparisons" (with the searchstring).
Most HashList-implementations can complete an exists-check with fewer operations/comparisons
(when the amount of data to search, is as large as the OPs).
E.g. the cHashD-Class which was mentioned, is faster than the RC5/6-cSortedDictionary-Class in such a scenario.
Olaf
I did a basic test with a binary search and the cHashList.
Compiled, fast code only, the binary search performs about 15% better compared to cHashList
But I really like the elegancy of cHashList!
Code:Option Explicit
Private Declare Function GetTickCount Lib "kernel32" () As Long
Private Sub Form_Click()
Dim t As Long
Dim sArray() As String
Dim i As Long, j As Long
Dim s(999) As String
Dim lIndex As Long, bExist As Boolean
ReDim sArray(120000 - 1)
For i = 0 To UBound(sArray)
sArray(i) = "K:" & Format(CStr(i), "0000000")
Next i
Dim cHL As clsHashList
Set cHL = New clsHashList
cHL.ReInit 120000
For i = 0 To UBound(sArray)
cHL.Add i, sArray(i)
Next i
For i = 0 To 999
s(i) = "K:" & Format(Int(Rnd * 120000), "0000000")
Next i
t = GetTickCount
For j = 1 To 1000: For i = 0 To 999
lIndex = GetIndexStringArray(s(i), sArray)
Next: Next
Print "GetIndex: " & GetTickCount - t
t = GetTickCount
For j = 1 To 1000: For i = 0 To 999
bExist = cHL.Exists(s(i))
Next: Next
Print "HashList: " & GetTickCount - t
End Sub
Public Function GetIndexStringArray(ByVal sID As String, sArray() As String) As Long
Dim lFirst As Long
Dim lLast As Long
Dim lMiddle As Long
Dim lSteps As Long
' assume search failed
GetIndexStringArray = -1
lFirst = 0
lLast = UBound(sArray)
Do
'lSteps = lSteps + 1
lMiddle = (lFirst + lLast) \ 2
Select Case StrComp(sID, sArray(lMiddle), vbBinaryCompare)
Case 0
GetIndexStringArray = lMiddle
Exit Do
Case 1
lFirst = lMiddle + 1
Case Else
lLast = lMiddle - 1
End Select
Loop Until lFirst > lLast
End Function
Try against the modified CHashD class linked a bit further down the post (Or directly here: https://www.vbforums.com/attachment....9&d=1473008813)
In my test it was about almost twice as fast as the binary search. Note that the Add method parameters are flipped, so you should reverse the order of the parameters in your test code.
Yep, this one performs even better than the "bare-bones, first implementation".Quote:
Originally Posted by jpbro
(despite supporting "all kind of Key-Types" via Variant-Key-Params).
Also, the CompareMode didn't match in Arnouts example (cHashD defaults to vbTextCompare)...
below is an adjusted example (using the cHashD-Code from your Zip), which native-copiled is:
- about twice as fast in bincomp-mode
- and about 2.8 times as fast in text-comparemode
HTHCode:Option Explicit
Private Declare Function GetTickCount Lib "kernel32" () As Long
Private Sub Form_Click()
Dim t As Long
Dim sArray() As String
Dim i As Long, j As Long
Dim S(999) As String
Dim lIndex As Long
ReDim sArray(120000 - 1)
For i = 0 To UBound(sArray)
sArray(i) = "K:" & Format(CStr(i), "0000000")
Next i
Const CompareMode = vbTextCompare
' Const CompareMode = vbBinaryCompare
Dim cHL As clsHashList
Set cHL = New clsHashList
cHL.ReInit 120000
cHL.CompareMode = CompareMode
For i = 0 To UBound(sArray)
cHL.Add sArray(i), i
Next i
For i = 0 To 999
S(i) = "K:" & Format(Int(Rnd * 120000), "0000000")
Next i
t = GetTickCount
For j = 1 To 1000: For i = 0 To 999
lIndex = GetIndexStringArray(S(i), sArray, CompareMode)
Next: Next
Print "GetIndex: " & GetTickCount - t
t = GetTickCount
For j = 1 To 1000: For i = 0 To 999
lIndex = cHL.IndexByKey(S(i))
Next: Next
Print "HashList: " & GetTickCount - t
End Sub
Public Function GetIndexStringArray(ByVal sID As String, sArray() As String, Optional ByVal CompareMode As VbCompareMethod) As Long
Dim lFirst As Long
Dim lLast As Long
Dim lMiddle As Long
Dim lSteps As Long
' assume search failed
GetIndexStringArray = -1
lFirst = 0
lLast = UBound(sArray)
Do
'lSteps = lSteps + 1
lMiddle = (lFirst + lLast) \ 2
Select Case StrComp(sID, sArray(lMiddle), CompareMode)
Case 0
GetIndexStringArray = lMiddle
Exit Do
Case 1
lFirst = lMiddle + 1
Case Else
lLast = lMiddle - 1
End Select
Loop Until lFirst > lLast
End Function
Olaf
I missed the update in the original thread.
Indeed with the cHashD the performance is twice as fast, thanks for the heads up!
FWIW, a further optimized variant of cHashD is contained in RC6Quote:
Originally Posted by Arnoutdv
(performing in this scenario about factor 3-3.5 better in both modes, binary and textcompare):
OlafCode:Option Explicit
Private Sub Form_Click()
Dim sArray() As String, K(999) As String
Dim i As Long, lIndex As Long
ReDim sArray(120000 - 1)
For i = 0 To UBound(sArray)
sArray(i) = "K:" & Format(CStr(i), "0000000")
Next i
' Const CompareMode = vbTextCompare
Const CompareMode = vbBinaryCompare
Dim cHL As cHashD
Set cHL = New_c.HashD(120000, False)
cHL.StringCompareMode = CompareMode
For i = 0 To UBound(sArray)
cHL.Add sArray(i), i
Next i
For i = 0 To UBound(K)
K(i) = "K:" & Format(Int(Rnd * 120000), "0000000")
Next i
For i = 0 To UBound(K) 'just to test for "formal correctness" of the algos
If cHL.IndexByKey(K(i)) <> GetIndexStringArray(K(i), sArray, CompareMode) Then
MsgBox "The found indexes do not match": Exit Sub
End If
Next
New_c.Timing True
For i = 0 To UBound(K)
lIndex = GetIndexStringArray(K(i), sArray, CompareMode)
Next
Print "GetIndex: " & New_c.Timing
New_c.Timing True
For i = 0 To UBound(K)
lIndex = cHL.IndexByKey(K(i))
Next
Print "HashList: " & New_c.Timing
End Sub
Public Function GetIndexStringArray(ByVal sID As String, sArray() As String, Optional ByVal CompareMode As VbCompareMethod) As Long
Dim lFirst As Long
Dim lLast As Long
Dim lMiddle As Long
Dim lSteps As Long
' assume search failed
GetIndexStringArray = -1
lFirst = 0
lLast = UBound(sArray)
Do
'lSteps = lSteps + 1
lMiddle = (lFirst + lLast) \ 2
Select Case StrComp(sID, sArray(lMiddle), CompareMode)
Case 0
GetIndexStringArray = lMiddle
Exit Do
Case 1
lFirst = lMiddle + 1
Case Else
lLast = lMiddle - 1
End Select
Loop Until lFirst > lLast
End Function
Only problem with this is that its limited to 1200 hash buckets. When there are a lot of collisions it gets much slower.Quote:
There is also the Dictionary object. Compared to Collections, it has one upside and one downside. The upside is that it uses a hash table for key lookups, so it's faster at that. The downside is that it's not a VB6 built-in class.
In case I missed it what is the key. A string?Quote:
Originally Posted by luca90
Quote:
Originally Posted by vbwins
Code:
Private Type VbCollectionItem
Data As Variant ' Ox00
Key As String ' <---------------- Ox10
pPrevIndexedItem As Long ' Ox14
pNextIndexedItem As Long ' Ox18
pvUnknown As Long ' Ox1C
pParentItem As Long ' Ox20
pRightBranch As Long ' Ox24
pLeftBranch As Long ' Ox28
bFlag As Boolean ' Ox2C
End Type ' Ox30 ' Length. (boolean padded to 4)
Sorry I meant what is key the OP wants to use.
It‘s a simple 1D-array of strings, all unique (no duplicates).Quote:
Originally Posted by vbwins
for Collection/Dictionary the array-member would be key and value.
i still don‘t understand why he just doesn’t test the performance on his dataset with all possibilities mentioned:
collection
dictionary
filter-function for string-arrays
Hash-thingy in RC6
binary search on array
whatever i missed….
EDIT: one downside not mentioned for binary search: array must be sorted.
so there might be another penalty hidden there
The Hash-thingy is also available as pure VB6 source, without requiring RC6 at all (though apparently there is a further optimized version in RC6).Quote:
Originally Posted by Zvoni
Just thought I'd mention this in case anyone was scared off thinking they had to use a separate library/reference.