[Python-Dev] More compact dictionaries with faster iteration
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
> 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.
-------------- next part --------------
An HTML attachment was scrubbed...
More information about the Python-Dev