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
ordering.
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.
See:
https://github.com/micropython/micropython/blob/77a48e8cd493c0b0e0ca2d2ad58a110a23c6a232/py/map.c#L139
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
OrderedDict.
--
Steve
_______________________________________________
Python-Dev mailing list
Python-Dev@python.org
https://mail.python.org/mailman/listinfo/python-dev
Unsubscribe:
https://mail.python.org/mailman/options/python-dev/archive%40mail-archive.com
