Optimized Array.au3

[-Ultima-]

Completed

These UDFs have been integrated into AutoIt's standard UDFs as of AutoIt v3.2.12.0.

Last version posted: HERE (2007-12-26)

_Array_UDF.zip_Array_Benchmark.zip

(Old version left for archival purposes, in case I mess something up in newer versions)

Array_UDF.zipArray_UDF_Benchmark.zip

IMPORTANT

For anyone using _GUICtrlListView_SimpleSort() from GUIListview.au3 while testing this, you're gonna need to change the line in that file that reads

_ArraySort($a_lv, $b_desc, 0, 0, $columns + 1, $iCol)

to

_ArraySort($a_lv, $b_desc, 0, 0, $iCol)

As far as I can tell, that's the only UDF that requires a change, since I removed the $i_Dim parameter from _ArraySort() in favor of simplicity-of-use (over a negligible increase in sorting time -- perfectly unnoticable, even after calling _ArraySort() thousands of times).

SUMMARY

-=-=-=-=-=-
- CLEANUP -
-=-=-=-=-=-

I tried to make things as consistent as I could while going through Array.au3. I reformatted function headers, made variable naming at least a bit more consistent, and made bounds checking more consistent. If there is an $iStart parameter in the function, it also has an $iEnd. In the process, of making all of these changes, I might've broken backwards compatibility a bit for some functions. They should all be listed in Compatibility.txt though.


-=-=-=-=-=-=-=-
- OPTIMIZING  -
-=-=-=-=-=-=-=-

- [MAJOR] The easiest things to optimize were the loops. Many of the loops weren't as tight as they could be, and people kept using if statements inside the loops when it could just as simply have been done outside of the loop. Making AutoIt check a condition over and over in a loop when the condition is never going to change is a big waste of resources. I can understand why people would want to make the code more elegant by minimizing repetition of code, but if the performance can be increased by anywhere from 50% to 70%, it's just not worth it to write the code in that manner. It's not as if the code becomes unreadable after moving the conditionals outside of the loops either. So yeah, if performance is an issue to you, then one of the most important things you need to do is make sure that you don't have unnecessary, never-changing conditional checks inside a loop. There may be exceptions, but you'll find this to hold true in most cases. If in doubt, simply run both versions of your function through several hundred or thousand iterations in a loop, and time it to see which one takes less time.

- [MINOR] Using SetError() and then Return "" separately is a bit wasteful, especially since you could simply use Return SetError(1, 0, ""). This improved performance by anywhere from 1-5%.

- [MINOR] "If Not $variable Then" is faster than "If $variable = 0 Then" is faster than "If $variable == 0 Then".

- [MINOR] "$iVar = $iVar + 1" is slower than "$iVar += 1". The same can be said about any of the other operations (-=, *=, /=).

CHANGES

expandcollapse popup

The following is a list of changes. The list might not be exhaustive; they're just a list of things I saw while comparing my Array.au3 with the standard UDF's while writing this. The performance differences are what I saw with the scripts I used to test (so YMMV), but some of the new functions might scale up more nicely than the old ones in terms of performance when there are more items in the array.

-=-=-=-=-=-=-=-=-=-
- OBVIOUS CHANGES -
-=-=-=-=-=-=-=-=-=-

_ArrayAdd():
===========
- Performance Difference: negligible for small arrays, scales up better than old version
- Now returns the index of the newly-added item


_ArrayBinarySearch():
====================
- Performance Difference: ~4% faster
- Added $iEnd parameter


_ArrayDelete():
==============
- Performance Difference: up to ~80% faster (less if $iElement near 0, more if $iElement near UBound($avArray))
- Can delete an item from a 1-element array (sets array to "" afterwards); this was done for consistency with _ArrayPop()
- Supports deletion of entire rows from 2D arrays


_ArrayDisplay():
===============
- Performance Difference: up to ~5% faster (tested by placing TimerInit() at beginning of function and TimerDiff() right after GUISetState() is called)
- ~35% smaller in code size
- ~99% more readable :P
- Moved outside of Array.au3


_ArrayMax():
===========
- Performance Difference: See _ArrayMaxIndex()
- Added $iEnd parameter


_ArrayMaxIndex():
================
- Performance Difference: up to ~45% faster
- Added $iEnd parameter


_ArrayMin():
===========
- Performance Difference: See _ArrayMinIndex()
- Added $iEnd parameter


_ArrayMinIndex():
================
- Performance Difference: up to ~45% faster
- Added $iEnd parameter


_ArrayPush():
============
- Performance Difference: up to ~90% faster (depends on $vValue type; improvements more visible on arrays)
- Fixed broken support for $vValue as an array while $iDirection is set to true


_ArraySearch():
==============
- Performance Difference: up to ~65% faster
- 2D arrays now supported
- Ability to search array in reverse order (end to beginning)


_ArraySort():
============
- Perfomance Difference: up to 40% faster
- Removed $i_Dim parameter, since it was pretty useless; now detected in function (hence the performance "hit")


_ArrayToClip():
==============
- Perfomance difference: up to ~80% faster
- Added $iEnd as a parameter to complement the $iStart


_ArrayToString():
================
- Perfomance difference: negligible
- Rewrote bounds checking to make it more more consistent with other functions


_ArrayTrim():
============
- Perfomance difference: up to ~25% faster



-=-=-=-=-=-=-=-=-=-=-
- SMALL ADJUSTMENTS -
-=-=-=-=-=-=-=-=-=-=-
Minor touchups to code... still achieved some performance improvement somewhere along the lines of 1-10%

_ArrayInsert():
==============
- Performance Difference: up to ~2% faster


_ArrayPop():
===========
- Performance Difference: negligible


_ArrayReverse():
===============
- Performance Difference: up to ~12% faster


_ArraySwap():
============
- Performance Difference: up to ~5% faster
- The code for _ArraySwap() isn't even array specific. It works for any variables that are passed into it. Ideally, I think it should be called _Swap(), and moved outside of Array.au3. Anyhow, I removed one measly line of code (SetError(0)) to get the performance boost.



-=-=-=-=-=-=-
- UNCHANGED -
-=-=-=-=-=-=-

_ArrayCreate():
==============
- Absolutely nothing to change besides the function header



-=-=-=-=-=-=-=-=-
- NEW FUNCTIONS -
-=-=-=-=-=-=-=-=-

_ArrayConcatenate():
===================
- Concatenate two arrays


_ArrayDisplayTree():
===================
- Displays given array in a treeview, with multi-dimensional and nested arrays supported


_ArrayFindAll():
===============
- Find the indices of all ocurrences of a search query between two points in a 1D or 2D array using _ArraySearch()

COMPATIBILITY CONCERNS

expandcollapse popup

-=-=-=-=-=-=-=-=-=-=-=-
COMPATIBILITY  CONCERNS
-=-=-=-=-=-=-=-=-=-=-=-

_ArrayAdd():
===========
- Changed the failure return value from 0 to -1
- Changed the success return value from 1 to the index of the newly-added item (shouldn't be a problem if people were properly checking for @error instead of the return value)


_ArrayBinarySearch():
====================
- Changed the failure return value from "" to -1. I made this change for the sake of consistency with _ArraySearch()'s failure return value. In the context of returning index values, -1 seems like a better failure response than simply an empty string...


_ArrayDelete():
==============
- I'm not really sure if this would cause a compatibility problem, but um... Instead of failing to delete the last item in a 1-element array, I made the function behave more like _ArrayPop() by setting the passed array to "" instead of leaving it alone.
- Along the same lines as above, the size of the array is now returned instead of 1. Accordingly, scripts that check the return value for errors instead of the @error macro might need to be updated


_ArrayDisplay():
===============
- Uh, the function is now outside Array.au3. Anyone who needs it needs to include ArrayDisplay.au3 too
- I made the function take the array in by reference instead of value for consistency with the other _Array* functions (people who used this function to display arrays on-the-fly need to store the array in a variable now before calling this function)


_ArrayMaxIndex() / _ArrayMinIndex():
===================================
- For the same reasons as with _ArrayBinarySearch(), I changed the failure return value to -1. Basically, if index, then return -1 on failure; if value, then return "" on failure; if miscellaneous, it's usually return 0 on failure. That's how I made my decisions for the return values anyway. IMHO, making everything consistent now makes it easier to maintain in the future, and makes it easier for people that use the functions regularly :\


_ArrayPush():
============
- Well, the function originally used the return value as the error signal, which is probably a bad idea. I simply set it to return 0 and make proper use of error codes on failure.


_ArraySort():
============
- The $i_Dim parameter was removed entirely, and $i_SortIndex (now called $iSubItem) moves up one position to take its place...


_ArrayTrim():
============
- Function takes and modifies array by reference; no longer returns modified array (consistency with other _Array* functions)


_GUICtrlListView_SimpleSort() [in GuiListView.au3]:
===========================
- The function calls _ArraySort() as if $i_Dim were still there. It needs to be updated to reflect the change.

Edited August 16, 2008 by -Ultima-

[jokke]

Rename it to _Array.au3 so we dont need to overwrite our existing Array.au3

Btw cant wait to test it out

[-Ultima-]

Well, it's not too hard to do that yourself

This is, if nothing goes wrong, meant to replace the existing Array.au3 anyway. Happy testing!

[jokke]

Well i cant rename it into _array.au3 cause you are calling Array.au3 inn every other file you added to your package, so original had to be renamed instead no biggie though..

Iwe got a error using this code though:

#include <Array.au3>
Dim $array[100][2]

For $x = 0 To 99
    
    $array[$x][0] = Random(0,100)
    
Next

_ArrayDisplay($array)

C:\Program Files\AutoIt3\Include\Array.au3(796,91) : ERROR: _ArraySort() called by a previous line with 6 arg(s). Min = 5. First previous line calling this Func is 1813.
Func _ArraySort(ByRef $avArray, $iDescending = 0, $iStart = 0, $iEnd = -1, $iSubItem = -1)

And thanks for your work, looking good

Hehe guess thats what i need to edit

Edited August 25, 2007 by jokke

[GEOSoft]

Well, it's not too hard to do that yourself

This is, if nothing goes wrong, meant to replace the existing Array.au3 anyway. Happy testing!

I just named mine arrayX.au3

You have in incoming PM. Please reply when you get time.

[WeMartiansAreFriendly]

I havent tested it yet, but went through the code, and it looks good.

[-Ultima-]

@jokke: That error would have to do with this:

Edit:

Oh, and for anyone using _GUIListViewSort() from GUIListview.au3 while testing this, you're gonna need to change line 1813 in that file from

_ArraySort($a_lv, $b_desc, 0, 0, $columns + 1, $i_sortcol)

to

_ArraySort($a_lv, $b_desc, 0, 0, $i_sortcol)

As far as I can tell, that's the only UDF that requires a change, since I removed the $i_Dim parameter from _ArraySort() in favor of simplicity-of-use (over a negligible increase in sorting time -- perfectly unnoticable, even after calling _ArraySort() thousands of times).

Edit: Ah, you just noticed the edit Edited August 25, 2007 by -Ultima-

[randallc]

@jokke: That error would have to do with this:

Edit: Ah, you just noticed the edit

Hi,

Great effort, what I have looked at.!

I would suggest you leave that parameter in if you are going to submit as udf, as I doubt jdeb would want anything which would break scripts..; just leave it people canput "Default" or "-1" there..

Best, Randall

[RazerM]

Sounds great with speed improvements.. Keep parameters the same though or it won't be replaced.

[-Ultima-]

But leaving the parameter in there doesn't really make much sense... If it's left there but ignored by the function itself, then it'll simply cause more confusion than it already does (I myself had to stare at the function a bit before realizing what $i_Dim was for, since the documentation wasn't that clear) :\

I understand your point of view, though, as I was torn between keeping it for backwards compatibility, and removing it for cleaner code. IMHO, cleaner code should be a higher priority. It really isn't that hard to fix any scripts that are broken by the change either. The most recent case of broken backwards compatibility was a change in AutoIt's handling of icon IDs, and many scripts will be broken by that, but there is a time and place for almost everything -- breaking backwards compatibility included.

Edited August 25, 2007 by -Ultima-

[randallc]

Hi,

re _ArrayDisplay;

1. $i_ShowOver4000 - you have removed the option of limiting number displayed to 4000 if someone wants rapid display of only part; LV is slow after that, and they might sit there waiting for ages if they inadvertently try to show 100,000; or they won't havee th option of showing 4100? ; [Also, removing the parameter is a scriptbreaker as it stands....]

2. $GUIDataReplace; removing this just seems to me an inconvenience and personal preference; and why remove a "feature" which is already present?; but might be reaonable; I personally would prefer to change the displayed character if there is a clash, than change the separator...; if I inadvertently try to display an array with a separator which is already in an item, the display will crash too.... you are not checking for that?

3. You have removed the limit on number of columns, so will reach the limit of LV display width for number of pixels; are you just interested in spedd, not crashing or display?.. I have written a further improvement on this, but not well tested yet, and when I was writing it, AutoIt was crashing over a certain limit of columns anyway; I haven't looked since that was fixed.

If UBound($ar_2DArray, 2) > 200 Then ; GUICtrlCreateListViewItem can only display listview columns to a certain number of pixels on the header, so colwidth needs to be set/ shrunk if too many??
        $i_ColWidth = 40 / (1 + Int(UBound($ar_2DArray, 2) / 800))
        For $i = 1 To UBound($ar_2DArray, 2)
            _GUICtrlListViewSetColumnWidth($searchlistView, $i, $i_ColWidth)
        Next
    Else
        _GUICtrlListViewSetColumnWidth($searchlistView, 0, $LVSCW_AUTOSIZE)
    EndIf

; do you have any reason to remove that; more speed, more crashes?

5. I have done extra enhancements, not tested, so column names can be used; perhaps you would be interested to test/ change the script too?

Best, randall

Edited August 25, 2007 by randallc

[randallc]

hi,

AutoIt's handling of icon IDs,

That was not in a UDF,though; and its enough trouble when the main pogram has to change something; I would not want to add to the probs with the UDfs too.., and I suspect that applies to jdeb...?

Best, Randall

[-Ultima-]

1 and 3)

Local $iColLimit = 250, $iLVIAddUDFThreshold = 4000, $iWidth = 640, $iHeight = 480

...

If $iSubItems > $iColLimit Then $iSubItems = $iColLimit

...

If $iLVIAddUDFThreshold > $iUBound - 1 Then $iLVIAddUDFThreshold = $iUBound - 1
For $i = 0 To $iLVIAddUDFThreshold
    GUICtrlCreateListViewItem($avArrayText[$i], $iListView)
Next
For $i = ($iLVIAddUDFThreshold + 1) To ($iUBound - 1)
    _GUICtrlListViewInsertItem($avArrayText[$i], -1, $iCurItem)
Next

2) Maybe it was a preference thing more than anything, but really, you could choose any other character as the separator if you so wish -- even a non-printing, control character, and it should still work. That said, I just tried the separator code, and it seems to be broken. I'll fix it in a bit. Fixed on my copy here, will upload later after I've gone through your code and GEOSoft's code.

4) The error checking seemed superfluous to me. The GUI_MAXCONTROLS = 4093 occurs per window, and I know for a fact I'll never hit the limit with the window having so little controls. When I do hit the limit because of too many items, I already have $iLVIAddUDFThreshold in place.

5) I'll take a look at your code, thanks

I'm not so interested in speed that would sacrifice stability for it. I just saw little point behind some of the code (truly no offense intended), and pruning unused/redundant/unnecessary code was all part of my rewrite :\

Edited August 25, 2007 by -Ultima-

[GEOSoft]

But leaving the parameter in there doesn't really make much sense... If it's left there but ignored by the function itself, then it'll simply cause more confusion than it already does (I myself had to stare at the function a bit before realizing what $i_Dim was for, since the documentation wasn't that clear) :\

I understand your point of view, though, as I was torn between keeping it for backwards compatibility, and removing it for cleaner code. IMHO, cleaner code should be a higher priority. It really isn't that hard to fix any scripts that are broken by the change either. The most recent case of broken backwards compatibility was a change in AutoIt's handling of icon IDs, and many scripts will be broken by that, but there is a time and place for almost everything -- breaking backwards compatibility included.

If you change the parameters then it becomes a script breker. They have to be in there in the same order. Any new params can be added at the end. See the __ArraySearch that I sent.

[Jos]

But leaving the parameter in there doesn't really make much sense... If it's left there but ignored by the function itself, then it'll simply cause more confusion than it already does (I myself had to stare at the function a bit before realizing what $i_Dim was for, since the documentation wasn't that clear) :\

I understand your point of view, though, as I was torn between keeping it for backwards compatibility, and removing it for cleaner code. IMHO, cleaner code should be a higher priority. It really isn't that hard to fix any scripts that are broken by the change either. The most recent case of broken backwards compatibility was a change in AutoIt's handling of icon IDs, and many scripts will be broken by that, but there is a time and place for almost everything -- breaking backwards compatibility included.

I prefer backwards compatibility over cleaner code for the simple fact that people expect the UDF to work and in general do not worry at all about how clean the Included UDF code is.

The Icon ID's change had another reason to make functions work consistently.

If you change the parameters then it becomes a script breker. They have to be in there in the same order. Any new params can be added at the end. See the __ArraySearch that I sent.

New parameters can be added at the end given they are optional or else they still would break a script. Edited August 26, 2007 by JdeB

[randallc]

Hi,

1. I still can't see how i can specify with your script to display -only- 4000 of, say, 100,000 lines?; how do I ask not to display more?

2.

and I know for a fact I'll never hit the limit with the window having so little controls.

Each created line in a listview is a control in that window.... so soon after 4000, you will hit the limit..

3. I forgot to ask how you are detecting desktop width to size your GUI?; you have removed that?

4.

you could choose any other character as the separator if you so wish

-but if you choose the wrong one, you will crash the script if it is in an item...

Best, randall

[-Ultima-]

1. OH, I totally missed that. Er, I guess I'll add it back in...

2. Believe me, I'm very familiar with the limit, and I know each call to GUICtrlCreateListViewItem() gets the GUI one step closer to the limit. The fact of the matter is, I have a total of *2* controls on the ArrayDisplay window by default. Any other control will be listview items. That means I'll never hit the 4093 limit, because by the time I reach $iLVIAddUDFThreshold, I'll switch over to _GUICtrlListViewInsertItem() anyway, which doesn't add to the limit.

3. Using Default as a arguments for X and Y position does the same thing as centering the dialog with the calculations you were using.

4. ...? If it crashes, then just pick another one... That's what the parameter is there for. I tried Chr(4) as a separator, and it worked fine...

Regarding backwards compatibility

Urg... I dunno... I'm of the opinion that just because a function was a certain way before doesn't mean that its parameters should never change (read: be reordered or removed). At this rate, parameters will just keep piling on and on without any hint of decreasing. Maybe I should just make the old functions wrap around the new ones for any that have changed parameters...

So the general consensus is that I don't break compatibility? What should I do about unused variables? What about the help file descriptions for the functions? Am I just going to list unused variables in the help file as useless, but fill them in anyway just for backwards compatibility...?

Edited August 26, 2007 by -Ultima-

[SmOke_N]

Urg... What about the help file descriptions for the functions? Am I just going to list them in the help file as useless, but fill them in anyway just for backwards compatibility...? I dunno... I'm of the opinion that just because a function was a certain way before doesn't mean that its parameters should never change (read: be reordered or removed). At this rate, parameters will just keep piling on and on without any hint of decreasing. Maybe I should just make the old functions wrap around the new ones for any that have changed parameters...

So the general consensus is that I don't break compatibility? What should I do about unused variables? What should be said in the help file?

You have to keep in mind that any type of small change can break scripts and the noobs have a hell of a time figuring out why.

As an example, when they switched the underscore for extended lines to where they had to have a space after the last char of the line you wanted to extend rather than being the last char itself... I can't tell you how many script broke and how many posts there were on it.

You're talking about re-writing an entire include directory (for the most part), which is commendable, but I can't imagine you wanting to answer 3000 posts on why their old scripts now have to be revamped.

The easiest way is the path of non-resistance here, to make them backwards compatible until you release a completely new version itself.

About the unused vars, although I'm not 100% sure on what you mean by that, I can't imagine passing a var to a function I didn't want it to use.

[Jos]

Urg... I dunno... I'm of the opinion that just because a function was a certain way before doesn't mean that its parameters should never change (read: be reordered or removed). At this rate, parameters will just keep piling on and on without any hint of decreasing. Maybe I should just make the old functions wrap around the new ones for any that have changed parameters...

So the general consensus is that I don't break compatibility? What should I do about unused variables? What about the help file descriptions for the functions? Am I just going to list unused variables in the help file as useless, but fill them in anyway just for backwards compatibility...?

I didn't mean to imply that we cannot remove parameters at all like the now obsolete $iDim, but just meant there has to be a damn good reason.

In this case the parameter became obsolete when the UBound() function was introduced in its current way of working. (before there was no way to retrieve the number of dimensions).

I have no issue with removing this parameter as I was planning to do this at some point in time myself as well, but we will have to make clear to everybody that this is a scriptbreaking change.

[-Ultima-]

About the unused vars, although I'm not 100% sure on what you mean by that, I can't imagine passing a var to a function I didn't want it to use.

Take _ArraySort() as an example.

The old function signature looked like this:

Func _ArraySort(ByRef $a_Array, $i_Decending = 0, $i_Base = 0, $i_UBound = 0, $i_Dim = 1, $i_SortIndex = 0)

The new signature looks like this:

Func _ArraySort(ByRef $avArray, $iDescending = 0, $iStart = 0, $iEnd = -1, $iSubItem = -1)

You'll notice that $i_Dim is no longer there. Now, everyone's telling me to put it back in, but if I put it back in, I'm not going to be using it anyway. It will be unused in the function body. Having the user customize $i_Dim is rather pointless, as sorting a 2D array should sort the entire row, not just the first subitems 0 to $i_Dim. If it were going to be like that, then there might as well be an $iStartSub and $iEndSub too (IMHO), which is even more... useless xD

Edit: @JdeB: Excellent. I definitely do agree that informing users that their scripts might break is the right thing to do, and that's why I mentioned it in my first post

Edited August 26, 2007 by -Ultima-