On 31.08.20 06:01, junknenopok@gmail.com 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)