1. Updated Resource Submission Rules: All model & skin resource submissions must now include an in-game screenshot. This is to help speed up the moderation process and to show how the model and/or texture looks like from the in-game camera.
    Dismiss Notice
  2. DID YOU KNOW - That you can unlock new rank icons by posting on the forums or winning contests? Click here to customize your rank or read our User Rank Policy to see a list of ranks that you can unlock. Have you won a contest and still havn't received your rank award? Then please contact the administration.
    Dismiss Notice
  3. The Lich King demands your service! We've reached the 19th edition of the Icon Contest. Come along and make some chilling servants for the one true king.
    Dismiss Notice
  4. The 4th SFX Contest has started. Be sure to participate and have a fun factor in it.
    Dismiss Notice
  5. The poll for the 21st Terraining Contest is LIVE. Be sure to check out the entries and vote for one.
    Dismiss Notice
  6. The results are out! Check them out.
    Dismiss Notice
  7. Don’t forget to sign up for the Hive Cup. There’s a 555 EUR prize pool. Sign up now!
    Dismiss Notice
  8. The Hive Workshop Cup contest results have been announced! See the maps that'll be featured in the Hive Workshop Cup tournament!
    Dismiss Notice
  9. Check out the Staff job openings thread.
    Dismiss Notice
Dismiss Notice
60,000 passwords have been reset on July 8, 2019. If you cannot login, read this.

Arrays and hashtables

Discussion in 'Triggers & Scripts' started by Krogoth, Oct 4, 2012.

  1. baassee

    baassee

    Joined:
    Nov 14, 2008
    Messages:
    3,220
    Resources:
    17
    Spells:
    14
    Tutorials:
    3
    Resources:
    17
    Who said indexing cannot be O(1) search? If we refer to GUI just use some sort of real variable event and set a temporary integer variable into the index you are currently playing with and voila you got the index but then you must remember to store it somewhere.
     
  2. PurplePoot

    PurplePoot

    Joined:
    Dec 14, 2005
    Messages:
    11,161
    Resources:
    3
    Maps:
    1
    Spells:
    1
    Tutorials:
    1
    Resources:
    3
    What is this supposed to do? Just use hashtables.
     
  3. baassee

    baassee

    Joined:
    Nov 14, 2008
    Messages:
    3,220
    Resources:
    17
    Spells:
    14
    Tutorials:
    3
    Resources:
    17
    Never (not that I have the need to do this anyway), vJASS/ZINC is much more simple thank god.
     
  4. PurplePoot

    PurplePoot

    Joined:
    Dec 14, 2005
    Messages:
    11,161
    Resources:
    3
    Maps:
    1
    Spells:
    1
    Tutorials:
    1
    Resources:
    3
    You can still use hashtables in vJass.
     
  5. baassee

    baassee

    Joined:
    Nov 14, 2008
    Messages:
    3,220
    Resources:
    17
    Spells:
    14
    Tutorials:
    3
    Resources:
    17
    Yes of course.
     
  6. edo494

    edo494

    Joined:
    Apr 16, 2012
    Messages:
    3,846
    Resources:
    5
    Spells:
    1
    JASS:
    4
    Resources:
    5
    its really just an opinion war here, one says oh hash shit!, baassee only abuses struct indexing :D(correct me if Im wrong) and other uses arrays. It doesnt matter how you do it as long as it works, really even you were talking about performence difference, all I can say is wtf? one eye blink takes so long I could add values to thousands of childkeys in same parent key in one hashtable and difference between calling SaveWhatEver and set whatever[index] is like what, 0.0001 second? lol

    Also I suggest using hashtables over arrays as arrays eat space(yes this is another what, its only some bytes but when you have hundreds of array variables its getting some size) because you can add multiple parameters to the same unit using some indexing system and just inserting index of given unit to parent key and changing(overwriting as Defskull calls it and its more right in terms of what happens) the values to whatever you want.
    For example: if I wanted to have stamina and spirt(yea wow but w/e nothing comes to my mind right now its quite late here as well) I would have to use 2 array variables and if I wanted to rewrite them it may be O(n) but using hashtable, we need only 1 parent key of hashtable, hashtable gives us oppoturninty to use O(1) if used correctly(array can be as well O(1) if used correctly) and also I need only one hashtable for all map not like we are using 255(256) hashtables, one for each spell or so(getting little off topic here). I would rather just call 2 times SaveInteger or SaveReal then using 2 fat ass arrays.
    Also hashtable can have 5 different things saved in one field at the same time(integer, real, boolean, string and any handle at the same parentkey, childkey at the same time)
     
  7. baassee

    baassee

    Joined:
    Nov 14, 2008
    Messages:
    3,220
    Resources:
    17
    Spells:
    14
    Tutorials:
    3
    Resources:
    17
    Remind me again when all spells in GUI form uses only 1 hashtable for all of them instead of 1 hashtable/spell. And yes I do know that arrays takes shitload of space compared to a non-arrayed variable that's why I try to prevent it by saying that it's useless to store things like this:

    Real[1] = X
    Real[2] = XX
    Real[3] = XXX

    And waste 8187 indexes and instead set it Real[CurrentIndex] = lvl*x. However I find myself going rather off-topic at this very moment.
     
  8. PurgeandFire

    PurgeandFire

    Code Moderator

    Joined:
    Nov 11, 2006
    Messages:
    7,426
    Resources:
    18
    Icons:
    1
    Spells:
    4
    Tutorials:
    9
    JASS:
    4
    Resources:
    18
    Hashtables eat space too. Every time something is stored, it uses memory to keep track of it. Just like an array. Hashtables are known as associative arrays.

    Arrays are generally easier to work with (nicer interface and easy to declare). The limitation is that you can only use an index of 0-8191. That is usually the case where we switch to hashtables--when we want to use bigger numbers as keys and values. The other cases are usually for simplicity (so you don't have to use indexing or other data structures), data tables, or for an easy O(1) complexity.

    I'm not 100% positive about this next statement, but the way Warcraft 3 allocates memory in terms of arrays is not an instant 0-8191 allocation. Memory is allocated depending on the indices you use. War3 allocates it by powers of 2. For example, if your max index size is 3 then it will only allocate memory for indices 0-4 (0 to 2^2). If your max index size is 1000, then it will allocate memory for indices 0-1024 (0 to 2^10). Note that this does not take into account whether you have used a total of 1000 slots. You could literally just do:
    Code (vJASS):
    globals
        real array x
    endglobals

    function Test takes nothing returns nothing
        set x[1000] = 5
    endfunction


    And it will allocate memory for all those indicies 0-1024. I guess in that way, arrays might seem a bit unfavorable but it is pretty rare to use indexes greater than 100 unless you are indexing widgets or manually hashing a value down to the index range. (for example:
    GetHandleId(h) - 0x100000
    )
     
  9. Adiktuz

    Adiktuz

    Joined:
    Oct 16, 2008
    Messages:
    9,674
    Resources:
    23
    Models:
    2
    Packs:
    1
    Maps:
    1
    Spells:
    16
    Tutorials:
    1
    JASS:
    2
    Resources:
    23
    they say JASS arrays always get all 8191 indexes upped...
     
  10. Krogoth

    Krogoth

    Joined:
    Apr 5, 2011
    Messages:
    247
    Resources:
    0
    Resources:
    0
    This should not be true.
     
  11. baassee

    baassee

    Joined:
    Nov 14, 2008
    Messages:
    3,220
    Resources:
    17
    Spells:
    14
    Tutorials:
    3
    Resources:
    17
    I do wonder about this PAF 'cause then we can rather set the array size in the globals block as well, don't you agree?

    Also I do remember Vexorian stating that one arrayed variable still takes more space than 3 non-arrayed variables (4 as well) thus creating 3 different variables (of course it's not userfriendly in any way). Thus I also wonder if your statement is true, because if you only use the first 0-1 indexes then how can the size of the variable still be greater if not memory wise? And of course having a spell with more than 4 levels is rather stupid by the player due to the fact that then you cannot convert the object into an slk-table thus the loading time will be increased by a greater amount.
     
  12. PurplePoot

    PurplePoot

    Joined:
    Dec 14, 2005
    Messages:
    11,161
    Resources:
    3
    Maps:
    1
    Spells:
    1
    Tutorials:
    1
    Resources:
    3
    That's how many elements it initializes (since GUI tries to avoid forcing the user to create most objects explicitly). The array max size is 8192. That said, warcraft 3 doesn't allocate all the memory for the array at once; it increases its size as needed (by powers of 2, if I recall correctly).
     
  13. PurgeandFire

    PurgeandFire

    Code Moderator

    Joined:
    Nov 11, 2006
    Messages:
    7,426
    Resources:
    18
    Icons:
    1
    Spells:
    4
    Tutorials:
    9
    JASS:
    4
    Resources:
    18
    @baassee: For the second paragraph, I'll try to test it eventually with war3err and let you know. :)
     
  14. edo494

    edo494

    Joined:
    Apr 16, 2012
    Messages:
    3,846
    Resources:
    5
    Spells:
    1
    JASS:
    4
    Resources:
    5
    I dont say I dont believe it but any prove of memory allocation by power of 2?
    I could check it myself but Im on mobile right now
     
  15. baassee

    baassee

    Joined:
    Nov 14, 2008
    Messages:
    3,220
    Resources:
    17
    Spells:
    14
    Tutorials:
    3
    Resources:
    17
    Blah I guess I screwed up what I was talking about. Never mind.