_ReDim - The most efficient way so far when you have to resize an existing array.

[guinness]

For those that have an understanding of 1D/2D Arrays or wish to learn, then this post is a good way to start. This isn't a UDF, more of 'what I've discovered' from reading many Forum posts (especially from Melba23, KaFu) about how ReDim should only be used when required and in an efficient way.

For those who tend to create their own Arrays it's inevitable that sometimes ReDim will have to be used. Sometimes knowing the final size of the Array isn't known, especially if using FileFindFirstFile/FileFindNextFile to record the file name(s). For most we use ReDim $aArray[$iTotal_Rows + 1] to increase the size of the Array (by 1 Row) but when it comes to Arrays that might have 1000+ items this starts to slow the Script down. So a little trick Melba23/KaFu pointed out, is to only ReDim when really necessary & then if so multiply the size by 1.5 and round to the next integer. Thus reducing the need for 'ReDimming' every time.

 

17 * 1.5 = 25.5
Ceiling(17 * 1.5) = 26

For Example if we were to create an Array with 1000 items using the traditional way, it would require the Array to be ReDimmed (you guessed it) 1000 times, but using the trick (when required and multiply by 1.5) this is reduced to only 16 times! In the tests I conducted this was the difference of 388ms VS 20ms, what a huge speed increase and only on 1000 items.

The reason why I haven't made this a UDF is because users declare variables differently. How I do it is I store the row size in index 0 and if using columns I store the size in index 0 & column 1. Others will use Ubound to find the size as they don't store the Array size in the Array or in a variable e.g. For $i = 0 To Ubound($aArray, 1) - 1. Others will store the row size in index 0, but won't keep a reference of how many columns the Array has, especially when they just 'hard code' it in Functions e.g. $aArray[$i][5] += 1.

How I declare Arrays:

#include <Array.au3>

Local $a1D[6] = [5, 1, 2, 3, 4, 5] ; Array count in the 0th element e.g. 5.
Local $a2D[6][3] = [[5, 3], [1, 1], [2, 2], [3, 3], [4, 4], [5, 5]] ; Array count in the 0th element, 0th column e.g. 5 and the column count in the 0th element, 1st column e.g. 3.

_ArrayDisplay($a1D, '1D Array')
_ArrayDisplay($a2D, '2D Array')

Therefore have a look at the Examples that are below and read the comments to understand a little further. Comments, suggestions, then please post below. Thanks.

Functions.

Func _ReDim1D(ByRef $aArray, ByRef $iDimension) ; Where Index [0] is the Row count.
    If ($aArray[0] + 1) >= $iDimension Then
        $iDimension = Ceiling(($aArray[0] + 1) * 1.5)
        ReDim $aArray[$iDimension]
        Return 1
    EndIf
EndFunc   ;==>_ReDim1D

Func _ReDim2D(ByRef $aArray, ByRef $iDimension) ; Where Index [0, 0] is the Row count and Row [0, 1] is the Column count.
    If ($aArray[0][0] + 1) >= $iDimension Then
        $iDimension = Ceiling(($aArray[0][0] + 1) * 1.5)
        ReDim $aArray[$iDimension][$aArray[0][1]]
        Return 1
    EndIf
EndFunc   ;==>_ReDim2D

Func _ReDim1D_Ubound(ByRef $aArray, ByRef $iDimension, ByRef $iCount) ; Using Ubound($aArray, 1) to find the Row size.
    $iCount += 1
    If ($iCount + 1) >= $iDimension Then
        $iDimension = Ceiling((UBound($aArray, 1) + 1) * 1.5)
        ReDim $aArray[$iDimension]
        Return 1
    EndIf
EndFunc   ;==>_ReDim1D_Ubound

Func _ReDim2D_Ubound(ByRef $aArray, ByRef $iDimension, ByRef $iCount) ; Using Ubound($aArray, 1) to find the Row size and Ubound($aArray, 2) for the Column size.
    $iCount += 1
    If ($iCount + 1) >= $iDimension Then
        $iDimension = Ceiling((UBound($aArray, 1) + 1) * 1.5)
        ReDim $aArray[$iDimension][UBound($aArray, 2)]
        Return 1
    EndIf
EndFunc   ;==>_ReDim2D_Ubound

Example use of Functions:

expandcollapse popup

#include <Array.au3>
#include <Constants.au3>

; Change the value of the $ARRAY_SIZE constant to determine the array size.
Global Const $ARRAY_SIZE = 5000

_1D_Slow() ; See how Slow this is by doing it the traditional way of increasing by 1.
_1D_1() ; Only ReDim when required and if so mutliply the count by 1.5 and round to the next integer.
_1D_2() ; Only ReDim when required and if so mutliply the count by 1.5 and round to the next integer.
_2D_1() ; Only ReDim when required and if so mutliply the count by 1.5 and round to the next integer, this also uses Ubound() to find the size of the Array.
_2D_2() ; Only ReDim when required and if so mutliply the count by 1.5 and round to the next integer, this also uses Ubound() to find the size of the Array.

Func _1D_Slow()
    Local $aArray[1] = [0], $hTimer = 0, $iCount = 0, $iDimension = 0

    $hTimer = TimerInit() ; Start the timer.
    For $i = 1 To $ARRAY_SIZE
        ReDim $aArray[($aArray[0] + 1) + 1] ; ReDim the array by adding 1 to the total count and then increasing by 1 for a new row.
        $iCount += 1 ; If array was ReDimmed then add to the ReDim count for output at the end.
        $aArray[0] += 1 ; Increase Index [0] by 1.
        $aArray[$i] = 'Row ' & $i & ': Col 0' ; Add random data.
        If Mod($i, 1000) = 0 Then
            ConsoleWrite('It''s still working! Now we''re at about ' & $i & ' elements in the array.' & @CRLF)
        EndIf
    Next
    $hTimer = Round(TimerDiff($hTimer)) ; End the timer and find the difference from start to finish.

    ReDim $aArray[$aArray[0] + 1] ; Remove the empty Rows, by ReDimming the total count plus the row for holding the count.

    ; _ArrayDisplay($aArray)
    MsgBox($MB_SYSTEMMODAL, 'How many times? - _1D_Slow()', 'The amount of times a ' & $ARRAY_SIZE & ' element array was ''ReDimmed'' was ' & $iCount & ' times.' & @CRLF & _
            'It only took ' & $hTimer & ' milliseconds to complete.')
EndFunc   ;==>_1D_Slow

Func _1D_1()
    Local $aArray[1] = [0], $hTimer = 0, $iCount = 0, $iDimension = 0

    $hTimer = TimerInit() ; Start the timer.
    For $i = 1 To $ARRAY_SIZE
        If _ReDim1D($aArray, $iDimension) Then ; Returns 1 if ReDimmed OR 0 if it wasn't. This uses ByRef, so just pass the array and a previously delcared variable for monbitoring the dimension.
            $iCount += 1 ; If array was ReDimmed then add to the ReDim count for output at the end.
        EndIf
        $aArray[0] += 1 ; Increase Index [0] by 1.
        $aArray[$i] = 'Row ' & $i & ': Col 0' ; Add random data.
    Next
    $hTimer = Round(TimerDiff($hTimer)) ; End the timer and find the difference from start to finish.

    ReDim $aArray[$aArray[0] + 1] ; Remove the empty Rows, by ReDimming the total count plus the row for holding the count.

    ; _ArrayDisplay($aArray)
    MsgBox($MB_SYSTEMMODAL, 'How many times? - _1D_1()', 'The amount of times a ' & $ARRAY_SIZE & ' element array was ''ReDimmed'' was ' & $iCount & ' times.' & @CRLF & _
            'It only took ' & $hTimer & ' milliseconds to complete.')
EndFunc   ;==>_1D_1

Func _1D_2()
    Local $aArray[1] = [0], $hTimer = 0, $iCount = 0, $iDimension, $iIndexTotal = 0

    $hTimer = TimerInit() ; Start the timer.
    For $i = 1 To $ARRAY_SIZE
        If _ReDim1D_Ubound($aArray, $iDimension, $iIndexTotal) Then ; Returns 1 if ReDimmed OR 0 if it wasn't. This uses ByRef, so just pass the array and a previously delcared variable for monbitoring the dimension and a second variable for monitoring the total count.
            $iCount += 1 ; If array was ReDimmed then add to the ReDim count for output at the end.
        EndIf
        $aArray[0] += 1 ; Increase Index [0] by 1.
        $aArray[$i] = 'Row ' & $i & ': Col 0' ; Add random data.
    Next
    $hTimer = Round(TimerDiff($hTimer)) ; End the timer and find the difference from start to finish.

    ReDim $aArray[$aArray[0] + 1] ; Remove the empty Rows, by ReDimming the total count plus the row for holding the count.

    ; _ArrayDisplay($aArray)
    MsgBox($MB_SYSTEMMODAL, 'How many times? - _1D_2()', 'The amount of times a ' & $ARRAY_SIZE & ' element array was ''ReDimmed'' was ' & $iCount & ' times.' & @CRLF & _
            'It only took ' & $hTimer & ' milliseconds to complete.')
EndFunc   ;==>_1D_2

Func _2D_1()
    Local $aArray[1][2] = [[0, 2]], $hTimer = 0, $iCount = 0, $iDimension = 0

    $hTimer = TimerInit() ; Start the timer.
    For $i = 1 To $ARRAY_SIZE
        If _ReDim2D($aArray, $iDimension) Then ; Returns 1 if ReDimmed OR 0 if it wasn't. This uses ByRef, so just pass the array and a previously delcared variable for monbitoring the dimension.
            $iCount += 1 ; If array was ReDimmed then add to the ReDim count for output at the end.
        EndIf
        $aArray[0][0] += 1 ; Increase Index [0, 0] by 1.
        $aArray[$i][0] = 'Row ' & $i & ': Col 0' ; Add random data.
        $aArray[$i][1] = 'Row ' & $i & ': Col 1' ; Add random data.
    Next
    $hTimer = Round(TimerDiff($hTimer)) ; End the timer and find the difference from start to finish.

    ReDim $aArray[$aArray[0][0] + 1][$aArray[0][1]] ; Remove the empty Rows, by ReDimming the total count plus the row for holding the count and include the number of colums too.

    ; _ArrayDisplay($aArray)
    MsgBox($MB_SYSTEMMODAL, 'How many times? - _2D_1()', 'The amount of times a ' & $ARRAY_SIZE & ' element array was ''ReDimmed'' was ' & $iCount & ' times.' & @CRLF & _
            'It only took ' & $hTimer & ' milliseconds to complete.')
EndFunc   ;==>_2D_1

Func _2D_2()
    Local $aArray[1][2] = [[0, 2]], $hTimer = 0, $iCount = 0, $iDimension = 0, $iIndexTotal = 0

    $hTimer = TimerInit() ; Start the timer.
    For $i = 1 To $ARRAY_SIZE
        If _ReDim2D_Ubound($aArray, $iDimension, $iIndexTotal) Then ; Returns 1 if ReDimmed OR 0 if it wasn't. This uses ByRef, so just pass the array and a previously delcared variable for monbitoring the dimension and a second variable for monitoring the total count.
            $iCount += 1 ; If array was ReDimmed then add to the ReDim count for output at the end.
        EndIf
        $aArray[0][0] += 1 ; Increase Index [0, 0] by 1.
        $aArray[$i][0] = 'Row ' & $i & ': Col 0' ; Add random data.
        $aArray[$i][1] = 'Row ' & $i & ': Col 1' ; Add random data.
    Next
    $hTimer = Round(TimerDiff($hTimer)) ; End the timer and find the difference from start to finish.

    ReDim $aArray[$aArray[0][0] + 1][$aArray[0][1]] ; Remove the empty Rows, by ReDimming the total count plus the row for holding the count and include the number of colums too.

    ; _ArrayDisplay($aArray)
    MsgBox($MB_SYSTEMMODAL, 'How many times? - _2D_2()', 'The amount of times a ' & $ARRAY_SIZE & ' element array was ''ReDimmed'' was ' & $iCount & ' times.' & @CRLF & _
            'It only took ' & $hTimer & ' milliseconds to complete.')
EndFunc   ;==>_2D_2

Func _ReDim1D(ByRef $aArray, ByRef $iDimension) ; Where Index [0] is the Row count.
    If ($aArray[0] + 1) >= $iDimension Then
        $iDimension = Ceiling(($aArray[0] + 1) * 1.5)
        ReDim $aArray[$iDimension]
        Return 1
    EndIf
EndFunc   ;==>_ReDim1D

Func _ReDim2D(ByRef $aArray, ByRef $iDimension) ; Where Index [0, 0] is the Row count and Row [0, 1] is the Column count.
    If ($aArray[0][0] + 1) >= $iDimension Then
        $iDimension = Ceiling(($aArray[0][0] + 1) * 1.5)
        ReDim $aArray[$iDimension][$aArray[0][1]]
        Return 1
    EndIf
EndFunc   ;==>_ReDim2D

Func _ReDim1D_Ubound(ByRef $aArray, ByRef $iDimension, ByRef $iCount) ; Using Ubound($aArray, 1) to find the Row size.
    $iCount += 1
    If ($iCount + 1) >= $iDimension Then
        $iDimension = Ceiling((UBound($aArray, 1) + 1) * 1.5)
        ReDim $aArray[$iDimension]
        Return 1
    EndIf
EndFunc   ;==>_ReDim1D_Ubound

Func _ReDim2D_Ubound(ByRef $aArray, ByRef $iDimension, ByRef $iCount) ; Using Ubound($aArray, 1) to find the Row size and Ubound($aArray, 2) for the Column size.
    $iCount += 1
    If ($iCount + 1) >= $iDimension Then
        $iDimension = Ceiling((UBound($aArray, 1) + 1) * 1.5)
        ReDim $aArray[$iDimension][UBound($aArray, 2)]
        Return 1
    EndIf
EndFunc   ;==>_ReDim2D_Ubound

Edited June 3, 2013 by guinness

[guinness]

This is not about replacing the functions in Array.au3, it's more concerned with those who use large Arrays and want to improve the efficiency of their application. Below is an example of adding data to an Array using the method of increasing the Array size by *2, though this is when a ReDim is required. As you can see from the example output below the difference is considerably large. Any tricks or tips with Arrays then please post below.

Example of _ArrayAddEx():

expandcollapse popup

#include <Array.au3>

Example()

Func Example()
    Local $aArray_1[1] = ['Data_0'], $aArray_2[1] = ['Data_0'], $hTimer = 0, $iCount = 0, $iDimension = 0

    $hTimer = TimerInit() ; Start the timer.
    For $i = 1 To 5000
        _ArrayAdd($aArray_1, 'Data_' & $i)
    Next
    $hTimer = Round(TimerDiff($hTimer)) ; End the timer and find the difference from start to finish.
    ConsoleWrite('_ArrayAdd from Array.au3 >> ' & $hTimer & @CRLF)
    _ArrayDisplay($aArray_1)

    $hTimer = TimerInit() ; Start the timer.
    For $i = 1 To 5000
        _ArrayAddEx($aArray_2, 'Data_' & $i, $iDimension, $iCount) ; $iDimension is the overall size of the array & $iCount is the last index number, because regarding the overall size +1 as the next item will give false results as we're increasing the size of the array not by 1 but multiplying 2.
    Next
    $hTimer = Round(TimerDiff($hTimer)); End the timer and find the difference from start to finish.
    ConsoleWrite('_ArrayAddEx by guinness >> ' & $hTimer & @CRLF)
    ReDim $aArray_2[$iCount] ; Remove the empty rows.
    _ArrayDisplay($aArray_2)
EndFunc   ;==>Example

Func _ArrayAddEx(ByRef $aArray, $sData, ByRef $iDimension, ByRef $iCount) ; Taken from Array.au3 and modified by guinness to reduce the use of ReDim.
    If IsArray($aArray) = 0 Then
        Return SetError(1, 0, -1)
    EndIf

    If UBound($aArray, 0) <> 1 Then
        Return SetError(2, 0, -1)
    EndIf

    If $iCount = 0 Then
        $iCount = UBound($aArray, 1)
    EndIf

    $iCount += 1
    If ($iCount + 1) >= $iDimension Then
        $iDimension = Ceiling((UBound($aArray, 1) + 1) * 1.5)
        ReDim $aArray[$iDimension]
    EndIf
    $aArray[$iCount - 1] = $sData
    Return $iCount - 1
EndFunc   ;==>_ArrayAddEx

Example output:

_ArrayAdd from Array.au3 >> 9523

_ArrayAddEx by guinness >> 138

Edited October 10, 2012 by guinness

[BrewManNH]

Nice speed increase using this. But your example might want to use ReDim at the end so that the arrays display the same. This might confuse some new users into thinking that it doesn't work the same and then they'd end up not using it.

I like the way you went about it.

[guinness]

Thanks BrewManNH. I've updated the example.

[Shaggi]

Typically, you increase size by 1.3 or so.. using your technique on a huge array with small elements may use excessive space (worst case near double)

Imagine i had an array with 10000 elements that are ints, if i wanted to add just one more int it would add 9999 unused indexes. Resizing arrays is a costly business, when writing such a script the author should be aware of the problem and implement his own algorithm

[jvanegmond]

I gave you ideas, guinness?

( See my last post )

Edited October 8, 2011 by Manadar

[AdmiralAlkex]

Empty elements take practically no space at all so a few thousand (or even millions!!) empty is totally worth the speed difference.

Run this with Task Manager on:

MsgBox(0, "", "")
Global $a[1000000]
MsgBox(0, "", "")

1 million elements in about 8 MB RAM. This scales linearly.

MsgBox(0, "", "")
Global $a[16777216]
MsgBox(0, "", "")

The absolute max in 128 MB. NOTE that I'm running x64 code by default. Set #AutoIt3Wrapper_UseX64=n and it's just 64 MB!!

So in big enough situations you could actually just declare max and work from there.

Also related to this, copying take no space either.

MsgBox(0, "", "")
Global $a[16777216]
MsgBox(0, "", "")
$b = $a
$c = $a
$d = $a
$e = $a
MsgBox(0, "", "")

Edited October 9, 2011 by AdmiralAlkex

[guinness]

I gave you ideas, guinness?

Honestly I didn't even see your post though now I wish I did. The post by Melba23 I was referring to was

[money]

Decent results:

_ArrayAdd from Array.au3 >> 4605.65909913131
_ArrayAddEx function by guinness >> 4743.97667860021
_ArrayAddEx function (no error checking) >> 3535.55046800641
_ArrayAddEx (no function)  >> 2084.16125513159
_ArrayAddEx (no ubound) >> 1455.13158795322
Array Add hardcoded >> 742.881008619811

_ArrayAdd was actually set to loop 2000x the rest were loop 99999x

Edited October 8, 2011 by money

[guinness]

Out of curiosity what were the functions you created money?

AdmiralAlex, thanks for that

Edited October 8, 2011 by guinness

[AdmiralAlkex]

I just realized those numbers are doubled on x64, it's only half my numbers if you set #AutoIt3Wrapper_UseX64=n. I will update the post above to reflect this.

[BrewManNH]

@Shaggi

Another thing to add to what AdmiralAlkek stated, once you ReDim your array down to be just large enough to hold all of the elements you need, most of that memory is recovered, so the point is a moot one.

[jaberwacky]

I wonder what the possibilities are concerning AutoIt ever having a list structure. If we had a list then this wouldn't even be a problem. Right?

[JScript]

@guinness

Criticisms and discussions aside, I really liked!!!

João Carlos.

[KaFu]

Honestly I didn't even see your post though now I wish I did. The post by Melba23 I was referring to was

...

Edit:

Nevertheless this summary and the underlying explanation is of course a great example ...

Edited October 9, 2011 by KaFu

[guinness]

I've updated the example and syntax in the original post. I also changed the calculation for redimming, opting for Total_Size * 1.5 and using Ceiling() to round to the nearest integer. Any suggestions then please post below.

[guinness]

I've updated the example replacing 4096 (in the MsgBox function) to the constant variable $MB_SYSTEMMODAL and added additional output data to the message boxes.

[lbsl]

Quite an old topic...

But if you want to have the most optimized array generation, you simply create one meeting the dimension of the records you are going to process, but instead of using the record counter to fill the array, you use a counter variable that you increase for each correct record that you added to the array. In the end, you redim the complete array to the secondary counter value -1 to have it sized down to the actual content:
 

$Record = UBound($MyUnprocessedArray)
Local $Added = 1
Dim $ProcessedArray[$Record]
For $x = 0 To UBound($MyUnprocessedArray) - 1

    If $MyUnprocessedArray[$x] == "Good" Then
        $ProcessedArray[$Added - 1] = $MyUnprocessedArray[$x]
        $Added += 1
    EndIf
Next
ReDim $ProcessedArray[$Added - 1]

No crap about working 1.5 times or 2 times ahead in size. You know what it could contain the most and you will bring it down to what it actually contains in the end.
The dim ahead function with just a smaller ceiling may only be efficient when you don't know what the maximum ceiling is going to be, but if i do know, i rather use my above method than the partial resized size method.
 

[guinness]

Thanks for posting.

[FireFox]

It's not the same point, the _ReDim function was created if you don't know how many elements you will add, especially if its filled size keeps changing or increasing.