Compare two arrays, FAST

[Cakkie]

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.

[zeroes]

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:

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

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)
hope this helped.

[Cakkie]

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.

[owenrb]

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

[Cakkie]

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.

[Clearcode]

An array is nothing more than an array of pointers to the actual data, along with a pointer to the next element, right?

No - an array is a contiguous block of memory. For example, if I have a UDT as :

Private Type ApiPoint
   ByVal x As Byte
   ByVal y As Byte
End Type

And I have 3 of them in an array:

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

Then if you were to read the memory from VarPtr(foo(0)) it would be:
[020][025][100][050][075][080]

All elements were the same, so all solutions had to traverse the entire array

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.

[Cakkie]

Originally posted by Clearcode
No - an array is a contiguous block of memory.

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)

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.

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.

[owenrb]

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:

int memcmp( const void *buf1, const void *buf2, size_t count );

What should it be in Visual Basic?

Private Declare Function memcmp Lib "crtdll.dll" (???, ???, ???) as Integer

[Clearcode]

Private Declare Function memcmp Lib "crtdll.dll" (???, ???, ???) as Integer

I'd say:

Private Declare Function memcmp Lib "crtdll.dll" (buffA As Byte, BuffB As Byte, ByVal Length As Long) as Long

And call it thus:

If memcmp(BuffA(0), BuffB(0), UBound(BuffA)) Then
...
End If

[Cakkie]

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?

[Vi2]

Hi!
I meet "CompareStringA" function. May be, it can help you. But what is the strange time they are shown!

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

[JeffB]

That last post is interesting, actually, StrComp() is quicker than browsing all the array. The API seems pretty much the same as StrComp()

JeffB

[Cakkie]

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

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

[JeffB]

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 :

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

It's interesting since it returns how many elements are the same. Anyway, maybe it is quicker than StrComp()

JeffB

[coolbiz]

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