Currently, ordered dicts are implemented with the help of a linked list. A while ago, ordinary dicts became ordered.
I would like to give re-implementing ordered dicts without linked lists a try.
However, I want to avoid duplicating work. Could you please point me to some existing efforts, if any? I tried to search myself, but didn’t find much. Thanks!
P.S. The main algorithmic difficulty I see is supporting ordered-dict’s move-to-front functionality. The rest seems pretty straightforward, if a bit tedious. What’s your take?
I see that this issue was from quite a while ago, before the dicts being ordered was well established.
I don’t really understand the problem they are bringing up with amortised vs worst case performance: almost everything about dicts only makes amortised claims. Or worse, collision handling only makes claims for the ‘average’ case of input.
Btw, if you want to see it, I can make move_to_end take worst case O(1) time (without linked lists). With a similar technique that also could be used to make inserts take O(1) worst case time. Basically, ‘lazy’ rebuilding, instead of compacing everything at once.
But I am not sure the extra implementation complexity would be worth it.
This is an idea similar to incremental garbage collection driven in small steps by allocations. It also thrashes less cache per dictionary operation. If it can be implemented cleanly then I’d look forward to this (as a user).