What's more efficent, collections or arrays?

[Azylaminaz]

Well, someone told me it is better to use arrays of say players rather than forces, or use arrays of units rather than groups simply because it is more efficient..

Say I wanted to make a sliding and death trigger for an ice maze. This is how I would do so using groups:

globals
    group mazers
    constant real speed = 5
    constant real radius = 32
endglobals

function Trig_SlideandDeath2_Actions takes nothing returns nothing
    local group g = CreateGroup()
    local group g2
    local unit u
    local unit u2
    local real x
    local real y
    call GroupAddGroup(mazers, g)
    loop
        set u = FirstOfGroup(g)
        exitwhen u = null
        if GetUnitState(u, UNIT_STATE_LIFE) > 0 then
            set x = GetUnitX(u) + speed * Cos(GetUnitFacing(u) * bj_DEGTORAD)
            set y = GetUnitY(u) + speed * Sin(GetUnitFacing(u) * bj_DEGTORAD)
            if GetTerrainType(x, y) == 'Nice' then
                call KillUnit(u)
            else
                call SetUnitPosition(u, x, y)
                set g2 = CreateGroup()
                call GroupEnumUnitsInRange(g2, x, y, radius, null)
                loop
                    set u2 = FirstOfGroup(g2)
                    exitwhen u2 = null
                    if Not(IsUnitAlly(u2, GetOwningPlayer(u))) then
                        call KillUnit(u)
                        exitwhen 1 == 1
                    endif
                    call GroupRemoveUnit(g2, u2)
                    set u2 = null
                endloop
                call DestroyGroup(g2)
                set g2 = null
            endif
        endif
        call GroupRemoveUnit(g, u)
        set u = null
    endloop
    call DestroyGroup(g)
    set g = null
endfunction

//===========================================================================
function InitTrig_SlideandDeath2 takes nothing returns nothing
    local trigger t = CreateTrigger()
    call TriggerRegisterTimerEvent(t, .03, true)
    call TriggerAddAction(t, function Trig_SlideandDeath2_Actions)
endfunction

With arrays, I would do:

globals
    unit array heroes
    unit array allUnits
    constant real radius = 32
    constant real speed = 5
endglobals

function Trig_SlideAndDeath_Actions takes nothing returns nothing
    local real x
    local real y
    local integer i = 0
    local integer i2
    loop
        exitwhen heroes<i> = null
        if GetUnitState(heroes<i>, UNIT_STATE_LIFE) &gt; 0 then
            set x = GetUnitX(heroes<i>) + speed * Cos(GetUnitFacing(heroes<i>) * bj_DEGTORAD)
            set y = GetUnitY(heroes<i>) + speed * Sin(GetUnitFacing(heroes<i>) * bj_DEGTORAD)
            if GetTerrainType(x, y) == &#039;Nice&#039; then
                call KillUnit(heroes<i>)
            else
                call SetUnitPosition(heroes<i>, x, y)
                set i2 = 0
                loop
                    exitwhen allUnits<i> == null
                    if SquareRoot((GetUnitX(allUnits[i2]) - x) * (GetUnitX(allUnits[i2]) - x) + (GetUnitY(allUnits[i2]) - y) * (GetUnitY(allUnits[i2]) - y)) &lt; radius and Not(IsUnitAlly(allUnits[i2], GetOwningPlayer(heroes<i>))) then
                        call KillUnit(heroes<i>)
                        exitwhen 1 == 1
                    endif
                    set i2 = i2 + 1
                endloop
            endif
        endif
        set i = i + 1
    endloop
endfunction

//===========================================================================
function InitTrig_SlideAndDeath takes nothing returns nothing
    local trigger t = CreateTrigger()
    call TriggerAddAction(t, function Trig_SlideAndDeath_Actions)
endfunction</i></i></i></i></i></i></i></i></i></i></i>

With the arrays, though, I would need to make a way to handle the global array for allUnits (and any other array system, as well, same with forces). I would approach this two ways, either by making it index at the front (which is how the above functions treat it) or by making the empty indexes point towards a flag, in which instead of exiting loops, the flag positions would be ignored and the loop would loop 0-8191, doing basically nothing on every empty index.
Making all the units fill the front slots would require me to loop to find an open index every time a unit is created. Every time a unit is removed, though, I would need to loop through the entire index shifting every position to the front.
A flag system would start out every index pointing towards a specific unit (one that isn't anywhere or w/e, basically imaginary). When a unit is created, it would be stored at the first location in which the flag unit is found. When a unit is removed, all I would need to do is set the slot to the flag unit again.

I'm just wondering, how is the most efficient way to go about this? I never took time to wonder how efficient my coding really was, just as long as it worked. Is there a way to gauge how much power is required to run a function? IE, counting the number of micro-ops of the function (including calls to other functions).

I don't know, I'm just bored. Also, I don't know if the actual code will work at all.. It might have a bit a typos, didn't run it through a compiler or anything. >.<; But that isn't the point.

Edit:
I don't like using ForForce or ForGroup because you can't pass locals between them, which is something I generally am heavily dependent on.

 

[Nestharus]

arrays are better than standard wc3 collections. From there, depending on what you are doing, hand written collections can be better than plain old arrays.

For example, because you don't care about order, an indexed array would be your best option for ice sliding.


There are actually utilities out there now for handling forces and players without using the natives... they are better than the standard wc3 things as well and work fully off of indexed arrays, so much faster too.

If you're interested, you can give me a PM. I wrote both of them ><. You can understand why I did too : ).


Also, for enumerations of units, items, and destructables, going through an array of all of them is faster than using an Enum native. However, you can run into the operation limit very quickly ;o.

 

[Zwiebelchen]

Also, for enumerations of units, items, and destructables, going through an array of all of them is faster than using an Enum native. However, you can run into the operation limit very quickly ;o.

Hmm, if you need the group only once, enumeration is faster than building up an array. Also, the TO did not write efficient code with those enumerations. Use filters, as they are (by logic) a lot faster than enumeration and looping through its members.
It makes no sense to build up a group and then loop through it removing its members again. Why don't you do what you need directly at the enumeration process by using a filter func? As a side effect, you also keep all of the group members and are able to use them again if you need so.


There was this benchmark thread about what is faster; arrays or collections and collections win if used correctly - at least if you need the collection only once. If you want to use it again, arrays are faster.

 

[Nestharus]

filter-
SetUnitX(GetFilterUnit(), GetUnitX(GetFilterUnit())+10)
----------------

ForGroup(..., filter)

is slower than

loop {
    SetUnitX(u[x], GetUnitX(u[x])+10)
    exitwhen x-- == 0
}

The array is already built.. you don't build it each time you iterate through it : p.

I always use indexed arrays for extremely efficient systems : )

Also, I never ever use group handles unless I'm doing an enumeration of units in an area and I never ever use force handles =).

 

[Zwiebelchen]

The array is already built.. you don't build it each time you iterate through it : p.

I already said that arrays are faster if you do not need to build them up anymore. However, if you have to build up your set before, groups are better, because you can do all your actions directly at the build-up process.

function lolfilter takes nothing returns nothing
      set ... bla
      return false
endfunction

call GroupEnumUnitsInRange(g, x, y, r, Condition(function lolfilter))

You see? If you want to use the set only once, enumeration with filter is better than an array, because you'd have to loop twice (enumeration for building up the array, actual looping through the array), instead of once.

I always use indexed arrays for extremely efficient systems : )

Also, I never ever use group handles unless I'm doing an enumeration of units in an area

Groups have undenyable advantages over unit arrays. Speed-wise, arrays might be better, sure, but you can not pass arrays as parameters to functions and this alone makes groups awesome compared to unit arrays.

Avoiding groups at all and doing everything with unit arrays will not get you anywhere. A reasonable mixture (depending in what you want to do) is the best.

 

[Nestharus]

Already knew all of that, heh =).

I was answering from an efficiency standpoint =).

I'm just wondering, how is the most efficient way to go about this?

Especially considering that was what he was asking about. He wasn't asking about maintainability =P.

Answer the question being asked, not the questions that aren't being asked : P.

 

[kingkingyyk3]

Linked list is faster than array, if you are using loop and n = n + 1

 

[weaaddar]

Bleh stop propagating the myth. Array is faster in SOME cases as is LinkedList. A linkedlist of units is slower than an array of units, where as a linked struct using the module or a hand crafted system will be faster than the array that indexs a struct. (note: I'm saying they are both fast and neither should be preferred on the merit of speed). Also the n=n+1 & test if its equal to some variable is not even worth switching to n-=1 and test if its equal to -1, its going to be .05 ms different on array of 1000 elements.

Either way, yes if you are maintaining the collection of units and you are quite convinced they will never die or disappear from the game use an array. If they might die use something like AIDs or UnitListModule or even a group they are all going to be roughly equivalent. The difference of iteration won't be great.

 

[Nestharus]

No, if they die you'd want an indexed array over linked list if you didn't care about the order : |.

Also a linked list will be faster for iteration than an indexed array, but an indexed array takes up less memory and is much faster for adding/removing elements. Also the difference in speed between them is so very tiny that an indexed array would probably be better considering add/removal of elements.


Really, like I said, for what you are doing, you should use an indexed array. It's minimal memory, minimal work, and simple. You don't care about the order of iteration for what you're doing, so it's perfect, lol. You're also adding and removing units as they go on ice and what not, so again perfect. But it can be debated that a linked list might be better because of the iteration.

I personally would use an indexed array in this case, but that's just me =). I don't use linked list unless I care about the order of iteration ;p.

 

[weaaddar]

Look at my benchmark thread for enumeration vs array vs linked list where it shows that an array of units will be faster than a linked list of units. Please stop propagating the myth.

 

[Nestharus]

Look at my benchmark thread for enumeration vs array vs linked list where it shows that an array of units will be faster than a linked list of units. Please stop propagating the myth.

I've benchmarked it too ;p

It has to do with a set+operation vs just a set.

 

[weaaddar]

Eh actually the code comes down
[ljass] localvar = array[localvar][/ljass] vs [ljass] localvar = localvar + 1[/ljass]

The [ljass] localvar+1[/ljass] is faster than the [ljass]array[/ljass] read.

 

[Nestharus]

untrue

array reads are the same speed as regular global reads and I believe globals are faster than locals ; ).

 

[Jesus4Lyf]

Look at my benchmark thread for enumeration vs array vs linked list where it shows that an array of units will be faster than a linked list of units. Please stop propagating the myth.

I posted the logical reality in that thread already. A list of structs is better than an array of structs. An array of units is better than a list of units. :thup: