_ArrayDelete speedup [SOLVED]

[hannes08]

Hey guys,

I have a huge array ($a_con) with, let's say 13k entries and around 2000 of them have to be deleted.

Right now I have the IDs of the Values that have to be deleted in a second array ($a_temp).

For $i = $a_temp[0] To 1 Step -1
        If $a_temp[$i] > 0 Then
            _ArrayDelete($a_con, $a_temp[$i])
        EndIf
    Next

I do have to check, whether there are empy records in the second array. (If $a_temp[$i] > 0 Then).

Any Ideas how I can speed this up? Right now it takes around 22 seconds.

[EDIT]

Well sometimes it's good to use the search function in the forum.

For $i = 1 To $a_temp[0]
    $a_con[$a_temp[$i]] = "NULL"
Next
$s_con = _ArrayToString($a_con, "|")
StringReplace($s_con, "|Null", "")
$a_con = StringSplit($s_con, "|")

Decreases with 13k entries from 22 to 0.6 seconds.

Edited March 29, 2011 by Hannes123

[SmOke_N]

That's much faster; and the reason being is you're not "redimming" your array 15k times.

This may be an even faster alternative:

expandcollapse popup

#include <Array.au3>
Local $a_data = StringSplit("1231394013939041", "")

Local $a_exc = __ArrayExclude1D($a_data, "1", 1, True)
_ArrayDisplay($a_exc)

; array to search ( mandatory param; must be an array )
; exclude value ( mandatory param )
; base to start ( if you use normal stringsplit to create the array, it will be 1 ) ( default is zero )
; if you want [0] index zero to contain the total indexes available ( default is no )
; the max bounds you want to search the array ( default is all of the indexes )
; case sensitive ( default is no )
Func __ArrayExclude1D(ByRef $a_arr, $s_excludeval, $i_base = 0, $f_zeroindextotal = False, $i_max = -1, $f_case = False)

    If Not IsArray($a_arr) Then Return SetError(1, 0, 0)

    If Int($i_max) < 1 Then $i_max = UBound($a_arr) - 1
    Local $a_ret[$i_max + 1], $i_add = 0
    If $f_zeroindextotal Then $i_add += 1

    If $f_case Then
        For $i = 0 To $i_max
            If Not ($a_arr[$i] == $s_excludeval) Then
                $a_ret[$i_add] = $a_arr[$i]
                $i_add += 1
            EndIf
        Next
    Else
        For $i = $i_base To $i_max
            If $a_arr[$i] <> $s_excludeval Then
                $a_ret[$i_add] = $a_arr[$i]
                $i_add += 1
            EndIf
        Next
    EndIf

    If $i_add = 0 Or ($i_add = 1 And $f_zeroindextotal) Then
        Return SetError(2, 0, 0)
    EndIf

    ReDim $a_ret[$i_add]
    If $f_zeroindextotal Then $a_ret[0] = $i_add - 1

    Return $a_ret
EndFunc

Edit:

Be fore warned, if you put a max value that's over the actual ubound, you will get a subscript error. I did not do much error/safety checking.

If you don't know what this means, then leave parameter 5 ( $i_max ) at -1.

The example is for "proof of concept" really.

Edited March 29, 2011 by SmOke_N

[enaiman]

Well - nice solutions

Too bad they work only for 1-dimensional arrays - so many times the arrays in need of deleting elements are 2-dimensional.

I had no idea it could be done this way - good to know it

[SmOke_N]

Again, it was just an example on my part.

You could easily add 2 dimensional to it if you so chose.

[Malkey]

[smOke_N ]

I found the mistake you left for people to find and corrected it.

[script Description]

Now we have two functions with different workings that do exactly the same thing.

__ArrayExclude1DRE is slightly faster on big arrays, and

__ArrayExclude1D is slightly faster on small arrays.

expandcollapse popup

#include <Array.au3> ; For _ArrayDisplay() use only.

; ------ Create test string -------
Local $sTest = ""
For $i = 1 To 10000
    $sTest &= Random(0, 9, 1) & Chr(Random(97, 122, 1)) & " "
Next
;or
;$sTest = "1a 2b 31a 1a2 1A 1a 9z4 2b 1a 4d"
; ----> End of Create test string ----

;#cs
Local $stxt1 = StringTrimRight($sTest, 1)
;ConsoleWrite($stxt1 & @CRLF)
Local $a_data = StringSplit($stxt1, " ")
Local $begin = TimerInit()
Local $a_exc = __ArrayExclude1DRE($a_data, "1a", 1, False, -1, True)
ConsoleWrite("Time: " & TimerDiff($begin) & @CRLF)
_ArrayDisplay($a_exc, "__ArrayExclude1DRE")
;#ce
;#cs
Local $stxt2 = StringTrimRight($sTest, 1)
Local $a_data = StringSplit($stxt2, " ")
Local $begin1 = TimerInit()
Local $a_exc = __ArrayExclude1D($a_data, "1a", 1, False, -1, True)
ConsoleWrite("Time2: " & TimerDiff($begin1) & @CRLF)
_ArrayDisplay($a_exc, "__ArrayExclude1D")
;#ce

Func __ArrayExclude1DRE(ByRef $a_arr, $s_excludeval, $i_base = 0, $f_zeroindextotal = False, _
        $i_max = -1, $f_case = False)
    If Not IsArray($a_arr) Then Return SetError(1, 0, 0)
    Local $sCase = "", $sStr = ""
    If $f_case = False Then $sCase = "(?i)" ; Allow case-insensitivity.
    If $i_max < 1 Or $i_max > (UBound($a_arr) - 1) Then $i_max = UBound($a_arr) - 1

    ; Array to String.  The "~" character chosen to prevent partial matching.
    For $i = $i_base To $i_max
        $sStr &= $a_arr[$i] & "~~"
    Next
    $sStr = "~" & StringTrimRight($sStr, 1)

    $sStr = StringRegExpReplace($sStr, $sCase & "(~" & $s_excludeval & "~)", ""); Remove all $s_excludeval
    $sStr = StringRegExpReplace($sStr, "(~)\1", "~") ; Replace all double or more "~"s with single "~"
    $sStr = StringRegExpReplace($sStr, "^[~]*|[~]*$", "") ; Remove leading & trailing "~"
    $a_ret = StringSplit($sStr, "~", (Not $f_zeroindextotal) * 2)
    Return $a_ret
EndFunc   ;==>__ArrayExclude1DRE


; array to search ( mandatory param; must be an array )
; exclude value ( mandatory param )
; base to start ( if you use normal stringsplit to create the array, it will be 1 ) ( default is zero )
; if you want [0] index zero to contain the total indexes available ( default is no )
; the max bounds you want to search the array ( default is all of the indexes )
; case sensitive ( default is no )
Func __ArrayExclude1D(ByRef $a_arr, $s_excludeval, $i_base = 0, $f_zeroindextotal = False, _
        $i_max = -1, $f_case = False)

    If Not IsArray($a_arr) Then Return SetError(1, 0, 0)

    If Int($i_max) < 1 Or $i_max > (UBound($a_arr) - 1) Then $i_max = UBound($a_arr) - 1 ;<--Added to this line.
    Local $a_ret[$i_max + 1], $i_add = 0
    If $f_zeroindextotal Then $i_add += 1

    If $f_case Then
        ;For $i = 0 To $i_max  ; <-------------- This line corrected
        For $i = $i_base To $i_max
            If Not ($a_arr[$i] == $s_excludeval) Then
                $a_ret[$i_add] = $a_arr[$i]
                $i_add += 1
            EndIf
        Next
    Else
        For $i = $i_base To $i_max
            If $a_arr[$i] <> $s_excludeval Then
                $a_ret[$i_add] = $a_arr[$i]
                $i_add += 1
            EndIf
        Next
    EndIf

    If $i_add = 0 Or ($i_add = 1 And $f_zeroindextotal) Then
        Return SetError(2, 0, 0)
    EndIf

    ReDim $a_ret[$i_add]
    If $f_zeroindextotal Then $a_ret[0] = $i_add - 1

    Return $a_ret
EndFunc   ;==>__ArrayExclude1D

[_ArrayExclude2D]

For a 2d version, you need two "true or false" parameters, one for rows, and one for columns, A "True" would re-dimension the 2d array if all the elements of an entire row or an entire column had been excluded, or a "false" would leave the row or column blank.

If all the elements of an entire row or column were not excluded, just leave those excluded element blank? Or, make it more like _ArrayFindReplace2D(), by having a "replacement string" parameter? The default "replacement string" parameter could be "", blank.

[hannes08]

Wow,

interesting to see what you guys are doing here. I did a little change to the snippet of SmOke_N because what I wanted to do is to delete specific IDs from an array. There is no need to check for the contents:

; array to search ( mandatory param; must be an array )
; exclude value ( mandatory param )
; base to start ( if you use normal stringsplit to create the array, it will be 1 ) ( default is zero )
; if you want [0] index zero to contain the total indexes available ( default is no )
; the max bounds you want to search the array ( default is all of the indexes )
Func __ArrayExcludeID(ByRef $a_arr, $s_excludeval, $i_base = 0, $f_zeroindextotal = False, $i_max = -1)

    If Not IsArray($a_arr) Then Return SetError(1, 0, 0)

    If Int($i_max) < 1 Then $i_max = UBound($a_arr) - 1
    Local $a_ret[$i_max + 1], $i_add = 0
    If $f_zeroindextotal Then $i_add += 1

    For $i = $i_base To $i_max
        If $i <> $s_excludeval Then
            $a_ret[$i_add] = $a_arr[$i]
            $i_add += 1
        EndIf
    Next

    If $i_add = 0 Or ($i_add = 1 And $f_zeroindextotal) Then
        Return SetError(2, 0, 0)
    EndIf

    ReDim $a_ret[$i_add]
    If $f_zeroindextotal Then $a_ret[0] = $i_add - 1

    Return $a_ret
EndFunc

I tested the same:

#include <Array.au3>
Dim $a_data[15001]
Dim $a_excl[2001]

$t = TimerInit()
For $i = 0 To 15000
    $a_data[$i] = $i
Next
ConsoleWrite(TimerDiff($t) & @CRLF)
$t = TimerInit()
For $i = 1 to 2000
    $a_data = __ArrayExcludeID($a_data, $i * 10, 1, True)
Next
ConsoleWrite(TimerDiff($t) & @CRLF)

Result:

116830ms

Now what I first wrote:

Dim $a_data[15001]
Dim $a_excl[2001]
$a_excl[0] = 2000

$t = TimerInit()
For $i = 0 To 15000
    $a_data[$i] = $i
Next
ConsoleWrite(TimerDiff($t) & @CRLF)
$t = TimerInit()
For $i = 1 to $a_excl[0]
    $a_data[$a_excl[$i]] = "NULL"
Next
$s_data = _ArrayToString($a_data, "|")
StringReplace($s_data, "|Null", "")
StringReplace($s_data, "Null", "")
$a_data = StringSplit($s_data, "|")
ConsoleWrite(TimerDiff($t) & @CRLF)

Result: 64ms

Anyway I appreciate the efforts and the enthusiasm you gys have and give to this great forum!

[SmOke_N]

That test is kind of rediculous.

In your 64ms one, you're removing 1 item.

In the one you modded of min, you're removing 2000!

2000 x's 64 ms is what?

Here is a better test of my implementation if you're trying to do the same thing:

expandcollapse popup

Dim $a_data[15001]
Dim $a_excl[2001]
$a_excl[0] = 2000

$t = TimerInit()
For $i = 0 To 15000
    $a_data[$i] = $i
Next
ConsoleWrite(TimerDiff($t) & @CRLF)
$t = TimerInit()
For $i = 1 to $a_excl[0]
    $a_data[$a_excl[$i]] = "NULL"
Next
$a_data = __ArrayExclude1D($a_data, "Null", 1, True)
ConsoleWrite(TimerDiff($t) & @CRLF)

; array to search ( mandatory param; must be an array )
; exclude value ( mandatory param )
; base to start ( if you use normal stringsplit to create the array, it will be 1 ) ( default is zero )
; if you want [0] index zero to contain the total indexes available ( default is no )
; the max bounds you want to search the array ( default is all of the indexes )
; case sensitive ( default is no )
Func __ArrayExclude1D(ByRef $a_arr, $s_excludeval, $i_base = 0, $f_zeroindextotal = False, $i_max = -1, $f_case = False)

    If Not IsArray($a_arr) Then Return SetError(1, 0, 0)

    If Int($i_max) < 1 Then $i_max = UBound($a_arr) - 1
    Local $a_ret[$i_max + 1], $i_add = 0
    If $f_zeroindextotal Then $i_add += 1

    If $f_case Then
        For $i = 0 To $i_max
            If Not ($a_arr[$i] == $s_excludeval) Then
                $a_ret[$i_add] = $a_arr[$i]
                $i_add += 1
            EndIf
        Next
    Else
        For $i = $i_base To $i_max
            If $a_arr[$i] <> $s_excludeval Then
                $a_ret[$i_add] = $a_arr[$i]
                $i_add += 1
            EndIf
        Next
    EndIf

    If $i_add = 0 Or ($i_add = 1 And $f_zeroindextotal) Then
        Return SetError(2, 0, 0)
    EndIf

    ReDim $a_ret[$i_add]
    If $f_zeroindextotal Then $a_ret[0] = $i_add - 1

    Return $a_ret
EndFunc

That should be the same thing you're trying to accomplish with yours.

And that is around 7 to 15 ms faster than yours when I tested.

[hannes08]

Hi SmOke_N,

well first of all, you're right if you say that there's an error in my script, but If you like you can try this:

$t = TimerInit()
;Fill data array with content
For $i = 0 To 15000
    $a_data[$i] = "Lorem ipsum dolor sit amet, consectetuer adipiscing elit. Aenean commodo ligula eget dolor. Aenean massa. Cum sociis natoque penatibus et magnis dis parturient montes, nascetur ridiculus mus." & $i
Next
ConsoleWrite(TimerDiff($t) & @CRLF)

$t = TimerInit()
;Fill exclution array with IDs to delete
For $i = 1 to $a_excl[0]
    $a_data[$a_excl[$i]] = "NULL"
Next
ConsoleWrite(TimerDiff($t) & @CRLF)

$t = TimerInit()
$s_data = _ArrayToString($a_data, "|")
$s_data = StringReplace($s_data, "|NULL", "")
$s_data = StringReplace($s_data, "NULL", "")
$a_data = StringSplit($s_data, "|")
ConsoleWrite(TimerDiff($t) & @CRLF)

The difference is, that I do have a list of items (IDs) I can delete in one step (here: StringReplace) instead of having to call the same function 2000 times. So you're right when you have to delete lines one by one.

So it is not ridiculous if you see it from that point of view.

Will you believe me I I tell you I still need far less than 120000ms (here: about 500ms)?

Edited March 31, 2011 by Hannes123