Printable View
Hi all,
I need to compare two arrays, and it must be done fast.
I'm actually looking for a way to do this is one call (like some API function), rather than looping through the array comparing each element.
The checking will happen several times per second, and it has to compare a total of around 50 arrays, so things really need to be fast.
Any suggestions are welcome.
sounds like you're asking for magic. Even if you use an API call, do you think that there isn't a loop happening behind the scenes?
Are we supposed to guess what kind of data is in the arrays that you want to compare? Do you think it doesn't matter?
First you say you need to compare 2 arrays, then you say you need to compare around 50 arrays. Could you possibly be a little more vague? With just a tiny effort, you could make this whole problem statement completely incomprehensible.
There are several approaches you could take, but given the totally vague nature of your problem statement, I wouldn't even begin to guess what might be appropriate.
Ok, let me rephrase things.
I need to compare two BYTE arrays, and it must be done fast.
I'm actually looking for a way to do this is one call (like some API function), rather than looping through the array comparing each element.
The checking will happen several times per second, and it has to compare a total of around 50 pairs of arrays (compare arr1a with arr1b, arr2a with arr2b, arr3a with arr3b,...) so things really need to be fast.
The reason I'm looking for a API solution is because API's are generally faster, or maybe you didn't know that.
Hey Cakkie,
I'm interested in finding out how to do this too. Please post your solution (if you find one) on this thread okay.
I'd think the fastest way is to compare the memory content as a whole (the whole chunk of memory that is used to store the array). And I think this can be done since array elements are laid next to each other in the memory right?
Good Luck,
-Cool Bizs
For I = to x
text1= Text1 & Array1(i)
Next
For I = 1 to y
Text2= Text2 & Array2(i)
Next
If Text1= Text2 then
Do something
End if
I think this may not be as slow as you think.
VbBaby :D
put memcmp in a C function and put that in a DLL and call it from VB --- you can't get any faster than that
Hey Cakkie!,
I've just try with the STRCOMP() function since there is a parameter vbBinaryCompare. That snippet of code will compare two arrays. I test it and if the arrays are differents, it returns <> 0, but you could test it more and also test the rapidity of it (and let us know :))
That memcmp, in C, would give surely better result, but the question is: how it does in VB ;)Code:Dim strA(2) As Byte
Dim strB(2) As Byte
'Try changing those number to see if the arrays are differents
strA(0) = 11
strB(0) = 11
strA(1) = 11
strB(1) = 12
strA(2) = 11
strB(2) = 11
'0 if identical
MsgBox StrComp(strA, strB, vbBinaryCompare)
JeffB
Hmm, StrComp is quite a slow function, as a matter of fact it is slower than looping the array.
Currently I wrote a function that will loop through the arrays, from the moment he finds a difference, he will exit the loop and return false, if he doesn't find a difference, he returns true.
This leads to the situation that if the difference is in the beginning of the array, the function will complete faster than if it was at the end, so it has a variable speed.
About the memcmp, I checked some sources, and it's a function that isn't covered by any API function available in VB (I'm not sure you can declare functions that reside in the C-Runtime library directly, maybe some API guru can answer this?). One option would be to create a C wrapper dll, and call that from VB, like Phinds implied. This would result in a dll of about 50K.
For now I'm going to stick with what I have, and optimize the code to the farest possible extent.
Thanks for you help.
Ok so StrComp() a poor function... :D
Well anyway, in C, browsing an array can be optimized. Instead of using a for loop, you can use pointers and pointers incrementation. Again, you have to use a dll. :)
JeffB
;) ;)Code:
'If it were Asp, it could have be done the following way.
But I would not swear on its speed.... Since it is Vb,
Colbiz must be right: there should be some way to
test the block of memory...
But if not Duncan, then.....
<HTML>
<SCRIPT language="vbscript">
dim a1, a2
dim i
dim Compare1, Compare2
redim a1(50)
redim a2(50)
'filling array for testing pourpouse
for i = 0 to 49
a1(i)=i
a2(i)=i
next
a1(50)=6
a2(50)=7 'difference in last cell
'Now the compare job
Compare1 = join(a1,",")
Compare2= join(a2,",")
if Compare1<>Compare2 then
msgbox "Different"
else
msgbox "Same"
end if
</Script>
</Html>
This code works for me in VB... and for "quicknest" purpose, the "," in the Join() function can be omitted and replaced by a empty string, but again, this browse the arrays 2 times (one for joining and one for comparing).
CopyMemory() API could also do the join() function work (I think... :))
JeffB
Using API calls would actually be slower in this respect as every time you call an API, VB has to load the parameters onto the stack then set the code pointer then unload them again thereafter.
I think the following is as fast as you will get:
Code:Private Function AreArraysEqual(bLhs() As Byte, bRhs() As Byte) As Boolean
Dim lIndex As Long
lIndex = 49
While (bLhs(lIndex) = bRhs(lIndex)) And lIndex
lIndex = lIndex - 1
Wend
AreArraysEqual = (lIndex = 0)
End Function
Hmm, is that so (not that I want to argue with you on API knowledge :))? An array is nothing more than an array of pointers to the actual data, along with a pointer to the next element, right? So basically all you need to do is pass the pointer of the first element, in case of vb this would be the first element (arr(0)).Quote:
Originally posted by Clearcode
Using API calls would actually be slower in this respect as every time you call an API, VB has to load the parameters onto the stack then set the code pointer then unload them again thereafter.
I know back in the time when I was writing a winsock application, that I used a lot of bytearrays. After some intensive testing, I came to the conclusion that when using copymemory to copy a part of an array to another array, things where quite faster than when using the loop method. I found this to be true excpecially with large amounts of data.
If one of the array is sorted, then, it's done. Just loop thru the unsorted array and compare with the value in sorted array using bsearch.
If none is sorted, then, the best way is to create memory index to the other array and do the same thing by bsearching the index.
Edit:
BTW, did I miss something in the question?
I can't imagine resorting immediately to API when the problem -- the way I look at it -- is purely a matter of organizing the array for fast retrieval. Although I am not very good at API, I think I have read enough so as not to doubt that API is much faster than the usual VB recipe of doing things.
But if you have 2 arrays of 100 elements each to be compared, I don’t think that API thing could match the speed of an organized comparison of 700 passes (100 elements x 7 passes each on bsearch) compared with 5000 passes (100 elements x 50 ave pass per element) for unorganized or unindexed arrays..
Theres a faster way than in C: Assembly
Ok, Im going to just disregard the suggestion to use Assembly...
I'll give you more insight in the situation, the arrays aren't sorted at all. They are filled using the GetDIBits, which get the bytes from a DeviceContext of 50x50 pixels. The result is that each array will size from somewhere around 2500 (8bit) to 7500 (24bit) elements. These need to be compared with a previously taken copy of that particular DC. If it is different, things are sent over winsock and the screen on the other side is updated accordingly.
how about instead of looping through the whole array, why not cut the array into half. that way instead of having a running time of O(n), you could cut it down to O(n/2). here's the sample code below:
and of course, some pre-calculations on the (n-i-1) operation could be done to further optimize the code. i know this isn't that fast but in my opinion there will always some loop going on to compare two arrays, even in APIs and assembly implementations. (this code has not been tested, this is only a conceptual model of some sort)Code:n = ' the size of the array
m = n \ 2
for i = 1 to m
if arrA(i) <> arrB(i) or arrA(n-i-1) <> arrB(n-i-1) then
arrayEqual = False
exit function
end if
next i
arrayEqual = True
hope this helped.
I've tested the different solution, and come to the conclusion that my solution is the fastest.
It takes an average of 770ms to compare two arrays with 5000 elements 500 times. All elements were the same, so all solutions had to traverse the entire array.
The solution given by Duncan (ClearCode), takes average 1010ms to do the same, and the code Zeroes gave took 1930ms to copmlete.
My guess is that this is because the solution of duncan does two comparisions for each element. The solution from Zeroes also does two comparisions, but does additional calculations in it, making it even slower.
Conclusion, whatever you do, keep it as simple as possible, since everything consumes time.
In C/C++ there is an available function called memcmp() used for comparing 2 buffers.
One way to utilize the function in VB (of course via API call) is to create new DLL (using C/C++ compiler), then use this function as your main comparison routine.
I hope this will help.
Owen
Yes, phinds already pointed that out.
Ok, just for the experiment, can someone create such a wrapper dll in C++? I don't have any C experience, and I don't have it installed.
No - an array is a contiguous block of memory. For example, if I have a UDT as :Quote:
An array is nothing more than an array of pointers to the actual data, along with a pointer to the next element, right?
And I have 3 of them in an array:Code:Private Type ApiPoint
ByVal x As Byte
ByVal y As Byte
End Type
Then if you were to read the memory from VarPtr(foo(0)) it would be:Code:Dim Foo(0 to 2) As ApiPoint
Foo(0).x = 20
Foo(0).y = 25
Foo(1).x = 100
Foo(1).y = 50
Foo(2).x = 75
Foo(2).y = 80
[020][025][100][050][075][080]
On average there will be more than one difference between the arrays and this means that the average first different byte will probably be in the first 25%...thus exiting out on the first difference will save time overall.Quote:
All elements were the same, so all solutions had to traverse the entire array
Oh well, I'll try to remember that, but isn't that an advantage? Say I only pass the pointer to the first element, and the length of the array, the function should have enough information? Of course, this would need the funtion to work this way (like CopyMemory)Quote:
Originally posted by Clearcode
No - an array is a contiguous block of memory.
Well, the information of the array is aquired from a DC, using GetDIBits. Blocks of 50x50 pixels are compared, and if different they are sent over winsock to another machine, which resores the image there, in other words, a remote screen program. Constantly sending the entire screen over, or sending the entire screen just because you moved you mouse a pixel isn't quite economical, is it.Quote:
On average there will be more than one difference between the arrays and this means that the average first different byte will probably be in the first 25%...thus exiting out on the first difference will save time overall.
The memcmp() function is available for export in crtdll.dll file. I hope you have the same file in your current window's system directory.
But, I can't figured out the proper API call declaration, particularly in the parameter type.
In C/C++, the prototype of memcmp() is:What should it be in Visual Basic?Code:int memcmp( const void *buf1, const void *buf2, size_t count );
Code:Private Declare Function memcmp Lib "crtdll.dll" (???, ???, ???) as Integer
I'd say:Quote:
Private Declare Function memcmp Lib "crtdll.dll" (???, ???, ???) as Integer
And call it thus:Code:Private Declare Function memcmp Lib "crtdll.dll" (buffA As Byte, BuffB As Byte, ByVal Length As Long) as Long
Code:If memcmp(BuffA(0), BuffB(0), UBound(BuffA)) Then
...
End If
Nope, I tried it and it gives a Bad Dll calling convention error.
I also tried passing the arrays as Any, since that is what CopyMemory uses, but the same error occurs. Maybe the error is in the count stuff, what datatype is count?
Hi!
I meet "CompareStringA" function. May be, it can help you. But what is the strange time they are shown!
Code:Option Explicit
Private Declare Function CompareBArray Lib "kernel32" Alias "CompareStringA" _
(ByVal Locale As Long, ByVal dwCmpFlags As Long, lpString1 As Any, _
ByVal cchCount1 As Long, lpString2 As Any, ByVal cchCount2 As Long) _
As Long
Private Sub Form_Load()
Dim i As Long, nRepeat As Long, a(1000) As Byte, b(1000) As Byte, fTime As Single
For i = LBound(a) To UBound(a)
a(i) = 50
b(i) = 50
Next i
i = 1000 ' Where is a difference. i = LBound(a) ... UBound(a)
a(i) = 100
b(i) = 101
nRepeat = 10000
fTime = Timer: Call f1cmp(a, b, nRepeat): Debug.Print "f1cmp = ", Timer - fTime, "sec"
fTime = Timer: Call f2cmp(a, b, nRepeat): Debug.Print "f2cmp = ", Timer - fTime, "sec"
fTime = Timer: Call f3cmp(a, b, nRepeat): Debug.Print "f3cmp = ", Timer - fTime, "sec"
Unload Me
End Sub
Sub f1cmp(a() As Byte, b() As Byte, ByVal nRepeat As Long)
Dim i As Long, n As Long
n = UBound(a) - LBound(a) + 1
For i = 0 To nRepeat
CompareBArray 0, 0, a(0), n, b(0), n
Next i
End Sub
Sub f2cmp(a() As Byte, b() As Byte, ByVal nRepeat As Long)
Dim i As Long
For i = 0 To nRepeat
StrComp a, b, vbBinaryCompare
Next i
End Sub
Sub f3cmp(a() As Byte, b() As Byte, ByVal nRepeat As Long)
Dim i As Long, n As Long
For i = 0 To nRepeat
For n = LBound(a) To UBound(a)
If a(n) <> b(n) Then
Exit For
End If
Next n
Next i
End Sub
That last post is interesting, actually, StrComp() is quicker than browsing all the array. The API seems pretty much the same as StrComp() ;)
JeffB
Ok, I added the two function to my benchmark, and appearantly StrComp is the fastest. I must admit that I didn't test that at first, because I though it would be miserably slow, so I guess the winner is JeffB ;)
Ok, to complete the test results:
500 times, 5000 element array, times are in ms
Code:The Cakkie way (loop through array): 773,3611
The Zerroes way, (half loop, double check): 1933,04
The Duncan way (while): 1030,899
The JeffB way (StrComp): 15,63858
The Vi2 way (CompareStringA): 27,82504
It seems that memcmp() API function won't work. I've just find a CompareMemory() API in the ntdll.dll (I use NT4 so I have the ntdll.dll, maybe you don't have it) anyway, here is how to use it, maybe you could test it Cakkie :
It's interesting since it returns how many elements are the same. Anyway, maybe it is quicker than StrComp() :) ;)Code:Private Declare Function CompareMemory Lib "Ntdll.dll" Alias "RtlCompareMemory" (buffA As Any, buffB As Any, ByVal Length As Long) As Long
Private Sub Command1_Click()
Dim buffA(10) As Byte
Dim buffB(10) As Byte
Dim x As Integer
For x = 0 To 10
buffA(x) = 10
buffB(x) = 10
Next x
'buffA(9) = 45
'Last element different
buffA(10) = 35
buffB(10) = 33
Dim ret As Long
'Return how many elements are the same
ret = CompareMemory(buffA(0), buffB(0), 11)
If ret <> 11 Then
MsgBox "Different: " & ret
Else
MsgBox "Same:" & ret
End If
End Sub
JeffB
Excellent job JeffB!
Wierd thing is, from MSDN October 2002, RTLCompareMemory() is only included in Win2K and XP. But you've proved them wrong ... (how come I'm not surprised?) ... ahhh good old M$ documentation :)
:)
-Cool Bizs
I'm just getting started in VB, but I have good knowledge of c++ so I'll make some points I encountered on reading this thread. First, memcpy accepts pointers as its first arguments. I'm still not clear about this in VB, but it looked like the above tried to put bytes in them?
Also, real pickiness here so ignore if not interested, but O(n) = O(n/2). The O operator in math ignores coefficients and is used mainly to compare different types of increases (linear v. quadratic, etc.). But the above algorithm would either not give a halving of time, or would not solve the comparison properly if I followed it correctly. Anyways, this is an O(n) problem but you can optimize by taking out some of the loop comparisons by "unwinding" it and comparing groups of numbers if your willing to state some byte boundaries to declare your array on (ie. declare array sizes in only multiples of four, etc.). Also should take out any extraneous material from inner loop. But using an optimized API seems best.
Anyway, just looking through the threads and trying to learn. If my post is off target in any way, I appologize. This is an interesting discussion that has already taught me some important VB lessons!
Ok, the RtlCompareMemory really kicks a$$. It get's the job done in 5,668877 ms.
The downpart of this is that is only runs on Nt/2K/XP.
Anyway, it is worth mentioning though.
What about MD5 checksum comparison?
Maybe not a smart one, but I can say that it works fine.
In some cases, maybe Cakkies' too, we can control the creation of the arrays and check the stored data at that time plus setting some kind of flags. So when the time comes to check the arrays the only thing we have to do is to check that flags, not the actual contents. In simple words the actual search takes place on the fly when the arrays are updating its elements one at a time (data store time).
This is very tricky when you have time when loading elements, and do not have much when the compare must be done.
Well, moreover in this situation instead of eventualy checking for the screen changes we can implement a hook routine to effeciently notify the remote for such changes. But this is much more advanced and more complicated than simply using the timer to generate the event...
However, StrComp function is the fastest way over other straight-forward or conceptual functions, but believe this no one has ever cited the InStrB function which is suppose to be second in the rank.
Cheers everyone!;)