473,320 Members | 2,097 Online
Bytes | Software Development & Data Engineering Community
Post Job

Home Posts Topics Members FAQ

Join Bytes to post your question to a community of 473,320 software developers and data experts.

Reducing memory overhead for dictionaries by removing precomputed hash

Forgive me if this has already been discussed, but it seems to me that
one could reduce the memory usage of dictionaries by 2/3 by removing
the precomputed hash in each bucket.

Since Dictionaries only allow immutable objects as keys, one could move
the precomputed hash into the keys.

* Strings are probably the most popular keys for dictionaries and they
already cache the hash (hmm that almost rhymes).
* Numbers are trivial to hash.
* For Tuples one could add a member to cache the hash.

So why store the hash? I imagine it makes rebuilding the dictionary a
bit quicker, since I guess you can avoid some comparisions since you
know there are no duplicates. haven't looked at the code to see if it
does that tho.

and collision chains are possibly a bit quicker to traverse, tho I
think python uses a mask instead of a mod by prime, so hash keys with
the same low bits will collide, so collisions might be more common, but
that's possibly fixable by using a congruential hash, but that's all
black magic to me.

-Kirat

Apr 18 '06 #1
0 905

This thread has been closed and replies have been disabled. Please start a new discussion.

Similar topics

4
by: Thomas Rast | last post by:
Hello everyone My scenario is somewhat involved, so if you're in a hurry, here's an abstract: I have a daemon that needs about 80MB of RAM to build its internal data structures, but can pack...
1
by: DJTB | last post by:
zodb-dev@zope.org] Hi, I'm having problems storing large amounts of objects in a ZODB. After committing changes to the database, elements are not cleared from memory. Since the number of...
16
by: Rich S | last post by:
Or just loosing it? I have a small c++ app which generates millions combinations of bitset class objects and adds them to a STL map. (on a side thanks to all who responded to my earlier...
4
by: Evangelista Sami | last post by:
hello all i am implementing an application in which a large number of (char *) is stored into a hash table structure. As there may be collisions, each (char *) inserted into my hash table is...
2
by: Martin | last post by:
I already know some techniques for writing small footprint software, but now I need to really squeeze the software I'm writing into a small space (embedded software). Is there a good web page...
10
by: Segfahlt | last post by:
I have a fairly simple C# program that just needs to open up a fixed width file, convert each record to tab delimited and append a field to the end of it. The input files are between 300M and...
4
by: xarnaudx | last post by:
hi, i've just a simple question: what are the time complexities of inserting / removing / checking if an element is present in 1) a list and 2) a dictionary? does anybody know? thanks
3
by: Xiaoning He | last post by:
hi currently i'm using a crawler called larbin to get some pages, it hashes each url to an integer. This is not a good method comparing to md5, however it's enough for me. Currently i set the hash...
14
by: cnb | last post by:
Are dictionaries the same as hashtables?
0
by: ryjfgjl | last post by:
ExcelToDatabase: batch import excel into database automatically...
0
isladogs
by: isladogs | last post by:
The next Access Europe meeting will be on Wednesday 6 Mar 2024 starting at 18:00 UK time (6PM UTC) and finishing at about 19:15 (7.15PM). In this month's session, we are pleased to welcome back...
1
isladogs
by: isladogs | last post by:
The next Access Europe meeting will be on Wednesday 6 Mar 2024 starting at 18:00 UK time (6PM UTC) and finishing at about 19:15 (7.15PM). In this month's session, we are pleased to welcome back...
0
by: jfyes | last post by:
As a hardware engineer, after seeing that CEIWEI recently released a new tool for Modbus RTU Over TCP/UDP filtering and monitoring, I actively went to its official website to take a look. It turned...
0
by: ArrayDB | last post by:
The error message I've encountered is; ERROR:root:Error generating model response: exception: access violation writing 0x0000000000005140, which seems to be indicative of an access violation...
1
by: PapaRatzi | last post by:
Hello, I am teaching myself MS Access forms design and Visual Basic. I've created a table to capture a list of Top 30 singles and forms to capture new entries. The final step is a form (unbound)...
1
by: Shællîpôpï 09 | last post by:
If u are using a keypad phone, how do u turn on JavaScript, to access features like WhatsApp, Facebook, Instagram....
0
by: Faith0G | last post by:
I am starting a new it consulting business and it's been a while since I setup a new website. Is wordpress still the best web based software for hosting a 5 page website? The webpages will be...
0
isladogs
by: isladogs | last post by:
The next Access Europe User Group meeting will be on Wednesday 3 Apr 2024 starting at 18:00 UK time (6PM UTC+1) and finishing by 19:30 (7.30PM). In this session, we are pleased to welcome former...

By using Bytes.com and it's services, you agree to our Privacy Policy and Terms of Use.

To disable or enable advertisements and analytics tracking please visit the manage ads & tracking page.