[Trigger] Array Size

[Starquizer]

Lets say I have an array unit variable of size 1 (Default), how many units that variable can store before I need to increase its size ? Or in other word how many variable-type object a 1 sized array variable can store ?

 

[MGCǂSpectre]

You can use Variable[0] and Variable[1] if you have array 1. So it should be 2 units types.

 

[Reaper2008]

Nope. You can only use Variable[0]. The index must be 1 or greater, but the count starts from 0.

 

[Starquizer]

Thats strange because I have an array variable of type Unit-Type with size 1 and I was able to set different unit types from index 1 to 15 w/o increasing the size.

 

[Arnadath]

maybe a dynamic array size i dunno

 

[Starquizer]

Or may be related to the type of the variable, perhaps ?

 

[Maker]

I remember someone saying that the game automatically reserves 8192 indexes for arrays, so theres no need to set the size of an array. I'm not 100% sure about that however. I will try to find that post.

 

[Eleandor]

An array has a size of 8192 indices, ranging from 0 to 8191. There is a known bug that the 8191th index is not saved when you save a game, so in single player, don't use that index.

The "size" of the array you see in GUI is the amount of indices that will be initialized with the value you have entered.

 

[Starquizer]

An array has a size of 8192 indices, ranging from 0 to 8191. There is a known bug that the 8191th index is not saved when you save a game, so in single player, don't use that index.

The "size" of the array you see in GUI is the amount of indices that will be initialized with the value you have entered.

So if I need to set 60 unit type I have to change the size to 60 ?

 

[Yixx]

the amount of indices that will be INITIALIZED! Gosh do you need more explanation?
When you got a unit-group array with 10 array size, it will do this:

loop
    exitwhen i > 9 // Dont know if this will become 9 or 10 though
    set udg_UNIT_GROUP[i] = CreateGroup()
    set i = i + 1
endloop

the other indices will not be initialized.

 

[Maker]

If you create an array and just leave the size to 1 it still works.

• Untitled Trigger 003
  • Events
    • Time - Elapsed game time is 5.00 seconds
  • Conditions
  • Actions
    • For each (Integer A) from 1 to 10, do (Actions)
      • Loop - Actions
        • Unit - Create 1 Footman for Player 1 (Red) at (Center of (Playable map area)) facing Default building facing degrees
        • Set Temp_Unit_Array[(Integer A)] = (Last created unit)
    • Wait 5.00 seconds
    • For each (Integer A) from 1 to 10, do (Actions)
      • Loop - Actions
        • Unit - Order Temp_Unit_Array[(Integer A)] to Move To (Center of Region 002 <gen>)

I used that trigger and all units moved to the location, although the arrays size is set to 1 initially.

 

[Deuterium]

The size in GUI is sort of stupid. I mean, even if it's 1, you can create up to 8192 arrays just by putting that number in the array

The only reason for the array size is so that the map script creates those arrays with certain values at map initialization.

 

[Arnadath]

the amount of indices that will be INITIALIZED! Gosh do you need more explanation?
When you got a unit-group array with 10 array size, it will do this:

loop
    exitwhen i > 9 // Dont know if this will become 9 or 10 though
    set udg_UNIT_GROUP[i] = CreateGroup()
    set i = i + 1
endloop

the other indices will not be initialized.

it will exeed 9 and go by 10

 

[Starquizer]

I asked for Unit-Type not group.

What I made is:
Array of Size 1 of Unit-Type.

I set it like that:

TypeA[1] = TYPE1
TypeA[2] = TYPE2
:
:
:
TypeA[16] = TYPE16

And it was still Working even with 1 size.

 

[Arnadath]

if its working it wont need to bug you but blizzard instead. Shall we report it or something?

 

[Deuterium]

And it was still Working even with 1 size.

Because it should...

I asked for Unit-Type not group.

What's the difference really? all variables function alike

 

[Starquizer]

Then 1 size can store how many object of the variable type because I remeber someone (Wizardrum I think) send a spell and he said it works twice and then stopped, then I told him to increase the array size for the dummy unit and it worked perfect. That thing is very confusing.

 

[Eleandor]

Guys, learn to read...
The "size" of arrays in GUI only matter for the initialization of the arrays. The actual size is always 8192, regardless of what you try to do.

 

[Cheezeman]

Second time that was posted.
God doesn't anyone read here? Discussion carries on even when Yixx gives the answer...

 

[Starquizer]

Guys, learn to read...
The "size" of arrays in GUI only matter for the initialization of the arrays. The actual size is always 8192, regardless of what you try to do.

OK, what is the meaning of "initialization of the arrays" ?

 

[Eleandor]

The first time you assign a value to a variable, it is called the initialization of the variable.
In the GUI variable editor you will notice that one of the things you can change is "Initial value". If you create an array of size 50, then arr[0] to arr[49] will be initialized to this initial value, while arr[50] to arr[8191] have a default value (0 for integers, "No unit" for units, "No group" for unit groups, etcetera).

Weren't you learning jass anyway?

integer array arr // You can't set a specific size, it's always of size 8192.
integer i = 0 // i is initialized to 0
loop
    exitwhen i >= 50
    set arr[i] = 3
    set i = i + 1
endloop
// arr[0] to arr[49] are initialized to "3", the rest is initialized to 0.

 

[Starquizer]

Weren't you learning jass anyway?

integer array arr // You can't set a specific size, it's always of size 8192.
integer i = 0 // i is initialized to 0
loop
    exitwhen i >= 50
    set arr[i] = 3
    set i = i + 1
endloop
// arr[0] to arr[49] are initialized to "3", the rest is initialized to 0.

Indeed I am, I was just making my TD map and I have no patience to write the entire map in JASS.

Anyway, thanks for your clarification and thanks to all who posted.

 

[Deuterium]

Eleandor saves the day

 

[Dr Super Good]

All WC3 arrays can freely use 0-8191 indexes. You can not define arrays with size in WC3.

For efficency however it allocates them in powers of 2 starting at 16 or 32 however this is the internal mechanics of WC3 and so does not influence how you when interfacing with arrays.

 

[Eleandor]

Has anyone actually ever given a decent proof that it does allocate them like that? I personally have my doubts. Firstly, why waste the time making the array larger and larger when it's only 2^15 bytes per array, and secondly why bother stopping at a size of 8192?

 

[Starquizer]

Eleandor saves the day

Truth to be told, YES.

 

[Dr Super Good]

why bother stopping at a size of 8192

Simple, to stop memory overflow. A poor script can not expend more than 32 KB an array, if there was no limate a poor script could hit 4 GB or more.

 

[Deuterium]

Has anyone actually ever given a decent proof that it does allocate them like that? I personally have my doubts. Firstly, why waste the time making the array larger and larger when it's only 2^15 bytes per array, and secondly why bother stopping at a size of 8192?

Why would you every need more then 8192 arrays? And why would it matter to you whether they do allocate that way or not?

And I guess DSG wouldn't say something unless he was 100% sure about it.

And no one is obliged to keep on providing proofs to things that should be by now obvious to all, so do your researches...

 

[Starquizer]

Eleandor, do setting the array at the initializtion trigger of the map consider an "initializing an array" and will look to its size or only at the variable editor ?

 

[Eleandor]

It doesn't really matter.

Simple, to stop memory overflow. A poor script can not expend more than 32 KB an array, if there was no limate a poor script could hit 4 GB or more.

Pff. Stupid reason. A poor script can fuck up your memory anyway. Just keep on creating units and your map eventually blows up too. So why didn't they make a unit limit? I think there are way worse methods to screw up a map than an array that uses more than 32kb.
Besides, the limit for arrays does not help at all. Just make a recursive function that has a local array. Because of its recursive nature, it keeps creating local arrays, and you'll eventually reach 4gb too. So what's the point?

Oh, right, we finally have hashtables now. They can be used as "infinite" arrays (ok, not infinite but you get the point). No clue why you can have hashtables with seemingly infinite memory capacities, but can't have arrays larger than 8192?

Why would you every need more then 8192 arrays? And why would it matter to you whether they do allocate that way or not?

Plenty of reasons. There's a reason vexorian implemented arrays larger than 8192 indices. Big downside of that is that it's really slow because it makes use of multiple normal arrays and melts them together with functions.

And no one is obliged to keep on providing proofs to things that should be by now obvious to all, so do your researches...

What do you mean "obvious by now"? It's not obvious at all, at the contrary. Would you care to show me *your* researches? Or do you just take DSG's word blindly?

 

[Dr Super Good]

I got the information from highly respected people in the jass community (I think maybe purplepoot) so I guess it is right.

Hashtables use limited sized arrays. . . Just you can interface with them like they have no limit due to the way they work. The index you store data in is a representation of the input provided when using hashtables (a hash), thus multiple input indexes will "hash" to the same hashtable index. However this is not a problem as it saves a copy of the unhashed index at that index as well and checks if that matches the input. For saving 2 indexes which hash to the same index (this case is called a hash collision) it simply stores it in the next free index and when retreving the value it loops until eithor the corrrect unhashed index is found, or until a free index is found (which results in the retrevial failing). As a rough guess the arrays in the hashtable are dynamic and will vary in size based on the number of objects stored, and the child arrays are unique to each parrent as arrays can be made in most languages on the fly and asigned to variables.

All this results in hashtables being an efficent way to save huge range indexed data in a reasonable ammount of space with mostly a O(1) efficency. The problem is if you flood the hashtables with eithor a huge number of parents, or a single parent index with a huge number of child ones. This results in hash collisions, which cause dramatic drop in efficency which can reach as low as O(n). As the array sizes used I do not know, I can not tell you the number you need for the efficency to really fall. All I can say is the size is probably in the thousands of saved values.

32 KB max arrays honsetly were probably an oversight from blizzard. For 95% of purposes 32 KB arrays are more than ample and if they are not due to large index ranges then hashing compensates. They however are totally unsuited for storing a huge ammount of generated data like extra map layers and such. Honestly in WC3's case I say they were a blessing as they make map developing simpler as they are easy as hell to manage, however from a programers point of view I would have prefered proper arrays, which are types containing an array object like those in java or C++ as they allow for a few useful opperations I will mention below. In SC2 as a rough guess by them saying its C like, will probably feature this.

Arrays of arrays, allowing extreemly efficent multi deminsional arrays which can have varible sizes of deminsions for indexes and do not waste space storing demensions on indexes that are not needed and allow for easy demension expanding by allowing the recreation of smaller arrays instead of one big one.
Passing arrays as parameters, meaning that you could perform standard opperations on variable arrays, eg you could represent a unit group as a unit array and pass it to functions which would be faster than the group type in jass which does something simlar but hashes as well.

 

[Eleandor]

You don't need to explain me how hashtables work. How do you know they use probing rather than chaining? Or is it just a random guess?

All this results in hashtables being an efficent way to save huge range indexed data in a reasonable ammount of space with mostly a O(1) efficency. The problem is if you flood the hashtables with eithor a huge number of parents, or a single parent index with a huge number of child ones. This results in hash collisions, which cause dramatic drop in efficency which can reach as low as O(n). As the array sizes used I do not know, I can not tell you the number you need for the efficency to really fall. All I can say is the size is probably in the thousands of saved values.

Right, that's why all hashtables grow as more space is needed. And they can grow waaaaay beyond a size of 8192. Don't know if this is the case for warcraft 3, but I would be very surprised if it's not, because it would be the first hashtable I've seen that doesn't grow. Besides, why would StringHash() return such large results? If hashtables in warcraft 3 have a fixed size, then they surely would have StringHash return a value between 0 and that size, right? Unless ofcourse the size is NOT fixed, and a simple Modulo is used on StringHash and the current size of the hashtable.

Most "respected jassers" are at wc3c, a site you never visit. Some things you're saying here are guesses anyway, so I don't find it very convincing when you say you know this information "from people".

32 KB max arrays honsetly were probably an oversight from blizzard. For 95% of purposes 32 KB arrays are more than ample and if they are not due to large index ranges then hashing compensates. They however are totally unsuited for storing a huge ammount of generated data like extra map layers and such. Honestly in WC3's case I say they were a blessing as they make map developing simpler as they are easy as hell to manage, however from a programers point of view I would have prefered proper arrays, which are types containing an array object like those in java or C++ as they allow for a few useful opperations I will mention below. In SC2 as a rough guess by them saying its C like, will probably feature this.

That still does not explain why they stopped at 8192. *if* arrays indeed grow, then what's the point of stopping there? If you say arrays start small because people usually don't need all the space, then why would they not allow people who *do* need the space to go beyond 8192? For all I know, that's because arrays are of fixed size, because that's easier to implement.

Arrays of arrays, allowing extreemly efficent multi deminsional arrays which can have varible sizes of deminsions for indexes and do not waste space storing demensions on indexes that are not needed and allow for easy demension expanding by allowing the recreation of smaller arrays instead of one big one.
Passing arrays as parameters, meaning that you could perform standard opperations on variable arrays, eg you could represent a unit group as a unit array and pass it to functions which would be faster than the group type in jass which does something simlar but hashes as well.

What does this have to do with anything? It's not even possible in jass anyway.

 

[Arnadath]

Let me ask something else. What if unit arrays are in fact unit group registerers that can hold one unit only. I mean in a unit group variable, you can have how many units? You get my point right?

 

[Dr Super Good]

Sigh...
StringHash returns the hash of the inputed string used in WC3 gamecasche. It was purly nativelised for 1.24 so hashtables were more useful and could store strings well like the gamecaches who they were based on. It may or may not return anything mechanical from WC3s engine.

I explained to you how hashtables work in computing, chaining seems kind of usless for hashtables as it would O(n) the efficency and result in something not called a hashtable.

It is only logical that the hashtable natives themselves do hashing on the actual inputed integers, even if that hash algerthim is but a modula integer returner.

Most "respected jassers" are at wc3c, a site you never visit. Some things you're saying here are guesses anyway, so I don't find it very convincing when you say you know this information "from people".

Go ahead, ask them about how WC3 allocates arrays, I am sure they will outline the exact same thing as I did, maybe with more accurate numbering.

 

[Eleandor]

I explained to you how hashtables work in computing, chaining seems kind of usless for hashtables as it would O(n) the efficency and result in something not called a hashtable.

Huh? Do you even know what chaining is? Probing also results in an efficiency of O(n) when there's a collision, in case you didn't realize that yet. Maybe you're the one who needs to be explained to what a hashtable is, if you're saying chaining isn't a valid technique for solving collisions...

It is only logical that the hashtable natives themselves do hashing on the actual inputed integers, even if that hash algerthim is but a modula integer returner.

It is only logical that a hashtable does not have a fixed size.

 

[Dr Super Good]

It is only logical that a hashtable does not have a fixed size.

It logically has to have a fixed size at any given point as computer memory is finite. It has been proved with the hashing used in group variables by captain griffen that the hashtable used for the group has a size of something like 64 or something before it starts to slow down horriably (hash collisions).

Probing also results in an efficiency of O(n) when there's a collision

Um..... I take it you have not covered hashes yet. It results in a variable efficency which only if the hashtable is 100% full will it reach O(n) in some cases (statistically unlikly), otherwise it is a lot less.

What hashtables probably use is an array of a fixed size of like 32 KB or something (note that this is a guess and for example as you have been struggling to tell the difference) for parents and maybe something smaller for childs. If that becomes full or exceeds its bounds it may default to linked lists for the extra data.

Disagree? then prove something otherwise, as so far your arguments have been nothing but saying I am wrong with no evidence behind them.

 

[Deuterium]

All this is interesting surely will read 2moro...

 

[aznricepuff]

Neither chaining nor probing results in O(n) searches unless every single entry hashes to the same index.

Probing can also degenerate to O(n) or near O(n) if you get lots of hash value clustering.

It results in a variable efficency which only if the hashtable is 100% full will it reach O(n) in some cases (statistically unlikly), otherwise it is a lot less.

A probing hashtable that is 100% full will just stop working (unless it reallocates to use a larger array).

 

[HINDYhat]

I'm pretty sure PipeDream was the one who figured out that array indexes were allocated in powers of 2, and that's just about the most trustworthy source I'll ever have.

 

[Eleandor]

Um..... I take it you have not covered hashes yet. It results in a variable efficency which only if the hashtable is 100% full will it reach O(n) in some cases (statistically unlikly), otherwise it is a lot less.

/facepalm.

Actually I'm right and you're wrong. You don't seem to understand how hashing works.

A hashtable is a large array. A hashfunction returns an integer which serves as the index to the array. When a collision occurs (that can be as soon as you have 2 elements, you don't need a full hashtable AT ALL), your efficiency drops to O(n) because you have to search an array. With linear probing, you must search each index after the index that corresponds to the hashed value, resulting in O(n). With separate chaining, each index points to a list. Only when 2 or more elements share the same index, the list must be searched resulting in efficiency drop. With both methods you can easily have your efficiency drop a lot without even having filled 10% of your table, if you're unlucky.

The more elements in the hashtable, the larger the chance a collision occurs. Therefor, every hashtable I have ever seen automatically resizes when it's filled for about 50%.

In fact, probing probably causes more collisions to occur than separate chaining.
In separate chaining, collisions only happen with elements that share the same hash.
In probing, collisions happen with elements that share the same hash but ALSO with elements that have a hash resulting in an index that is already used by another element.

If you claim efficiency only drops when the table is completely used, you must be on crack or you just don't know how it works at all.

Oh, and hashtables don't use an array of 32kb. Like I said: before you make some claims, go find me some proof. Test it, perhaps.

 

[aznricepuff]

When a collision occurs (that can be as soon as you have 2 elements, you don't need a full hashtable AT ALL), your efficiency drops to O(n) because you have to search an array.

It only drops to O(n) if all hash values get clustered around the same index. Otherwise, you can have a single collision but still have near constant time operations because the entries are dispersed in a random enough fashion that the next available index is either right next to the hashed-to index or very close to it (2 or 3 indexes down).

 

[Dr Super Good]

It does not loop through the whole array, its obvious you have not researched them...
It loops from the index where the collision occured to eithor the start or end of the array + spill over as hash sysytem usually save it in the neighboring index if the index is taken. It also loops until it finds an empty array as then it can not logically be past that point. As for the array size problem, after the array size is exceeded it probably falls to a linked list array to handle excess ontop of the array as it will have to loop through all excess indexes anyway, and so efficency should not reduce much. Obviously it would be more efficent in the long term to rebuild the table with a bigger array but that would eat too much time as it requires a total array rebuild and recomputation of each hash to fit into it, however is possiable but I doubt blizzard would program something like this in a lagless way.

Thus what will probably happen is that hashtables in WC3 that are overloaded with indexes will resort to near O(n) type efficency like those in groups however unless the fursest index is referd it will never obtain O(n) (why hashing is efficent for its purpose). In a 100% full hash array with data and algerthim producing random indexes (impossiable to be the case but near what a good hash system should do) the efficency should on average be O(n/2) in the wost case. If exess storage systems like lists are used on top of that it will add the list n to it (O(na/2+nl) with na being the number in the array and nl being the number in the list) which is why when you exceed the capacity of the array the efficency will drop hideously.

All in all, for efficent hashing, it is best to store less than the array size of the hashtable and if possiable rebuilding the array with room to expand instead of dumping the excess entires into a list of some form if the capacity is exceeded.

 

[aznricepuff]

For hashtables that use a fixed size array and don't ever rehash, chaining is a better collision resolution. This is because if load factor exceeds 1.00 (and you have a decent enough hashing function), search times become O(lf), where lf = load factor. This is equivalent to O(n/i), where n=number of elements and i=number of indexes in the array. Meanwhile, using probing, the table degenerates into best case O(of), where of=number of overflow elements. Actual efficiency depends on the probing algorithm.

So if you had a hashtable with 100 indexes and loaded 1000 elements into it, with chaining search times go to O(10) while with probing under best case it goes to O(900).

 

[Dr Super Good]

Ah, so each index becomes a list, that is even more efficent. Do not know why I did not see that as a possibility eariler.

 

[Braylon08]

I have a question. if using a region array i can assign regions to it... do i assign an index number to each reagion using a trigger?