[Python-Dev] More compact dictionaries with faster iteration (original) (raw)

Raymond Hettinger raymond.hettinger at gmail.com
Tue Dec 11 00:39:22 CET 2012

On Dec 10, 2012, at 4:06 AM, Mark Shannon <mark at hotpy.org> wrote:

Instead, the 24-byte entries should be stored in a dense table referenced by a sparse table of indices. What minimum size and resizing factor do you propose for the entries array?

There are many ways to do this. I don't know which is best. The proof-of-concept code uses the existing list resizing logic. Another approach is to pre-allocate the two-thirds maximum (This is simple and fast but gives the smallest space savings.) A hybrid approach is to allocate in two steps (1/3 and then 2/3 if needed).

Since hash tables aren't a new problem, there may already be published research on the best way to handle the entries array.

Raymond

-------------- next part -------------- An HTML attachment was scrubbed... URL: <http://mail.python.org/pipermail/python-dev/attachments/20121210/7787840d/attachment.html>

More information about the Python-Dev mailing list