[Python-Dev] More compact dictionaries with faster iteration

[Raymond Hettinger]

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>