Actually, I think the reverse traversal case is the worst case because: it's not possible to use negative subscripts with islice (because that would require making a full copy).

This doesn't work:
>>> islice(dict.keys(), -1, -5)

Reverse traversal did work in Python 2 but was foregone when making .keys() a view in Python 3 in order to avoid lulling users into making usually unnecessary copies.

If it's not possible to support (dict_view||dict_sequence_view).__getitem__(slice_or_index) without causing a performance regression in dict, which directly affects core performance, I'm not sure that this use case is worth it either. There's always the linked list odict.

There are probably tests somewhere that show what happens when we delete a dict key and value? I'm still somewhat mystified by that, tooL

On Fri, Jul 31, 2020 at 8:44 PM Guido van Rossum <guido@python.org> wrote:
This is not great news. A solution could be to make dict.ordered() force compaction -- if there are no deleted keys this would be a no-op. We'd have to be able to tell in constant time whether this is the case. But yeah, this would be a dangerous thing in the hands of folks below wizard level. Another solution could be to make dict.ordered() fail if there are deleted keys. But that's not a great experience either.

All in all I retract this idea.

On Fri, Jul 31, 2020 at 5:31 PM Stestagg <stestagg@gmail.com> wrote:
On Sat, 1 Aug 2020 at 00:32, Guido van Rossum <guido@python.org> wrote:
If true this would be a huge argument against adding indexing and slicing (other than the special case starting with 0). However, I don't think it's true. The dict implementation (again, starting in 3.6) actually stores the list of keys in a compact array, in the insertion order. The hash table stores indices into this array. Moreover, in order to implement the ordered property, you pretty much have to do this (since the hash table *definitely* isn't going to be ordered :-). So indexing and slicing into this array would seem to be possible, unless I am missing something. I'm CC"ing Inada Naoki because it's his code -- maybe he can enlighten us.

I’m not Inada Naoki :). So happy to be corrected, but I looked into this quite closely. 

The dict keys is compact only *until* you delete an item, at which point, a hole is left in the array, which defeats direct lookups (either by indexing or via a view).  Order preservation is still kept as code that iterates over dictionaries knows to just skip the holes. 

I’m unsure when/if compaction is called however. So there may be a technique for forcing the keys to be compacted again.  This would cause very unpredictable performance in the case of large dictionaries (a main use-case here)

Steve


_______________________________________________
Python-ideas mailing list -- python-ideas@python.org
To unsubscribe send an email to python-ideas-leave@python.org
https://mail.python.org/mailman3/lists/python-ideas.python.org/
Message archived at https://mail.python.org/archives/list/python-ideas@python.org/message/CWQMLXNOEPCXUXPQSTUOI5VUF4V7R36B/
Code of Conduct: http://python.org/psf/codeofconduct/


--
--Guido van Rossum (python.org/~guido)
_______________________________________________
Python-ideas mailing list -- python-ideas@python.org
To unsubscribe send an email to python-ideas-leave@python.org
https://mail.python.org/mailman3/lists/python-ideas.python.org/
Message archived at https://mail.python.org/archives/list/python-ideas@python.org/message/JY2ZJTOE4VHC36VWTMZY4QM7U2NUCYT5/
Code of Conduct: http://python.org/psf/codeofconduct/