[Python-Dev] Guarantee ordered dict literals in v3.7?
steve at pearwood.info
Tue Nov 7 01:33:03 EST 2017
On Mon, Nov 06, 2017 at 06:35:48PM +0200, Paul Sokolovsky wrote:
> For MicroPython, it would lead to quite an overhead to make
> dictionary items be in insertion order. As I mentioned, MicroPython
> optimizes for very low bookkeeping memory overhead, so lookups are
> effectively O(n), but orderedness will increase constant factor
> significantly, perhaps 5x.
Paul, it would be good if you could respond to Raymond's earlier
comments where he wrote:
I've just looked at the MicroPython dictionary implementation and
think they won't have a problem implementing O(1) compact dicts with
The likely reason for the confusion is that they are already have an
option for an "ordered array" dict variant that does a brute-force
linear search. However, their normal hashed lookup is very similar
to ours and is easily amenable to being compact and ordered.
Raymond has also volunteered to assist with this.
> Also, arguably any algorithm which would *maintain* insertion order
> over mutating operations would be more complex and/or require more
> memory that one which doesn't.
I think it would be reasonable to say that builtin dicts only maintain
insertion order for insertions, lookups, and changing the value. Any
mutation which deletes keys may arbitrarily re-order the dict.
If the user wants a stronger guarantee, then they should use
More information about the Python-Dev