5 ms·
Wait, if it is held in a separate dense array, is removal of a key from a dictionary O(N)?
by ummonk 7y ago
Wait, if it is held in a separate dense array, is removal of a key from a dictionary O(N)?
- Rapzid 7y agoYou can use memcpy to remove items from the middle of a memory segment. It's probably not a single memory segment either; I imagine it works more like a Golang slice.
- ummonk 7y agoMemcpy is certainly O(N). But yeah, if they implement it with multiple slices (e.g. a B tree) it could be fast.
- Rapzid 7y agoHrm, I'm pretty sure I meant memmove: https://golang.org/src/runtime/slice.go https://golang.org/src/runtime/slice.go EDIT: I could have sworn they were shifting entire pages around without using a cycle per byte but I can't find any reference to that now haha.
- jameshart 7y agoGreat, you recovered the memory. But now you have to update all the pointers to the array in the hashmap....
- dilap 7y agoYou don't actually remove the entry, you just mark it as deleted. Eventually if too many things are deleted you repack the array. Still amortized O(1). (No different than a hash table in general, which will need to recopy the underlying array when it grows.)
- Rapzid 7y agoI _think_ this may be the implementation: https://github.com/python/cpython/blob/60ac6ed5579f6666130fc264d3b748ee9575e3aa/Objects/odictobject.c https://github.com/python/cpython/blob/60ac6ed5579f6666130fc... There are copious notes in there about the implementation and it indicates linked lists are used. EDIT: Blargh, it's here: https://github.com/python/cpython/blob/60ac6ed5579f6666130fc264d3b748ee9575e3aa/Objects/odictobject.c https://github.com/python/cpython/blob/60ac6ed5579f6666130fc... . That file references this blog post which indicates they may be flagging and repacking as dilap commented: https://morepypy.blogspot.com/2015/01/faster-more-memory-efficient-and-more.html https://morepypy.blogspot.com/2015/01/faster-more-memory-eff...