Raymond Hettinger added the comment: Just for the record, here is the draft of the post I was going to make on python-dev but didn't prove to be necessary.
--------------------------------------------- I think would be a mistake to replace the implementation of collections.OrderedDict() with the builtin compact-and-ordered dict. They serve different use cases and deserve different implementations that best serve those use cases. When PEP 372 for the OrderedDict was accepted a decade ago, Armin and I looked at various implementation strategies. It came down to a contest between keeping the order in an arraylike structure (like a Python list) or using a doubly-linked list. The latter was chosen because it had superior algorithmic performance for workloads that involved a mix of insertions and deletions. In particular, it offered a constant time guarantee for popping from any location or doing a move_to_front or move_to_last operation (which was helpful in implementing an LRU cache for example). It supported arbitrary deletions and insertions without leaving holes that require periodic compaction. When Eric Snow implemented OrderedDict in C for Python 3.5, he kept the doubly-linked list design to maintain those benefits. In contrast, when I proposed the design for the current Python built-in dictionary, it had a different goal, namely compact storage. It is very good at meeting that goal. However, the ordering of keys was a side-effect and somewhat of an afterthought rather than being something it was designed to handle well (which may be one of the reasons that Guido did not guarantee the ordering behavior). At last year’s sprints, there was a deliberate decision to not replace the OrderedDict with the built-in dict. I believe that decision was a good one and should be maintained. It will allow us to have a separation of concerns and continue to improve the OrderedDict in a way that best supports applications that do interesting things with ordering (such as Antoine’s idea to use an OrderedDict as a circular queue). I fully support efforts to improve the code for collections.OrderedDict() but think it is essential for it to evolve separately from the built-in dict and for its implementation strategy to be primarily focused efficiently maintaining order (its raison d'etre). ---------- _______________________________________ Python tracker <rep...@bugs.python.org> <https://bugs.python.org/issue31265> _______________________________________ _______________________________________________ Python-bugs-list mailing list Unsubscribe: https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
