wc3campaigns
WC3C Homepage - www.wc3c.netUser Control Panel (Requires Log-In)Engage in discussions with other users and join contests in the WC3C forums!Read one of our many tutorials, ranging in difficulty from beginner to advanced!Show off your artistic talents in the WC3C Gallery!Download quality models, textures, spells (vJASS/JASS), systems, and scripts!Download maps that have passed through our rigorous approval process!

Go Back   Wc3C.net > Resources > Code Resources > Scripts
User Name
Password
Register Rules Get Hosted! Chat Pastebin FAQ and Rules Members List Calendar



Reply
 
Thread Tools Search this Thread
Old 07-03-2008, 12:34 AM   #1
Vexorian
Free Software Terrorist
 
Vexorian's Avatar


Technical Director
 
Join Date: Apr 2003
Posts: 14,905

Submissions (37)

Vexorian has a reputation beyond repute (1060)Vexorian has a reputation beyond repute (1060)Vexorian has a reputation beyond repute (1060)Vexorian has a reputation beyond repute (1060)Vexorian has a reputation beyond repute (1060)Vexorian has a reputation beyond repute (1060)Vexorian has a reputation beyond repute (1060)

Hero Contest #3 - 2nd Place

Default Table 3.1

Table used to be just vJassified gamecache, now it is vJassified 'hashtable'. It is made to look like using an associative array or 'dictionary'. And the methods are coded so they are inline friendly, in other words when you use sometable[someint] and set sometable[someint]=something , you are actually using native gamecache usage. So, even though the looks understandable and self documenting, it is very close to the fastest way to use gamecache. Perhaps saving the contents of I2S in some variable before calling these functions thrice would be mildly faster, but probably not in a relevant way, there is also no good reason for doing multiple consecutive calls on the same index either.

Why gamecache? In all seriousness, speed is gamecache's only issue, Table has some advantages over customly made hash systems and CSData:
- No practical limits
- Very multi instanceable. You can have more than 1 table at the same time, in fact you may have 400000 tables at the same time, each being an indepent associative array. Oh, and its multi instancibility won't make it so you end up with 50 lines of code per instance.
- Cleaning all the contents of one Table is possibly O(1)

Why hashtable? Basically, hashtable keeps all those advantages for gamecache but it is also quite fast. Theory has it that it is just 2x times an array usage...

Some stuff:
* You may change maxinstances, a big value will remove the 8000 limit and just make allocation slower, allocation does not really matter too much or at all when you use Table correctly.
* 2d array syntax to have access to simulate "mission keys", just calls StringHash on them.


Collapse Table 3.1 (for patch 1.23b +):
library Table
//***************************************************************
//* Table object 3.1
//* ------------
//*
//*   set t=Table.create() - instanceates a new table object
//*   call t.destroy()     - destroys it
//*   t[1234567]           - Get value for key 1234567
//*                          (zero if not assigned previously)
//*   set t[12341]=32      - Assigning it.
//*   call t.flush(12341)  - Flushes the stored value, so it
//*                          doesn't use any more memory
//*   t.exists(32)         - Was key 32 assigned? Notice
//*                          that flush() unassigns values.
//*   call t.reset()       - Flushes the whole contents of the
//*                          Table.
//*
//*   call t.destroy()     - Does reset() and also recycles the id.
//*
//*   If you use HandleTable instead of Table, it is the same
//* but it uses handles as keys, the same with StringTable.
//*
//*  You can use Table on structs' onInit  if the struct is
//* placed in a library that requires Table or outside a library.
//*
//*  You can also do 2D array syntax if you want to touch
//* mission keys directly, however, since this is shared space
//* you may want to prefix your mission keys accordingly:
//*
//*  set Table["thisstring"][ 7 ] = 2
//*  set Table["thisstring"][ 5 ] = Table["thisstring"][7]
//*
//***************************************************************

//=============================================================
    globals
        private constant integer MAX_INSTANCES=8100 //400000
        //Feel free to change max instances if necessary, it will only affect allocation
        //speed which shouldn't matter that much.

    //=========================================================
        private hashtable ht = InitHashtable()
    endglobals

    private struct GTable[MAX_INSTANCES]

        method reset takes nothing returns nothing
            call FlushChildHashtable(ht, integer(this) )
        endmethod

        private method onDestroy takes nothing returns nothing
            call this.reset()
        endmethod

    endstruct

    //Hey: Don't instanciate other people's textmacros that you are not supposed to, thanks.
    //! textmacro Table__make takes name, type, key
    struct $name$ extends GTable

        method operator [] takes $type$ key returns integer
            return LoadInteger(ht, integer(this), $key$)
        endmethod

        method operator []= takes $type$ key, integer value returns nothing
            call SaveInteger(ht,  integer(this)  ,$key$, value)
        endmethod

        method flush takes $type$ key returns nothing
            call RemoveSavedInteger(ht, integer(this), $key$)
        endmethod

        method exists takes $type$ key returns boolean
            return HaveSavedInteger( ht,  integer(this)  ,$key$)
        endmethod

        static method flush2D takes string firstkey returns nothing
            call $name$(- StringHash(firstkey)).reset()
        endmethod

        static method operator [] takes string firstkey returns $name$
            return $name$(- StringHash(firstkey) )
        endmethod

    endstruct
    //! endtextmacro

    //! runtextmacro Table__make("Table","integer","key" )
    //! runtextmacro Table__make("StringTable","string", "StringHash(key)" )
    //! runtextmacro Table__make("HandleTable","handle","GetHandleId(key)" )

endlibrary

Expand Table 2.0 (for wc3 version 1.23 or earlier):

Changes in 2.0
* A 2D array syntax to handle mission keys, however, this comes with a price as in: function calls.
* The other aspects of Table have gotten a little faster as I2S is replaced with an array look up. this comes with a price as if you now change the instance limit to something larger than 8190, Table will become much slower. Just hope you don't ever, ever, need to do that.
* initializing is done using struct onInit instead of library initializer, this simply is to also allow other structs using onInit to use Tables, notice that as long as you use the Table in a library that requires Table or in a scope, its initializers are guaranteed to run after Table's.

Changes in 2.1
* Works in patch 1.23b.
* Will only work with patch 1.23b.

Thanks go to blizzard for listening in adding GetHandleId , without such native Table would have been killed.

Changes in 3.0
* Fuxing thanks to blizzard, the hashtable natives are great. Moved from gamecache to hashtable, the interface is the same, speed should have improved greatly, the static [] operator is faster. Basically, everything will get inlined to hashtable native usage now...

Changes in 3.1
* Can now be used in module initializers.
__________________
Zoom (requires log in)Wc3 map optimizer 5.0
Someone should fix .wav sound in this thing.
Zoom (requires log in)JassHelper 0.A.2.A
Turns your simple code into something that is complicated enough to work.
Faster != more useful

Last edited by Anitarf : 11-09-2011 at 12:58 PM.
Vexorian is offline   Reply With Quote
Sponsored Links - Login to hide this ad!
Old 07-03-2008, 01:38 AM   #2
Here-b-Trollz
Corkscrew Chainsaw!!!
 
Join Date: Jun 2006
Posts: 711

Here-b-Trollz has a spectacular aura about (149)

Hero Contest #2 - 2nd Place

Default

Hmm, minimal but also possible... what about this?

Collapse JASS:
library Table initializer init
//***************************************************************
//* Table object
//* ------------
//*
//*   set t=Table.create() - instanceates a new table object
//*   call t.destroy()     - destroys it
//*   t[1234567]           - Get value for index 1234567
//*                          (zero if not assigned previously)
//*   set t[12341]=32      - Assigning it.
//*   call t.flush(12341)  - Flushes the stored value, so it
//*                          doesn't use any more memory
//*   call t.reset()       - Flushes the whole contents of the
//*                          Table.
//*   call t.destroy()     - Does reset() and also recycles the id.
//*
//*
//***************************************************************

//=============================================================
    globals
        private constant integer MAX_INSTANCES=400000

    //=========================================================
        private gamecache gc
    endglobals

    struct Table[MAX_INSTANCES]
        private string index=I2S(this)
        method operator [] takes integer key returns integer
            return GetStoredInteger(gc,.index,I2S(key))
        endmethod

        method operator []= takes integer key, integer value returns nothing
            call StoreInteger(gc,.index,I2S(key), value)
        endmethod

        method flush takes integer key returns nothing
            call FlushStoredInteger(gc,.index,I2S(key))
        endmethod

        method reset takes nothing returns nothing
            call FlushStoredMission(gc,.index)
        endmethod

        private method onDestroy takes nothing returns nothing
            call FlushStoredMission(gc,.index)
        endmethod
    endstruct


    private function init takes nothing returns nothing
        call FlushGameCache(InitGameCache("libtable.gc"))
        set gc=InitGameCache("libtable.gc")
    endfunction
endlibrary

Seems to work for me, and it saves a function call. Although... i suppose it would depend on whether or not your table indexes go up past one array's worth.
__________________
By reading this signature, you agree that I cannot be held accountable for anything that I might say or do.

Last edited by Here-b-Trollz : 07-03-2008 at 01:39 AM.
Here-b-Trollz is offline   Reply With Quote
Old 07-03-2008, 01:48 AM   #3
Vexorian
Free Software Terrorist
 
Vexorian's Avatar


Technical Director
 
Join Date: Apr 2003
Posts: 14,905

Submissions (37)

Vexorian has a reputation beyond repute (1060)Vexorian has a reputation beyond repute (1060)Vexorian has a reputation beyond repute (1060)Vexorian has a reputation beyond repute (1060)Vexorian has a reputation beyond repute (1060)Vexorian has a reputation beyond repute (1060)Vexorian has a reputation beyond repute (1060)

Hero Contest #3 - 2nd Place

Default

That one actually replaces an I2S with a function call, try compiling it. If you replace MAX_INSTANCES with 8000 it becomes an array lookup, not sure if I2S is faster than an array lookup or viceversa.
__________________
Zoom (requires log in)Wc3 map optimizer 5.0
Someone should fix .wav sound in this thing.
Zoom (requires log in)JassHelper 0.A.2.A
Turns your simple code into something that is complicated enough to work.
Faster != more useful
Vexorian is offline   Reply With Quote
Old 07-03-2008, 01:56 AM   #4
Here-b-Trollz
Corkscrew Chainsaw!!!
 
Join Date: Jun 2006
Posts: 711

Here-b-Trollz has a spectacular aura about (149)

Hero Contest #2 - 2nd Place

Default

Meh. I've never done any serious benchmarking. I would assume though that since I2S doesn't create a handle, it's relatively fast? (comparatively) If that's the case, it's prolly better just to keep I2S. Gah.

By the way it rules that we finally have a scripts section up
__________________
By reading this signature, you agree that I cannot be held accountable for anything that I might say or do.

Last edited by Here-b-Trollz : 07-03-2008 at 01:58 AM.
Here-b-Trollz is offline   Reply With Quote
Old 07-03-2008, 03:42 AM   #5
moyack
Evil Emoticon
 
moyack's Avatar


Respected User
Project Leader: PoC
 
Join Date: Jan 2006
Posts: 3,266

Submissions (17)

moyack is a splendid one to behold (661)moyack is a splendid one to behold (661)moyack is a splendid one to behold (661)moyack is a splendid one to behold (661)

AI Tournament #2 - 2nd PlaceHero Contest - Second place

Send a message via MSN to moyack
Default

Just one question.... you could add a customizable gamecache filename...

Collapse JASS:
globals
        private constant integer MAX_INSTANCES=400000
        private constant string FILE_NAME = "MyGC" //<= the game cache filename used in your map...

    //=========================================================
        private gamecache gc
    endglobals

...

    private function init takes nothing returns nothing
        call FlushGameCache(InitGameCache(FILE_NAME))
        set gc=InitGameCache(FILE_NAME)
    endfunction
moyack is offline   Reply With Quote
Old 07-03-2008, 04:06 AM   #6
Vexorian
Free Software Terrorist
 
Vexorian's Avatar


Technical Director
 
Join Date: Apr 2003
Posts: 14,905

Submissions (37)

Vexorian has a reputation beyond repute (1060)Vexorian has a reputation beyond repute (1060)Vexorian has a reputation beyond repute (1060)Vexorian has a reputation beyond repute (1060)Vexorian has a reputation beyond repute (1060)Vexorian has a reputation beyond repute (1060)Vexorian has a reputation beyond repute (1060)

Hero Contest #3 - 2nd Place

Default

but what if the map already uses missionkeys and keys that could collide with Table's?
__________________
Zoom (requires log in)Wc3 map optimizer 5.0
Someone should fix .wav sound in this thing.
Zoom (requires log in)JassHelper 0.A.2.A
Turns your simple code into something that is complicated enough to work.
Faster != more useful
Vexorian is offline   Reply With Quote
Old 07-03-2008, 04:21 AM   #7
cohadar
master of fugue
 
cohadar's Avatar
 
Join Date: Jun 2007
Posts: 2,453

Submissions (5)

cohadar is a jewel in the rough (246)cohadar is a jewel in the rough (246)cohadar is a jewel in the rough (246)cohadar is a jewel in the rough (246)cohadar is a jewel in the rough (246)

Default

Just a small technicality, this is not an associative array because key is always integer.
This is a simple dynamic array allocator.
__________________
Omg database crash deleted my signature, as a side effect this immensely improved wc3c.
cohadar is offline   Reply With Quote
Old 07-03-2008, 04:48 AM   #8
Vexorian
Free Software Terrorist
 
Vexorian's Avatar


Technical Director
 
Join Date: Apr 2003
Posts: 14,905

Submissions (37)

Vexorian has a reputation beyond repute (1060)Vexorian has a reputation beyond repute (1060)Vexorian has a reputation beyond repute (1060)Vexorian has a reputation beyond repute (1060)Vexorian has a reputation beyond repute (1060)Vexorian has a reputation beyond repute (1060)Vexorian has a reputation beyond repute (1060)

Hero Contest #3 - 2nd Place

Default

Quote:
this is not an associative array because key is always integer
It's relative, what I think of associative arrays is key->value, I prefer calling them associative arrays since they are not really arrays, there are no bounds for the key. You may even use negative key and things like that.
__________________
Zoom (requires log in)Wc3 map optimizer 5.0
Someone should fix .wav sound in this thing.
Zoom (requires log in)JassHelper 0.A.2.A
Turns your simple code into something that is complicated enough to work.
Faster != more useful
Vexorian is offline   Reply With Quote
Old 07-03-2008, 06:16 AM   #9
cohadar
master of fugue
 
cohadar's Avatar
 
Join Date: Jun 2007
Posts: 2,453

Submissions (5)

cohadar is a jewel in the rough (246)cohadar is a jewel in the rough (246)cohadar is a jewel in the rough (246)cohadar is a jewel in the rough (246)cohadar is a jewel in the rough (246)

Default

Quote:
Originally Posted by Wiki
From the perspective of a computer programmer, an associative array can be viewed as a generalization of an array. While a regular array maps an index to an arbitrary data type such as integers, other primitive types, or even objects, an associative array's keys can be arbitrarily typed.

So the fact you can use negative values does not make it associative because negative integer is still an integer, same type.
Your code represents a dynamic array.

Gamecache is associative array.

Technicality like I said, but misusing names is always dangerous in the long run.
__________________
Omg database crash deleted my signature, as a side effect this immensely improved wc3c.
cohadar is offline   Reply With Quote
Old 07-03-2008, 01:26 PM   #10
Vexorian
Free Software Terrorist
 
Vexorian's Avatar


Technical Director
 
Join Date: Apr 2003
Posts: 14,905

Submissions (37)

Vexorian has a reputation beyond repute (1060)Vexorian has a reputation beyond repute (1060)Vexorian has a reputation beyond repute (1060)Vexorian has a reputation beyond repute (1060)Vexorian has a reputation beyond repute (1060)Vexorian has a reputation beyond repute (1060)Vexorian has a reputation beyond repute (1060)

Hero Contest #3 - 2nd Place

Default

wikipedia is wikipedia in that paragraph it is mentioning what a programmer thinks of associative arrays, not the definition. I really think these are closer to being associative than to normal arrays, it is also a good way to avoid people from thinking it is a good idea to use them in spite of dynamic arrays.

Quote:
Originally Posted by wiki
An associative array (also associative container, map, mapping, hash, dictionary, finite map, lookup table, and in query-processing an index or index file) is an abstract data type composed of a collection of unique keys and a collection of values, where each key is associated with one value. The operation of finding the value associated with a key is called a lookup or indexing, and this is the most important operation supported by an associative array. The relationship between a key and its value is sometimes called a mapping or binding. For example, if the value associated with the key "bob" is 7, we say that our array maps "bob" to 7. Associative arrays are very closely related to the mathematical concept of a function with a finite domain. As a consequence, a common and important use of associative arrays is in memoization.

This reminded me I needed an exists() method. Updating.
__________________
Zoom (requires log in)Wc3 map optimizer 5.0
Someone should fix .wav sound in this thing.
Zoom (requires log in)JassHelper 0.A.2.A
Turns your simple code into something that is complicated enough to work.
Faster != more useful
Vexorian is offline   Reply With Quote
Old 07-03-2008, 02:05 PM   #11
moyack
Evil Emoticon
 
moyack's Avatar


Respected User
Project Leader: PoC
 
Join Date: Jan 2006
Posts: 3,266

Submissions (17)

moyack is a splendid one to behold (661)moyack is a splendid one to behold (661)moyack is a splendid one to behold (661)moyack is a splendid one to behold (661)

AI Tournament #2 - 2nd PlaceHero Contest - Second place

Send a message via MSN to moyack
Default

Quote:
Originally Posted by Vexorian
but what if the map already uses missionkeys and keys that could collide with Table's?
Still this option helps the user to set the proper name of the table if this situation happens.
moyack is offline   Reply With Quote
Old 07-03-2008, 02:13 PM   #12
Vexorian
Free Software Terrorist
 
Vexorian's Avatar


Technical Director
 
Join Date: Apr 2003
Posts: 14,905

Submissions (37)

Vexorian has a reputation beyond repute (1060)Vexorian has a reputation beyond repute (1060)Vexorian has a reputation beyond repute (1060)Vexorian has a reputation beyond repute (1060)Vexorian has a reputation beyond repute (1060)Vexorian has a reputation beyond repute (1060)Vexorian has a reputation beyond repute (1060)

Hero Contest #3 - 2nd Place

Default

Another thing is that the initializer must flush the gamecache.
__________________
Zoom (requires log in)Wc3 map optimizer 5.0
Someone should fix .wav sound in this thing.
Zoom (requires log in)JassHelper 0.A.2.A
Turns your simple code into something that is complicated enough to work.
Faster != more useful
Vexorian is offline   Reply With Quote
Old 07-03-2008, 07:24 PM   #13
the-thingy
User
 
Join Date: Feb 2006
Posts: 172

the-thingy will become famous soon enough (30)the-thingy will become famous soon enough (30)

Default

Three questions about this:

1) Must I call t.reset before t.destroy? I don't really understand how GC works :P

2) Do I declare t like local Table t = Table.create ()? If not, how do I do it?

3) Let's say I have a trigger that stores an integer, then recalls it after 5 seconds. If that trigger runs twice within 5 seconds, will I have use a different key for set t[1234567] = GetRandomInt (1, 10) everytime the trigger fires, or will it get the correct value, even if the same key is used for both instances?

Collapse JASS:
function Test takes nothing returns nothing
//See Q2 for the declaration part :P
local integer rnd = GetRandomInt (1, 10)
set t[1] = rnd
call BJDebugMsg (I2S (t[1]))
call TriggerSleepAction (5.)
call BJDebugMsg (I2S (t[1]))

endfunction

If rnd = 5 on first instance, and rnd = 7 on second instance, would my result be (- representing one second of the wait)

5
7
-
-
-
-
-
5
7

Last edited by the-thingy : 07-03-2008 at 07:24 PM.
the-thingy is offline   Reply With Quote
Old 07-03-2008, 08:11 PM   #14
Here-b-Trollz
Corkscrew Chainsaw!!!
 
Join Date: Jun 2006
Posts: 711

Here-b-Trollz has a spectacular aura about (149)

Hero Contest #2 - 2nd Place

Default

Collapse JASS:
method reset takes nothing returns nothing
    call FlushStoredMission(gc,I2S(this))
endmethod

private method onDestroy takes nothing returns nothing
    call FlushStoredMission(gc,I2S(this))
endmethod

Strange... destroy and reset would appear to do the *exact* same thing. So, if you are removing the Timer object, just destroy it, but if you want to keep the object and just empty it out, use .reset()


Table is probably most useful as a global. But you can still use it as a local. In both cases, you create a new table with Table.create(), yes.


As for question three.... I don't think GetRandomInt() works the way you want it to...
__________________
By reading this signature, you agree that I cannot be held accountable for anything that I might say or do.
Here-b-Trollz is offline   Reply With Quote
Old 07-03-2008, 08:55 PM   #15
the-thingy
User
 
Join Date: Feb 2006
Posts: 172

the-thingy will become famous soon enough (30)the-thingy will become famous soon enough (30)

Default

Quote:
As for question three.... I don't think GetRandomInt() works the way you want it to...

OK, ignoring the GetRandomInt part, what if you have an array of values, and each instance used the next value in the array (lets say, the value held in the array slot corresponds to the array's index i.e. myArray[0] = 0, myArray[1] = 1, etc)

If that was the case, would 0 and 1 be displayed if the trigger fired twice within the 5 second window?
the-thingy is offline   Reply With Quote
Reply


Thread Tools Search this Thread
Search this Thread:

Advanced Search

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

vB code is On
Smilies are On
[IMG] code is On
HTML code is Off


All times are GMT. The time now is 06:27 PM.


Donate

Affiliates
The Hubb http://bylur.com - Warcraft, StarCraft, Diablo and DotA Blog & Forums The JASS Vault Clan WEnW Campaign Creations Clan CBS GamesModding Flixreel Videos

Powered by vBulletin (Copyright ©2000 - 2014, Jelsoft Enterprises Ltd).
Hosted by www.OICcam.com
IT Support and Services provided by Executive IT Services