dcsimg
Results 1 to 11 of 11

Thread: [RESOLVED] Efficient "Key-Value" operations?

  1. #1

    Thread Starter
    Frenzied Member
    Join Date
    Sep 2012
    Posts
    1,656

    Resolved [RESOLVED] Efficient "Key-Value" operations?

    I need to implement a storage structure similar to the JavaScript Key-Value array, for example:

    var arr = [];

    arr["apple"] = 111;
    arr["pear"] = 222;
    arr["orange"] = 333;

    I know that VB.Colletion can do this. I'd like to know if there is a more efficient way to implement the "Key-Value" operations? Could we use VB.Arrays to implement efficient "Key-Value" storage structure and operations?
    Last edited by dreammanor; May 13th, 2019 at 04:42 AM.

  2. #2
    PowerPoster Arnoutdv's Avatar
    Join Date
    Oct 2013
    Posts
    3,605

    Re: Efficient "Key-Value" operations?

    Collections, Dictionaries and Hash lists come to mind.
    You are using RC5 so why come up with another method??

  3. #3

    Thread Starter
    Frenzied Member
    Join Date
    Sep 2012
    Posts
    1,656

    Re: Efficient "Key-Value" operations?

    Quote Originally Posted by Arnoutdv View Post
    Collections, Dictionaries and Hash lists come to mind.
    You are using RC5 so why come up with another method??
    Hi Arnoutdv, thank you for your reply. I'd like to know if there is a faster Key-Value retrieval method than RC5.Collection.

    I know that RC5.Collection seems to be the fastest of all collection classes. But I want to know if there are other storage objects dedicated to Key-Value, which is more efficient.

  4. #4
    PowerPoster Arnoutdv's Avatar
    Join Date
    Oct 2013
    Posts
    3,605

    Re: Efficient "Key-Value" operations?

    I remember a thread in which some test were done already.
    Comparing the VBA.Collection, Scripting.Dictionary, RC5.cCollection, RC5.cSortedDictonary and some other hash implementations.
    I believe the trick also submitted a solution.

    Simple and fast, lightweight HashList-Class (no APIs)
    Last edited by Arnoutdv; May 13th, 2019 at 06:28 AM.

  5. #5
    Frenzied Member wqweto's Avatar
    Join Date
    May 2011
    Posts
    1,579

    Re: Efficient "Key-Value" operations?

    For hash-based containers there is something called perfect hash function. The idea is to fill up the container with all values and then find a hash function that maps key to integer index w/o any collisions which makes the container fast (by reducing the slowness of collision resolution).

    Try testing RC5.Collection against .Net Dictionary<string, object> or HashSet or whatever container fits your needs. Probably Olaf did similar benchmarks and can share a link or two.

    cheers,
    </wqw>

  6. #6

    Thread Starter
    Frenzied Member
    Join Date
    Sep 2012
    Posts
    1,656

    Re: Efficient "Key-Value" operations?

    Quote Originally Posted by Arnoutdv View Post
    I remember a thread in which some test were done already.
    Comparing the VBA.Collection, Scripting.Dictionary, RC5.cCollection, RC5.cSortedDictonary and some other hash implementations.
    I believe the trick also submitted a solution.

    Simple and fast, lightweight HashList-Class (no APIs)
    Thank you, @Arnoutdv.

    I rewrote the test program and compared TrickHashTable, Scripting.Dictionary, RC5.cCollection, RC5.cSortedDictonary, OlafHashList, OlafHashD(OlafHashDict). The performance of RC5.cSortedDictonary and OlafHashD (OlafHashDict) is the best. Some test results are as follows:

    Add items(Binary compare):
    (1) Trick HashTable: 0.595s (add 100000) 1.627s (add to 200000) 2.479s (add to 300000)
    (2) VB.Dictionary: 0.717s (add 100000) 1.530s (add to 200000) 3.151s (add to 300000)
    (3) RC5.Collection: 0.195s (add 100000) 0.241s (add to 200000) 0.242s (add to 300000)
    (4) RC5.SortDict: 0.180s (add 100000) 0.229s (add to 200000) 0.227s (add to 300000)
    (5) Olaf HashList: 0.271s (add 100000) 0.384s (add to 200000) 0.486s (add to 300000)
    (6) Olaf HashD: 0.172s (add 100000) 0.204s (add to 200000) 0.239s (add to 300000)

    -------------------------------------------------------------------------------------------
    Add items(Text compare):
    (1) Trick HashTable: 0.601s (add 100000) 1.566s (add to 200000) 2.474s (add to 300000)
    (2) VB.Dictionary: 1.349s (add 100000) 4.077s (add to 200000) 6.944s (add to 300000)
    (3) RC5.Collection: 0.201s (add 100000) 0.250s (add to 200000) 0.253s (add to 300000)
    (4) RC5.SortDict: 0.192s (add 100000) 0.238s (add to 200000) 0.238s (add to 300000)
    (5) Olaf HashList: 0.273s (add 100000) 0.382s (add to 200000) 0.488s (add to 300000)
    (6) Olaf HashD: 0.206s (add 100000) 0.317s (add to 200000) 0.412s (add to 300000)

    -----------------------------------------------------------------------------------------------------------------
    I also tested AccessAll and ForEach, and the test data was too much, so I didn't post the results.
    Attached Images Attached Images  
    Attached Files Attached Files
    Last edited by dreammanor; May 14th, 2019 at 01:19 AM.

  7. #7

    Thread Starter
    Frenzied Member
    Join Date
    Sep 2012
    Posts
    1,656

    Re: Efficient "Key-Value" operations?

    Quote Originally Posted by wqweto View Post
    For hash-based containers there is something called perfect hash function. The idea is to fill up the container with all values and then find a hash function that maps key to integer index w/o any collisions which makes the container fast (by reducing the slowness of collision resolution).

    Try testing RC5.Collection against .Net Dictionary<string, object> or HashSet or whatever container fits your needs. Probably Olaf did similar benchmarks and can share a link or two.

    cheers,
    </wqw>
    Thank you, wqweto, could you write an example based on my test program? I'll test and compare your method.

  8. #8
    PowerPoster Arnoutdv's Avatar
    Join Date
    Oct 2013
    Posts
    3,605

    Re: Efficient "Key-Value" operations?

    A perfect hash function can be constructed that maps each of the keys to a distinct integer, with no collisions. These functions only work with the specific set of keys for which they were constructed. Passing an unknown key will result a false match or even crash.
    Minimal Perfect Hash Functions

  9. #9

    Thread Starter
    Frenzied Member
    Join Date
    Sep 2012
    Posts
    1,656

    Re: Efficient "Key-Value" operations?

    Quote Originally Posted by Arnoutdv View Post
    Hi Arnoutdv, thank you for the link provided. Mathematical algorithms always make me a headache, maybe The trick is suitable for dealing with such problems.

  10. #10
    PowerPoster Arnoutdv's Avatar
    Join Date
    Oct 2013
    Posts
    3,605

    Re: Efficient "Key-Value" operations?

    The import thing is that the perfect hash only works for fixed and known set of keys. So it has limited use in real life scenarios

  11. #11

    Thread Starter
    Frenzied Member
    Join Date
    Sep 2012
    Posts
    1,656

    Re: Efficient "Key-Value" operations?

    Understand. RC5.cSortedDictonary and Olaf's HashD (HashDict) should be able to meet my needs. Thank you.

Posting Permissions

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



Featured


Click Here to Expand Forum to Full Width