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

Raymond Hettinger raymond.hettinger at gmail.com
Tue Dec 11 05:59:31 CET 2012

On Dec 10, 2012, at 4:02 AM, Serhiy Storchaka <storchaka at gmail.com> wrote:

On 10.12.12 05:30, Raymond Hettinger wrote:

On Dec 9, 2012, at 10:03 PM, MRAB <python at mrabarnett.plus.com_ _<mailto:python at mrabarnett.plus.com>> wrote:

What happens when a key is deleted? Will that leave an empty slot in the entry array? Yes. See the delitem() method in the pure python implemention at http://code.activestate.com/recipes/578375 You can move the last entry on freed place. This will preserve compactness of entries array and simplify and speedup iterations and some other operations. def delitem(self, key, hashvalue=None): if hashvalue is None: hashvalue = hash(key) found, i = self.lookup(key, hashvalue) if found: index = self.indices[i] self.indices[i] = DUMMY self.size -= 1 if index != size: lasthash = self.hashlist[index] lastkey = self.keylist[index] found, j = self.lookup(lastkey, lasthash) assert found assert i != j self.indices[j] = index self.hashlist[index] = lasthash self.keylist[index] = lastkey self.valuelist[index] = self.valuelist[size] index = size self.hashlist[index] = UNUSED self.keylist[index] = UNUSED self.valuelist[index] = UNUSED else: raise KeyError(key)

That is a clever improvement. Thank you.

Using your idea (plus some tweaks) cleans-up the code a bit (simplifying iteration, simplifying the resizing logic, and eliminating the UNUSED constant). I'm updating the posted code to reflect your suggestion.

Thanks again,

Raymond

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

More information about the Python-Dev mailing list