471,339 Members | 1,253 Online
Bytes | Software Development & Data Engineering Community
Post +

Home Posts Topics Members FAQ

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

memory efficient set/dictionary

What is the best to go about using a large set (or dictionary) that
doesn't fit into main memory? What is Python's (2.5 let's say)
overhead for storing int in the set, and how much for storing int ->
int mapping in the dict?

Please recommend a module that allows persistent set/dict storage +
fast query that best fits my problem, and as lightweight as possible.
For queries, the hit ratio is about 10%. Fast updates would be nice,
but i can rewrite the algo so that the data is static, so update speed
is not critical.

Or am i better off not using Python here? Cheers.

Jun 10 '07 #1
6 5592
On Sun, 10 Jun 2007 07:27:56 -0700, koara wrote:
What is the best to go about using a large set (or dictionary) that
doesn't fit into main memory? What is Python's (2.5 let's say)
overhead for storing int in the set, and how much for storing int ->
int mapping in the dict?
How do you know it won't fit in main memory if you don't know the
overhead? A guess? You've tried it and your computer crashed?

Please recommend a module that allows persistent set/dict storage +
fast query that best fits my problem,
Usually I love guessing what people's problems are before making a
recommendation, but I'm feeling whimsical so I think I'll ask first.

What is the problem you are trying to solve? How many keys do you have?
Can you group them in some way, e.g. alphabetically? Do you need to search
on random keys, or can you queue them and do them in the order of your
choice?

and as lightweight as possible.
For queries, the hit ratio is about 10%. Fast updates would be nice,
but i can rewrite the algo so that the data is static, so update speed
is not critical.

Or am i better off not using Python here? Cheers.

--
Steven.

Jun 10 '07 #2
Hello Steven,

On Jun 10, 5:29 pm, Steven D'Aprano
<s...@REMOVE.THIS.cybersource.com.auwrote:
...
How do you know it won't fit in main memory if you don't know the
overhead? A guess? You've tried it and your computer crashed?
exactly
Please recommend a module that allows persistent set/dict storage +
fast query that best fits my problem,

Usually I love guessing what people's problems are before making a
recommendation, but I'm feeling whimsical so I think I'll ask first.

What is the problem you are trying to solve? How many keys do you have?
Corpus processing. There are in the order of billions to tens of
billions keys (64bit integers).
Can you group them in some way, e.g. alphabetically? Do you need to search
on random keys, or can you queue them and do them in the order of your
choice?

Yes, keys in sets and dictionaries can be grouped in any way, order
doesn't matter. Not sure what you mean.
Yes, i need fast random access (at least i do without having to
rethink and rewrite everything, which is what i'd like to avoid with
the help of this thread :-)

Thanks for the reply!
Jun 10 '07 #3
Please recommend a module that allows persistent set/dict storage +
fast query that best fits my problem,
What is the problem you are trying to solve? How many keys do you have?

Corpus processing. There are in the order of billions to tens of
billions keys (64bit integers).
I would recommend you to use a database since it meets your
requirements (off-memory, fast, persistent). The bsdddb module
(berkeley db) even gives you a dictionary like interface.
http://www.python.org/doc/lib/module-bsddb.html

regards,
Rafa
Jun 10 '07 #4
Rafael Darder Calvo wrote:
Please recommend a module that allows persistent set/dict storage +
fast query that best fits my problem,

What is the problem you are trying to solve? How many keys do you have?

Corpus processing. There are in the order of billions to tens of
billions keys (64bit integers).
I would recommend you to use a database since it meets your
requirements (off-memory, fast, persistent). The bsdddb module
(berkeley db) even gives you a dictionary like interface.
http://www.python.org/doc/lib/module-bsddb.html
Standard SQL databases can work for this, but generally your
recommendation of using bsddb works very well for int -int mappings.
In particular, I would suggest using a btree, if only because I have had
troubles in the past with colliding keys in the bsddb.hash (and recno is
just a flat file, and will attempt to create a file i*(record size) to
write to record number i .

As an alternative, there are many search-engine known methods for
mapping int -[int, int, ...], which can be implemented as int -int,
where the second int is a pointer to an address on disk. Looking into a
few of the open source search implementations may be worthwhile.

- Josiah
Jun 11 '07 #5
I would recommend you to use a database since it meets your
requirements (off-memory, fast, persistent). The bsdddb module
(berkeley db) even gives you a dictionary like interface.
http://www.python.org/doc/lib/module-bsddb.html

Standard SQL databases can work for this, but generally your
recommendation of using bsddb works very well for int -int mappings.
In particular, I would suggest using a btree, if only because I have had
troubles in the past with colliding keys in the bsddb.hash (and recno is
just a flat file, and will attempt to create a file i*(record size) to
write to record number i .

As an alternative, there are many search-engine known methods for
mapping int -[int, int, ...], which can be implemented as int -int,
where the second int is a pointer to an address on disk. Looking into a
few of the open source search implementations may be worthwhile.
Thanks guys! I will look into bsddb, hopefully this doesn't keep all
keys in memory, i couldn't find answer to that during my (very brief)
look into the documentation.

And how about the extra memory used for set/dict'ing of integers? Is
there a simple answer?

Jun 11 '07 #6
koara wrote:
>>I would recommend you to use a database since it meets your
requirements (off-memory, fast, persistent). The bsdddb module
(berkeley db) even gives you a dictionary like interface.
http://www.python.org/doc/lib/module-bsddb.html
Standard SQL databases can work for this, but generally your
recommendation of using bsddb works very well for int -int mappings.
In particular, I would suggest using a btree, if only because I have had
troubles in the past with colliding keys in the bsddb.hash (and recno is
just a flat file, and will attempt to create a file i*(record size) to
write to record number i .

As an alternative, there are many search-engine known methods for
mapping int -[int, int, ...], which can be implemented as int -int,
where the second int is a pointer to an address on disk. Looking into a
few of the open source search implementations may be worthwhile.

Thanks guys! I will look into bsddb, hopefully this doesn't keep all
keys in memory, i couldn't find answer to that during my (very brief)
look into the documentation.
No, bsddb does not keep all data in memory.

And how about the extra memory used for set/dict'ing of integers? Is
there a simple answer?
A non-long integer for a 32 bit Python uses 12 bytes. A non-long
integer for a 64 bit Python uses 24 bytes.

Each entry in a dictionary for a 32 bit Python uses 12 bytes; 4 for the
hash, 4 for the key pointer, 4 for the value pointer. Double that to 24
bytes each in the 64 bit Python (I don't know if the hash actually has
its range increased, but if one doesn't double the size of the pointers,
then you have alignment issues that can slow down dictionary access).

Sets only have the hash and key pointers, so only use 8/16 bytes per entry.
- Josiah
Jun 11 '07 #7

This discussion thread is closed

Replies have been disabled for this discussion.

Similar topics

8 posts views Thread by Benjamin Scott | last post: by
12 posts views Thread by Anon | last post: by
4 posts views Thread by Thomas Rast | last post: by
6 posts views Thread by Ganesan selvaraj | last post: by
3 posts views Thread by RubenDV | last post: by
7 posts views Thread by Jim | last post: by
1 post views Thread by buu | last post: by

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.