On Dec 10, 2012, at 4:02 AM, Serhiy Storchaka <storch...@gmail.com> wrote:
> On 10.12.12 05:30, Raymond Hettinger wrote: >> On Dec 9, 2012, at 10:03 PM, MRAB <pyt...@mrabarnett.plus.com >> <mailto:pyt...@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
_______________________________________________ Python-Dev mailing list Python-Dev@python.org http://mail.python.org/mailman/listinfo/python-dev Unsubscribe: http://mail.python.org/mailman/options/python-dev/archive%40mail-archive.com
