On 31.08.20 06:01, [email protected] wrote:
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.
Unless I'm misunderstanding the task, it sounds like this could be
solved by repeated lookups of cycle elements. It seems to be a special
case anyway that all cycles are inserted in order into the dict. I.e.
instead of iterating from one key to another you would just iterate the
cycle:
if outcome in states:
cycle = [outcome]
while (state := states[cycle[-1]]) != outcome:
cycle.append(state)
result = sum(cycle)
_______________________________________________
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/R2MIVDA3Y5QYYO25HTGKUTZ74MAUNCRL/
Code of Conduct: http://python.org/psf/codeofconduct/
