Python 2.7 alpha 1
mail.python.org
mail.python.org
I wonder how this will turn out, long-term? Seems like a good idea on the face of it.
Hmm... shouldn't that be `O(log n)` or something like that? Or do they really use cuckoo (or similar) hashing with O(1) hash access?
def __delitem__(self, key):
'od.__delitem__(y) <==> del od[y]'
# Deleting an existing item uses self.__map to find the link which is
# then removed by updating the links in the predecessor and successor nodes.
dict.__delitem__(self, key)
link = self.__map.pop(key)
link.prev.next = link.next
link.next.prev = link.prevThat's exactly the part I was referring to. If deleting the key from an OrderedDict is O(1), then all these operations have to be O(1):
- dictionary deletion
- _map.pop (which is another dictionary deletion)
- linked list removal (obvious)
I'm not saying they aren't - just wanted to make sure that's the case. I didn't know whether to interpret the sentence from "what's new" as - "we use a map to know the elements, so the only operation on a linked list is unlink, which is O(1)", or "the whole lookup+delete is O(1)".
So yes, the whole operation is O(1) on average.