4 ms·

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 tak

by alxv 17y ago

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

viraptor 17y ago
> 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)".
- alxv 17y ago
  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. So yes, the whole operation is O(1) on average.
- andrewcooke 17y ago
  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)

by alxv 17y ago

viraptor 17y ago

> 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)".

alxv 17y ago
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. So yes, the whole operation is O(1) on average.
andrewcooke 17y ago
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)