On Fri, Jul 10, 2020 at 1:28 PM Ronald Oussoren <ronaldoussoren@mac.com> wrote:
On 10 Jul 2020, at 14:08, Stestagg <stestagg@gmail.com> wrote:
Adding indexing to views adds another requirement to the dict implementation:
Yes, that's the proposed change
indexing for sequences at least suggests that access is O(1).
That makes it impossible to use, as an example, a linked list to preserve
insertion order.
The docs for the Sequence abc explicitly talk about situations where index is not O(1), and say that while not ideal, this is valid (mentioning linked-lists by name).
Its a quality of implementation issue. A sequence where item access is not O(1) is not invalid, but surprising and likely to cause performance problems because users tend to expect that item access is O(1).
Yes, as the docs say. But this has been raised a few times in the thread, and it orthogonal to the 'we may want to make arbitrary changes to how dicts work in the future' debate.
The current existing `dict` implementation does not support O(1) index lookup from a view, (as discussed previously), so a change to linked-lists would not change this runtime O characteristic.
The current views don’t support indexing at all, that’s the whole point of this thread.
The intent of my statement was: The current implementation of dict does not allow any reasonable implementation of dict_keys/dict_values/dict_items with O(1) index behaviour. I.e. the performance scalability of any future changes to the dict_* types that add direct indexing is *not* likely to be adversely affected by changes to the implementation of dict(), unless somehow iteration in O(n) time becomes impossible.