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

Serhiy Storchaka storchaka at gmail.com
Mon Dec 10 10:02:26 CET 2012

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)

More information about the Python-Dev mailing list