Raymond Hettinger
raymond.hettinger at gmail.com
Tue Dec 11 05:59:31 CET 2012Previous message:
[Python-Dev] More compact dictionaries with faster iteration
Next message:
[Python-Dev] More compact dictionaries with faster iteration
Messages sorted by:
———
On Dec 10, 2012, at 4:02 AM, Serhiy Storchaka <
> wrote: > On 10.12.12 05:30, Raymond Hettinger wrote: >> On Dec 9, 2012, at 10:03 PM, MRAB <
>> <mailto:
>> 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
>
———
Previous message:
[Python-Dev] More compact dictionaries with faster iteration
Next message:
[Python-Dev] More compact dictionaries with faster iteration
Messages sorted by:
———