detecting a difference between two arrays

[nullschritt]

And even if so, if one insert is done at index 0 in array2, you will get UBound($array) differences whereas only the index changes

 

Not sure what you mean. The purpose of the function is to return the position of the change. By knowing the position of the change I can ten pull it from the array and place it in the database(If you insert a value to position 0 in array 2, it will stop in the first loop and return position 0, the same is true for any point in the either array.). Though your comment made me notice a bug in my code that I revised. [Could not differentiate between no change and change @ position 0]

Edited February 7, 2014 by nullschritt

[Gianni]

this way is a little faster:

Func _arraygetdifference2($array1, $array2)
    For $i = 0 To UBound($array1) - 1
        If $array1[$i] <> $array2[$i] Then Return $i
    Next
    Return "Null"
EndFunc   ;==>_arraygetdifference2

here a test to compare speed:

Local $a[500000]
Local $b[500000]

For $i = 0 To 499999 ; fill arrays
    $a[$i] = $i
    $b[$i] = $i
Next

$a[499999] = 9 ; last element is not equal

$time = TimerInit()
ConsoleWrite("==> " & _arraygetdifference($a, $b) & @CRLF) ; use func from post #8
ConsoleWrite("Time spent 1: " & TimerDiff($time) & @CRLF)

$time = TimerInit()
ConsoleWrite("==> " & _arraygetdifference2($a, $b) & @CRLF); use my variation
ConsoleWrite("Time spent 2: " & TimerDiff($time) & @CRLF)

Func _arraygetdifference($array1, $array2)
    Local $pos = 'Null'
    For $i = 0 To UBound($array1) - 1
        If $array1[$i] <> $array2[$i] Then
            $pos = $i
            ExitLoop
        EndIf
    Next
    Return $pos
EndFunc   ;==>_arraygetdifference

Func _arraygetdifference2($array1, $array2)
    For $i = 0 To UBound($array1) - 1
        If $array1[$i] <> $array2[$i] Then Return $i
    Next
    Return "Null"
EndFunc   ;==>_arraygetdifference2

[nullschritt]

 

this way is a little faster:

Func _arraygetdifference2($array1, $array2)
    For $i = 0 To UBound($array1) - 1
        If $array1[$i] <> $array2[$i] Then Return $i
    Next
    Return "Null"
EndFunc   ;==>_arraygetdifference2

here a test to compare speed:

Local $a[500000]
Local $b[500000]

For $i = 0 To 499999 ; fill arrays
    $a[$i] = $i
    $b[$i] = $i
Next

$a[499999] = 9 ; last element is not equal

$time = TimerInit()
ConsoleWrite("==> " & _arraygetdifference($a, $b) & @CRLF) ; use func from post #8
ConsoleWrite("Time spent 1: " & TimerDiff($time) & @CRLF)

$time = TimerInit()
ConsoleWrite("==> " & _arraygetdifference2($a, $b) & @CRLF); use my variation
ConsoleWrite("Time spent 2: " & TimerDiff($time) & @CRLF)

Func _arraygetdifference($array1, $array2)
    Local $pos = 'Null'
    For $i = 0 To UBound($array1) - 1
        If $array1[$i] <> $array2[$i] Then
            $pos = $i
            ExitLoop
        EndIf
    Next
    Return $pos
EndFunc   ;==>_arraygetdifference

Func _arraygetdifference2($array1, $array2)
    For $i = 0 To UBound($array1) - 1
        If $array1[$i] <> $array2[$i] Then Return $i
    Next
    Return "Null"
EndFunc   ;==>_arraygetdifference2

Thanks! Nice streamlining.

[Gianni]

Maybe an improvement in the search of differences could be that of splitting the search in two directions within the same loop,
one direction from top to the center and the other direction from bottom to center.
in this way, if differences are located randomly along the array, in the long term, the time to find the difference should reduce to about half.
Of course this works only if is not important to know if the found difference is the first one in the array or the last one.

this should do:

Func _arraygetdifference2($array1, $array2)
    Local $j = UBound($array1)
    For $i = 0 To Int(UBound($array1) - 1)/2
        If $array1[$i] <> $array2[$i] Then Return $i
        $j -=1
        If $array1[$j] <> $array2[$j] Then Return $j
    Next
    Return "Null"
EndFunc   ;==>_arraygetdifference2

[JohnOne]

You would need to add bounds checking withing each direction for each iteration.

[Gianni]

the search is already within the bounds of the array

[jdelaney]

If speed is critical, don't use 1 line if statements, they go slower than 3 line if statements.

$iTime = TimerInit()
For $i = 0 To 10000000
    If True Then $b = 1
Next
ConsoleWrite(TimerDiff($iTime) & @CRLF)

$iTime = TimerInit()
For $i = 0 To 10000000
    If True Then
        $b = 1
    EndIf
Next
ConsoleWrite(TimerDiff($iTime) & @CRLF)

Output:

6195.61682860482
3975.4707037034

Edited February 9, 2014 by jdelaney

[nullschritt]

 

Maybe an improvement in the search of differences could be that of splitting the search in two directions within the same loop,

one direction from top to the center and the other direction from bottom to center.

in this way, if differences are located randomly along the array, in the long term, the time to find the difference should reduce to about half.

Of course this works only if is not important to know if the found difference is the first one in the array or the last one.

this should do:

Func _arraygetdifference2($array1, $array2)
    Local $j = UBound($array1)
    For $i = 0 To Int(UBound($array1) - 1)/2
        If $array1[$i] <> $array2[$i] Then Return $i
        $j -=1
        If $array1[$j] <> $array2[$j] Then Return $j
    Next
    Return "Null"
EndFunc   ;==>_arraygetdifference2

Seems like a good idea but maybe not always the most efficient. Aka if the string I'm looking for is 1 value past the midpoint, the script will take 2x as long to locate it.

[jaberwacky]

Minor optimizations on PincoPanco's function is marginally faster:

Func _arraygetdifference4(Const $array1, Const $array2)
  Local Const $up_bound = UBound($array1)
  
  Local Const $up_to = Int(($up_bound - 1) / 2)  
  
  Local $j = $up_bound
  
  For $i = 0 To $up_to Step 1
    If $array1[$i] <> $array2[$i] Then 
      Return $i
    EndIf
    
    $j -= 1
    
    If $array1[$j] <> $array2[$j] Then 
      Return $j
    EndIf
  Next
  
  Return "Null"
EndFunc

Test:

expandcollapse popup

Local $a[500000]
Local $b[500000]

For $i = 0 To 499999 ; fill arrays
  $a[$i] = $i
  $b[$i] = $i
Next

$a[499999] = 9 ; last element is not equal

Global $elapsed = 0

$time = TimerInit()
For $i = 1 To 5
  _arraygetdifference($a, $b)
  $elapsed += TimerDiff($time)
Next
ConsoleWrite("Average 1 " & $elapsed / 5 & @CRLF)
$elapsed = 0

$time = TimerInit()
For $i = 1 To 5
  _arraygetdifference2($a, $b)
  $elapsed += TimerDiff($time)
Next
ConsoleWrite("Average 2 " & $elapsed / 5 & @CRLF)
$elapsed = 0

$time = TimerInit()
For $i = 1 To 5
  _arraygetdifference3($a, $b)
  $elapsed += TimerDiff($time)
Next
ConsoleWrite("Average 3 " & $elapsed / 5 & @CRLF)
$elapsed = 0

$time = TimerInit()
For $i = 1 To 5
  _arraygetdifference4($a, $b)
  $elapsed += TimerDiff($time)
Next
ConsoleWrite("Average 4 " & $elapsed / 5 & @CRLF)

Func _arraygetdifference($array1, $array2)
  Local $pos = 'Null'
  For $i = 0 To UBound($array1) - 1
    If $array1[$i] <> $array2[$i] Then
      $pos = $i
      ExitLoop
    EndIf
  Next
  Return $pos
EndFunc

Func _arraygetdifference2($array1, $array2)
  For $i = 0 To UBound($array1) - 1
    If $array1[$i] <> $array2[$i] Then Return $i
  Next
  Return "Null"
EndFunc

Func _arraygetdifference3($array1, $array2)
  Local $j = UBound($array1)
  For $i = 0 To Int(UBound($array1) - 1)/2
    If $array1[$i] <> $array2[$i] Then Return $i
    $j -=1
    If $array1[$j] <> $array2[$j] Then Return $j
  Next
  Return "Null"
EndFunc

Func _arraygetdifference4(Const $array1, Const $array2)
  Local Const $up_bound = UBound($array1)
  
  Local Const $up_to = Int(($up_bound - 1) / 2)  
  
  Local $j = $up_bound
  
  For $i = 0 To $up_to Step 1
    If $array1[$i] <> $array2[$i] Then 
      Return $i
    EndIf
    
    $j -= 1
    
    If $array1[$j] <> $array2[$j] Then 
      Return $j
    EndIf
  Next
  
  Return "Null"
EndFunc

[guinness]

Has anyone suggested using Scripting.Dictionary to compare?

[Gianni]

Seems like a good idea but maybe not always the most efficient. Aka if the string I'm looking for is 1 value past the midpoint, the script will take 2x as long to locate it.

 

You are right, I was wrong, in the long term there is not advantage.

If speed is critical, don't use 1 line if statements, they go slower than 3 line if statements.

$iTime = TimerInit()
For $i = 0 To 10000000
    If True Then $b = 1
Next
ConsoleWrite(TimerDiff($iTime) & @CRLF)

$iTime = TimerInit()
For $i = 0 To 10000000
    If True Then
        $b = 1
    EndIf
Next
ConsoleWrite(TimerDiff($iTime) & @CRLF)

Output:

6195.61682860482

3975.4707037034

 

this seems interesting,

but having tried jaberwacky's test in post >#29, the func that use this suggestions takes longer time than the one that uses "1 line if statement"

to make the test I changed

$a[499999] = 9  --> to $a[250000] = 9

so the difference is in the middle of the array.

this is the result:

Average 1 596.088079322401

Average 2 485.371194972564

Average 3 1106.30611673769 <--- "1 line if statement"

Average 4 1280.84799019452 <--- "3 line if statement"

[Gianni]

Has anyone suggested using Scripting.Dictionary to compare?

 

how can this achieved?

[guinness]

how can this achieved?

Read the first array into a Scripting.Dictionary object and then use .Exists to check if it's already present when iterating through the second array.

[JohnOne]

If arrays are not a requirement, I'd not be surprised if there was a swanky way to do it using dllstructs.

[guinness]

how can this achieved?

An idea ...

expandcollapse popup

Example()

Func Example()
    Local $aArray_1 = __ArrayFill(1, False) ; Create a 1d random zeroth element array.
    Local $aArray_2 = __ArrayFill(1, False) ; Create a 1d random zeroth element array.

    Local $hAssocArray = 0
    _AssociativeArray_Startup($hAssocArray)

    #Region Check $aArray_1
    For $i = 0 To UBound($aArray_1) - 1
        $hAssocArray.Item($aArray_1[$i]) = 0 ; Add to the associative array.
    Next

    For $i = 0 To UBound($aArray_2) - 1
        If Not $hAssocArray.Exists($aArray_2[$i]) Then ; Check if the item exists.
            ConsoleWrite($aArray_2[$i] & ' >> doesn''t exist in $aArray_2' & @CRLF)
        EndIf
    Next
    #EndRegion Check $aArray_1

    $hAssocArray = 0 ; Destroy the object.
    _AssociativeArray_Startup($hAssocArray)

    #Region Check $aArray_2
    For $i = 0 To UBound($aArray_2) - 1
        $hAssocArray.Item($aArray_2[$i]) = 0 ; Add to the associative array.
    Next

    For $i = 0 To UBound($aArray_1) - 1
        If Not $hAssocArray.Exists($aArray_1[$i]) Then ; Check if the item exists.
            ConsoleWrite($aArray_1[$i] & ' >> doesn''t exist in $aArray_1' & @CRLF)
        EndIf
    Next
    #EndRegion Check $aArray_2

EndFunc   ;==>Example

Func _AssociativeArray_Startup(ByRef $aArray, $fIsCaseSensitive = False) ; Idea from MilesAhead.
    Local $fReturn = False
    $aArray = ObjCreate('Scripting.Dictionary')
    ObjEvent('AutoIt.Error', '__AssociativeArray_Error')
    If IsObj($aArray) Then
        $aArray.CompareMode = Int(Not $fIsCaseSensitive)
        $fReturn = True
    EndIf
    Return $fReturn
EndFunc   ;==>_AssociativeArray_Startup

Func __ArrayFill($iType, $fIsIndexCount = Default) ; By guinness.
    Local $iRows = Random(2, 1000, 1)
    If $fIsIndexCount = Default Then
        $fIsIndexCount = True
    EndIf
    Switch $iType
        Case 2
            Local $iCols = Random(2, 25, 1)
            Local $aReturn[$iRows][$iCols]
            For $i = 0 To $iRows - 1
                For $j = 0 To $iCols - 1
                    $aReturn[$i][$j] = 'Row ' & $i & ': Col ' & $j
                Next
            Next
            If $fIsIndexCount Then
                For $i = 0 To $iCols - 1
                    $aReturn[0][$i] = ''
                Next
                $aReturn[0][0] = $iRows - 1
            EndIf
        Case Else
            Local $aReturn[$iRows]
            For $i = 0 To $iRows - 1
                $aReturn[$i] = 'Row ' & $i
            Next
            If $fIsIndexCount Then
                $aReturn[0] = $iRows - 1
            EndIf
    EndSwitch
    Return $aReturn
EndFunc   ;==>__ArrayFill

[Gianni]

 

An idea ...

 

nice! learned something new

can be useful to use his ready made methods.

but this script does not find if the 2 arrays are identical

also, looking at this page I am not able to find a method or an easy way to compare if 2 arrays are identical and if not, where is the (first) difference...

[JohnOne]

Maybe setting to compare mode might kill two birds with one stone.

Will fail if already exists (not changed) and add it if it does not exist (changed - note the key)

[BlackDawn187]

What if you somehow integrated the below code, It would help compare differences in a simpler manner without looping through all the arrays. Whether or not it's quicker I'll leave that up to you guys to figure out. Along with how to determine the array position of change.

While 1
$CombinedNewData = _ArrayToString($Array, " ", 1, $Array[0])
$CombinedOldData = _ArrayToString($Array2, " ", 1, $Array2[0])  

If $CombinedNewData <> $CombinedOldData Then
   MsgBox(0, "", "Something Changed")
   ;Call your function to determine position?
ElseIf $CombinedNewData = $CombinedOldData Then
   MsgBox(0. "", "Nothing Changed")
   ;Continue While Loop
EndIf

Sleep("60000")

WEnd

Edited February 9, 2014 by BlackDawn187

[JohnOne]

ArrayToString loops through the array, StringCompare will effectively loop through it again.

[BlackDawn187]

StringCompare("")

StringCompare(^ ERROR