Optimization -> Handle2ArrayIndex

Summay

If I have an array filled with different handles; which would be the fastest way to retrieve a handle's index in the array?

Theory + Theorems

Hidden information: Given an integer value an array will quickly return a corresponding object/primitive that I've put there. That is the function of an array. As you may or may not know; any function f is inversible as long as JASS: //Logic and math x!=y <=> f(x)!=f(y) I will assume that the (function of the) array is inversible. No handle exists twice in the array.

-------------------
Small arrays

Some logic has led me to the conclusion that for small arrays, simply iterating through the array and comparing would be the fastest:

The approach above would work just fine if myArray was limited to a few objects. However, the function would become quite slow if myArray reached larger sizes (like 7777).

Large arrays

For large arrays, my hyphothesis is that a GameCache approach would be faster.

My assumption is thus that somewhere; there is a performance border between the "large" and "small" arrays. When the middle item in the array takes just as long time to reach with both methods; the border is found.

My question is, simply; how large does my array have to be before I should switch to the game cache-approach?

Whats pretty cool is that if you make a loop that creates handles, the integer ID of each handle will be +1 the last created handle. So you can just store the ID of handlearray[0] and subtract that from each handle to get its index. This only works for something you would plan on creating ahead of time, and just recycling however.

the integer attaching will usually be faster, but using gamecache isn't really necessary. There are plenty of ways to attach a single integer to a handle that are as simple as a single global array. Just use something like CSData and you'll be fine.

well you may try harder and eventually reinvent the wheel hash table .

If you need iterations through the array you may even use a balanced binary search tree and that stuff...

Although with a hash table it is easy to iterate through the elements.

If you use gamecache you are pretty much using array+hash table, doesn't matter too much.

Answer seriously depends on what type of handles are we talking about...

Please read through the entire post before replying. What I was asking for was a comparison in speed between CSCache and looping through a global array, in order to retrieve the array index for a given element (handle / object).


I like humor. :)


I just want to get the integer index corresponding to the handle (as I pretty much mentioned above). Dunno if that classifies as "need iterations".


But the post below says...


Really? That's interesting. Can you please explain why?

Well if you are using timers my preferred way is ABC + Collections
If you are using plain units I would go for PUI
If you are using only hero handles you are better with player array

If you are using arrays for special effects and something like that you best see a doctor...

Hey! :P Are you claiming that the effect-list structs that I've constructed for my maps are a waste!? :P

Now, I plan to attach the integers to triggers. Once again, I wonder; how many times can the loop run before a game-cache call would be faster?

Probably ~5.

You are doing something wrong,
I can not think of a single example where attaching integers to triggers would be useful ...

CSData does not use gamecache, its just a single global array, and has nothing to do with handlevars.

We need to know this for the same reason tuna suppliers need to know if you are using the product for fish patties or raw sushi.

Timers are easily recyclable, and so are dummy units. You could use the trick I described earlier to get the array index of the handles. Then just make a parallel integer array for data storage

For other units you could use userdata, CSData, or a hashing algorithm.

Woah! Somebody who is willing to answer, even if it is approximative!
Thanks a lot.


Never understood that before. Do you mean the internal ID that the H2I retrieves? Like this?


You must have quite some confidence to state that I am doing something wrong, only because you can't think of a usage.

A splendid useage of it is if you somehow have a handle array where the order of the handles is important. If you have one handle, and want to retrieve the next, the previos, the -2:nd, etc; you have to be able to identify its index in the array.

This is what I intended it for:


I've made an automated system for making units move between a set of regions (DotA, AoS, AotZ, that kind of pathing). Also, I keep the units moving in a group (GroupIssueOrder). A unit's custom value is an integer value that is an array index for that unit's pathgroup.

All regions are manually put in a rect array. The pathgroup's destination integer are pointing to the rect to which the units are heading.

When a unit enters a region, it will check if the entered region was the destination for that group. Event Response - Entered Region... hm, doesn't extist, does it? Luckily, I can attach an integer value to the TriggeringTrigger (which does indeed exist), that value can then point to the rect array.

If the entered rect was equal to the myRectRegion[pathgroup[GetUnitUserData(GetEnteringUnit())].destination]; I will update the destination to destination +/-1; and Issue the group move order to that region.

How about this:

You put a bunch of regions/locations/(x,y) or whatever in an array.
say from 0 to 5


When unit enters map you order it to move to point[0]
when unit enters point 0, you increase UnitUserData to 1
when unit enters point 1, you increase UnitUserData to 2
...
That way you can give all units orders to always
Attack(PointArray[UnitUserData(unit)])

Oh and make sure that you set new UserData only if it is higher than previous one.
This will prevent a unit that returned from point 4 to point 2 (because it was chasing a hero for example) to get stupid and start going to point 3 again instead to point 4.
(Important only if unit path is crossing itself like in some tower defens maps - Gem TD for example )

cohadar, that is exactly what I wrote in my previous post. The only difference is that instead of letting the UnitUserData refer directly to the point-array; I let it refer to the unit's pathingstruct. In that struct, there is the destination integer, which acts precisely as you suggested.

pathinggroup[GetUnitUserData()].destination is equal to your GetUnitUserData()
As mentioned above; I need the group variable in the pathgroup struct in order to be able to issue group orders.

Why don't you just simple use UnitUserData?

Oh I see you need it for some other system don't ya?
That is why you are asking this hashing nonsense question.

Well it is time you learn of the benefits of PUI.
You can find it in my signature.

I do not simply use UnitUserData because I use it for other stuff too. True.
That is not why I'm asking the hashing questions though.

The problem is that I want to create the pathing automatically. I do NOT want to manually create a trigger for each of the onehundredfiftyeleven regions on my map. In other words; I have a function which automatically creates a trigger for each rect that I give to it.

The drawback with this is, of course, the lack of a GetEnteredRegion()-function. Even if I'm using GetUnitUserData() to know where the unit is heading; I have nothing to compare it with.

That's why I wonder if the fastest way is to attach an integer to the trigger; or if I should just create a trigger array parallell with the rect array.

The drawback of the GC-method is that every time a valid unit enters a pathing-region; a GC-call will be used.

Hidden information: I just came up with something though! If I let the units know to which trigger they are heading to; then I can compare the triggers directly, avoiding unneccesary GC-calls! :D