I have a use case which relates to this request: iterating over a dict starting from a given key. I would like to achieve this without having to pay the full O(n) cost if I'm going to be iterating over only a few items. My understanding is that this should be achievable without needing to iterate through the entire dict, since the dict's internal key lookup points to a particular index of dk_entries anyway.
My sample use case at a high level is when the dict stores values uniquely representing the state of a process (say, the hash of a changing object), and the values represent some outcome of a step in that process. The process can contain loops, so at each step we check if the current state's outcome is already stored (thus we want a dict for O(1) lookup), and when a matching state is found we'd like to stop and loop over the in-between states performing some operation on their values (say, summing their outcome values). We may continue the process and find state-loops many times (the actual use case involves non-deterministic branches and thus possibly many loops), and the state-dict might reach a very large size, so iterating over the entire dict every time we find a matching key is undesirable, as is storing keys in an associated list as this would ~double the memory used. Doing this efficiently would require either the addition of indexing to dicts as well as some sort of get_key_index operation, or else could be done without knowing indices if an iter_from_key operation were introduced (which used the internal dk_indices to know where to start iterating over dk_entries). I think this thread touches on the same sorts of debates however so I'm mentioning this here. I also think that even if adding new features to the built-in dict is undesirable, adding a collections.IndexableDict would be very useful (sortedcollections.IndexableDict exists but sorting is not acceptable for many use cases). _______________________________________________ Python-ideas mailing list -- [email protected] To unsubscribe send an email to [email protected] https://mail.python.org/mailman3/lists/python-ideas.python.org/ Message archived at https://mail.python.org/archives/list/[email protected]/message/MK5BHIJYNA5GT5ITFR6XKHPT47RWC5RF/ Code of Conduct: http://python.org/psf/codeofconduct/
