Results 1 to 10 of 10

Thread: Possible to "Redim" Dictionary?

  1. #1
    thinBasic MVPs
    Join Date
    Oct 2012
    Location
    Germany
    Age
    54
    Posts
    1,544
    Rep Power
    172

    Possible to "Redim" Dictionary?

    I wonder if it's possible to "redim" the dictionary if I need more keys.

    The help warns about:

    More than NumberOfKeys keys can be stored into a dictionary but this will slow down all operations.
    So I fear to reach the limit but also to use up unnecessary memory if not 5000 keys used...

    Now I thought about some "Redim Preserve" in this manner:

    Uses "Dictionary"
    Dword pDictionary = Dictionary_Create(1000)
    ' ...
    ' now discover I have reached limit, 1000 Keys are used...
    
    ' copy dictionary to some buffer
    Dword pBuffer = Heap_Alloc( Dictionary_MemInfo(pDictionary, %HT_MemInfo_Total) )
    Memory_Copy( pDictionary, pBuffer, Heap_Size(pBuffer) )
    
    'kill the old dictionary
    Dictionary_Free(pDictionary)
    
    ' create a bigger one
    pDicitonary = Dictionary_Create(2000)
    
    ' put the data back? 
    Memory_Copy( pBuffer, pDictionary, Heap_Size(pBuffer) )
    
    would this work or corrupt the dictionary-content?

    Last edited by ReneMiner; 16-05-2013 at 13:17.
    I think there are missing some Forum-sections as beta-testing and support

  2. #2
    thinBasic author ErosOlmi's Avatar
    Join Date
    Sep 2004
    Location
    Milan - Italy
    Age
    57
    Posts
    8,793
    Rep Power
    10
    No, it is not possible to REDIM and you cannot just copy data.
    A thinBasic dictionary is like an hash table with separated linked list chaining used for overflow (when two o more keys generate the same hash value)

    http://en.wikipedia.org/wiki/Hash_table


    500px-Hash_table_5_0_1_1_1_1_0_LL.svg.png

    The reason why a hash table MUST have a fixed number of buckets is because the hash value calculated over a key MUST give the bucket where to store key/data pair.
    If I change the number of pre-defined buckets, all the hash values will change creating a mess.

    I need to develop a new function that:
    • create a new hash table with the new number of keys (buckets)
    • get all the keys from original dictionary
    • recalculate the hash
    • remap data to the new hash table/hash value
    • delete old hash table


    In the meantime you can just double or more the initial number of keys needed.
    This will not much increase your memory consumption. Every bucket (even if empty) will just consume 2 DWORD (8 bytes) so 10000 empty buckets will consume 80Kb

    Ciao
    Eros
    www.thinbasic.com | www.thinbasic.com/community/ | help.thinbasic.com
    Windows 10 Pro for Workstations 64bit - 32 GB - Intel(R) Xeon(R) W-10855M CPU @ 2.80GHz - NVIDIA Quadro RTX 3000

  3. #3
    Hi Eros

    I use a scheme, whereby a block of keys can be dumped when it falls out of scope. The hash table never has to be rebuilt. Any data links which point beyond the truncated boundary, are automatically nulled whenever they are encountered. I use this facility for disallocating local variables etc at the end of a function, while leaving globals in place.

    But the table I use is currently static (100k). though it would be possible to make it stretchable by mapping the table into a dynamic string.

    Food for thought?

    Charles
    Last edited by Charles Pegge; 17-05-2013 at 00:19.

  4. #4
    thinBasic author ErosOlmi's Avatar
    Join Date
    Sep 2004
    Location
    Milan - Italy
    Age
    57
    Posts
    8,793
    Rep Power
    10
    Hi Charles,

    I cannot use such a "static" scheme in thinBasic dictionary because every dictionary has its own life.

    Anyway, yes: a lot of food for thoughts.

    Stanley Durham has posted many interesting variations of data structures and algorithms in Power Basic forum: http://www.powerbasic.com/support/pb...splay.php?f=12 and search for OLIB or HLIB
    All is work can be foud here: http://www.deadtheorywalking.com/pow...asic_code.html

    Maybe I can "steal" some ideas

    Ciao
    Eros
    Last edited by ErosOlmi; 17-05-2013 at 14:20.
    www.thinbasic.com | www.thinbasic.com/community/ | help.thinbasic.com
    Windows 10 Pro for Workstations 64bit - 32 GB - Intel(R) Xeon(R) W-10855M CPU @ 2.80GHz - NVIDIA Quadro RTX 3000

  5. #5
    Stealing ideas is good, but sometimes it is easier to build from the base.

    The compiler entity table I use, is really a cross-breed between a regular hash table and a stack. The table boundary is recorded before entering a function, then restored on leaving the function, chopping off the local data. This technique can be applied to any level of nesting.

  6. #6
    Member
    Join Date
    Sep 2008
    Location
    Germany
    Posts
    406
    Rep Power
    56
    Stealing ideas is good.

    Is not this a punishable act? Here in my world we have own ideas.

  7. #7
    thinBasic author ErosOlmi's Avatar
    Join Date
    Sep 2004
    Location
    Milan - Italy
    Age
    57
    Posts
    8,793
    Rep Power
    10
    Quote Originally Posted by Charles Pegge View Post
    The compiler entity table I use, is really a cross-breed between a regular hash table and a stack. The table boundary is recorded before entering a function, then restored on leaving the function, chopping off the local data. This technique can be applied to any level of nesting.
    Is for sure a clever idea: a common hash table divided into slices.
    It is quite easy to manage and very fast because you do not have to de-allocate/allocate every time but just clean a slice.

    Looking at the code I use allocate local function variables (an array of hash tables, one for each function stack level, allocated/de-allocated at every function execution) ...
    ... maybe I will steal something from your suggestion.

    Thanks a lot
    Eros
    www.thinbasic.com | www.thinbasic.com/community/ | help.thinbasic.com
    Windows 10 Pro for Workstations 64bit - 32 GB - Intel(R) Xeon(R) W-10855M CPU @ 2.80GHz - NVIDIA Quadro RTX 3000

  8. #8
    thinBasic MVPs
    Join Date
    Oct 2012
    Location
    Germany
    Age
    54
    Posts
    1,544
    Rep Power
    172
    Quote Originally Posted by peter View Post
    Stealing ideas is good.

    Is not this a punishable act? Here in my world we have own ideas.

    Let's call it "involuntary sharing" then
    I think there are missing some Forum-sections as beta-testing and support

  9. #9
    Member
    Join Date
    Sep 2008
    Location
    Germany
    Posts
    406
    Rep Power
    56
    An attack?

    I am willing to quitting this forum, for sure.

  10. #10
    thinBasic MVPs
    Join Date
    Oct 2012
    Location
    Germany
    Age
    54
    Posts
    1,544
    Rep Power
    172
    No attack! we're just doing it for fun - wir machen doch nur Spaß
    I think there are missing some Forum-sections as beta-testing and support

Similar Threads

  1. Forum: added "Auto Youtube Link-Converter" plugin
    By ErosOlmi in forum Web and Forum
    Replies: 0
    Last Post: 07-05-2011, 12:47
  2. The original "Python programming in OpenGL" by Stan Blank
    By Petr Schreiber in forum ThinBASIC programming in OpenGL/TBGL
    Replies: 0
    Last Post: 25-02-2010, 17:48
  3. Replies: 17
    Last Post: 21-02-2010, 07:45
  4. Uses "File", "Crypto" ... ???
    By marcuslee in forum thinBasic General
    Replies: 3
    Last Post: 01-12-2009, 19:38

Members who have read this thread: 0

There are no members to list at the moment.

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •