> On Dec 15, 2019, at 6:48 PM, Larry Hastings <la...@hastings.org> wrote:
>
> As of 3.7, dict objects are guaranteed to maintain insertion order. But set
> objects make no such guarantee, and AFAIK in practice they don't maintain
> insertion order either. Should they?
I don't think they should.
Several thoughts:
* The corresponding mathematical concept is unordered and it would be weird to
impose such as order.
* You can already get membership testing while retaining insertion ordering by
running dict.fromkeys(seq).
* Set operations have optimizations that preclude giving a guaranteed order
(for example, set intersection loops over the smaller of the two input sets).
* To implement ordering, set objects would have to give-up their current
membership testing optimization that exploits cache locality in lookups (it
looks at several consecutive hashes at a time before jumping to the next random
position in the table).
* The ordering we have for dicts uses a hash table that indexes into a
sequence. That works reasonably well for typical dict operations but is
unsuitable for set operations where some common use cases make interspersed
additions and deletions (that is why the LRU cache still uses a cheaply updated
doubly-linked list rather that deleting and reinserting dict entries).
* This idea has been discussed a couple times before and we've decided not to
go down this path. I should document prominently because it is inevitable that
it will be suggested periodically because it is such an obvious thing to
consider.
Raymond
_______________________________________________
Python-Dev mailing list -- python-dev@python.org
To unsubscribe send an email to python-dev-le...@python.org
https://mail.python.org/mailman3/lists/python-dev.python.org/
Message archived at
https://mail.python.org/archives/list/python-dev@python.org/message/6CO2CZS4CPP6MSJKRZXXQYFLY5T3UVDU/
Code of Conduct: http://python.org/psf/codeofconduct/
