Interesting--the Python-Dev folks are moving more and more of 3.x into the 2.x series (2.7 corresponds to 3.1). They're pretty effectively shortening the gap that people will eventually have to jump when going from 2 to 3.
I wonder how this will turn out, long-term? Seems like a good idea on the face of it.
> How does the OrderedDict work? It maintains a doubly-linked list of keys, appending new keys to the list as they’re inserted. A secondary dictionary maps keys to their corresponding list node, so deletion doesn’t have to traverse the entire linked list and therefore remains O(1).
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?
I am not sure why you think deletion has to be O(log n), but can assure you that it is O(1). Of course, this is assuming you consider a hash table lookup to take constant time. If that can help, this is implementation of deletion for the OrderedDict collection:
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.prev
> this is assuming you consider a hash table lookup to take constant time
That'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)".
The dictionary implementation of Python is a hash table using open addressing with quadratic probing. Deletion is essentially a lookup to replace the key with a tombstone. And, the table is never resized after a deletion.
i think the confusion here is whether we're talking about worst case or average times. cuckoo hashing addresses worst case times, while the traditional O(1) for access to a probed table is an average time (worst case is going to be O(n) i guess). that's not as bad as it sounds because provided the load factor is low enough the probability of the worst case goes down "fast enough" for the average to be bounded. i think :o)
No, hashing is part of the O in O(1). For pathological cases O(n) could be faster than O(1), but fast hashing is fundamental to Python performance, so I expect it to be fast.
I wonder how this will turn out, long-term? Seems like a good idea on the face of it.