Fast search of a difference of two arrays

[hunt]

I searched at a forum "array diff", but have not found a fast way of a finding of a difference of two arrays. Whether there is any function similar on array_diff (in php)?

[picaxe]

Try this by BugFix

[hunt]

picaxe

I tried function by Bugfix, but it long finds a difference (~500ms, array1=1200 elements, array2=500 elements).

I saw the program in which the difference of two these arrays was calculated instantly (~ <50ms)

Edited March 11, 2009 by hunt

[PsaltyDS]

picaxe

I tried function by Bugfix, but it long finds a difference (~500ms, array1=1200 elements, array2=500 elements).

I saw the program in which the difference of two these arrays was calculated instantly (~ <50ms)

Well, the time can be reduced. This averages about 270ms on my box:

expandcollapse popup

#include <Array.au3>

Global $MyArray1[1200]
For $n = 0 To UBound($MyArray1) - 1
    $MyArray1[$n] = $n
Next

Global $MyArray2[500]
For $n = 0 To UBound($MyArray2) - 1
    $MyArray2[$n] = ($n * 2) + 1; Odd numbers only
Next

Global $iTimer = TimerInit()
$avResult = _ArrayDiff($MyArray1, $MyArray2)
$iTimer = Round(TimerDiff($iTimer), 2) & "ms"
_ArrayDisplay($avResult, "Time = " & $iTimer)

; -------------------------------------------------
; Function:  _ArrayDiff
; Purpose:  Returns an array of elements from $avArray1 that do not occur in $avArray2
; Syntax:   _ArrayDiff(ByRef $avArray1, ByRef $avArray2 [, $f_CaseSense = 0])
;   Where:  $avArray1 = ByRef source array
;           $avArray2 = ByRef array to search for $avArray1 elements
;           $f_CaseSense (optional) = Case sensitivity as passed to StringInStr()
;               0 = not case sensitive, using the user's locale (default)
;               1 = case sensitive
;               2 = not case sensitive, using a basic/faster comparison
; Returns:  On success returns an array with [0] = count containing any elements
;               from $avArray1 that do not occur in $avArray2
;               If all elements in $avArray1 occur in $avArray2 then [0] = 0
;           On Failure returns 1-element array [0] = 0 and sets @error.
; Author:   PsaltyDS on www.autoitscript.com/forum
; Notes:    Similar to PHP array_diff function
; --------------------------------------------------
Func _ArrayDiff(ByRef $avArray1, ByRef $avArray2, $f_CaseSense = 0)
    Local $avRET[1] = [0], $sRET = ""

    If (IsArray($avArray1) = 0) Or (UBound($avArray1, 0) <> 1) Then Return SetError(1, 1, $avRET)
    If (IsArray($avArray2) = 0) Or (UBound($avArray2, 0) <> 1) Then Return SetError(1, 2, $avRET)

    Local $sArray2 = Chr(1) & _ArrayToString($avArray2, Chr(1)) & Chr(1)

    For $n = 0 To UBound($avArray1) - 1
        If Not StringInStr($sArray2, Chr(1) & $avArray1[$n] & Chr(1)) Then $sRET &= $avArray1[$n] & Chr(1)
    Next

    If StringLen($sRET) Then
        $sRET = StringTrimRight($sRET, 1)
        $avRET = StringSplit($sRET, Chr(1))
    EndIf

    Return $avRET
EndFunc  ;==>_ArrayDiff

If blazing speed is your primary need, AutoIt is not for you.

Since there hasn't been enough interest to get a PHP-like _ArrayDiff() in the Array.au3 UDF, you can bet there is no interest in putting an optimized native C++ function in the interpreter.

[hunt]

PsaltyDS

Thanks for example. I tried it but time ~850ms on my computer (

[PsaltyDS]

PsaltyDS

Thanks for example. I tried it but time ~850ms on my computer (

That's kind of sad. Low-spec computer running a VM...?

If you know how to do this in PHP, why are you doing it in AutoIt? AutoIt does unique things, especially with easily accessing third-party GUI controls, and the native functions are pretty fast, but if you need a custom function to run at blazing speeds you are in the wrong place.

One option is to use Run(), RunWait(), a WScript object, etc., to execute an external function code in whatever you have access to. There was an array search topic once, I believe, where somebody made it appear really fast in AutoIt by passing the data to an external javascript instance.

[hunt]

PsaltyDS

I do programm, it is not necessary php.

But I nevertheless have achieved a fast finding of a difference of 2 arrays. Time of calculation was 43-45ms

This is a example. Calculation time depends on that how much 2 arrays are sorted.

This code works only when the second array is a subset of the first array.

Elements of arrays should begin with [1]

expandcollapse popup

Func _ArrayDiff($array1,$array2)
    $step=1
    $j=1
    $begin=TimerInit()
    $ubound1=$array1[0]+1
    For $i=1 to $array2[0]
        $exists=0
        While $j<$ubound1
            If $array2[$i]=$array1[$j] Then
                $array1[$j]=""              
                $j+=1
                $step=$j
                $exists=1
                ContinueLoop(2)
            Endif
            $j+=1
        Wend
        If $exists=0 Then
            $j=$step-2
            While $j>0
                If $array2[$i]=$array1[$j] Then
                    $array1[$j]=""                  
                    $j+=1
                    $step=$j
                    ExitLoop
                Endif
                $j-=1
            Wend
        Endif
    Next

    $count_temp=1
    Dim $Temp[$ubound1] 
    For $i=1 to $array1[0]
        If $array1[$i]<>"" Then 
            $Temp[$count_temp]=$array1[$i]
            $count_temp+=1
        Endif
    Next        
    $Temp[0]=$count_temp-1
    Redim $Temp[$count_temp]
;MsgBox(0,"",TimerDiff($begin))
    return $Temp
EndFunc

[masvil]

Well, the time can be reduced. This averages about 270ms on my box:

Works great, thank you :-)