Updating a dictionary of trajectories after a step has been made

Question

I am using a dictionary to save possible trajectories in a game. A trajectory is defined as a list of numbers separated by _. For example '3_7_2_5' is a trajectory of 4 steps. I use a dictionary as I assign a value to each trajectory. The meaning of this value does not matter for the purpose of my question. I also save the trajectories in separated dictionaries if they have different numbers of steps.

I want to update the dictionary in such a way that only the trajectories starting from '1' are preserved. Moreover, I want to remove the '1' from the name, since I don't need to keep listing a step that has already been made.

# here I create the initial dictionaries 

pts=[{},{},{}]

for j in range(20):
    k=random.choice(range(3))
    path=str(k)
    for d in range(len(pts)):
        k=random.choice(range(4))       
        pts[d][path]=k
        path+='_'+str(k)

print 'initial dictionaries =',pts

# here I make the update


ind=1
new_pts=[{},{},{}]
path=str(ind)
for d in range(len(pts)-1):
    for path in pts[d+1]:
        if path[:len(str(ind))]==str(ind):
            new_pts[d][path[len(str(ind))+1:]]=pts[d+1][path]


pts=new_pts

print 'updated dictionaries =',pts

As you can see, the first element of the old list pts has been discarded. The second element has been used to create the first element of the updated list and so on.

Now, it seems to me that my algorithm is not very efficient. For updating the dictionary I am using a for loop over all keys, even though most of them are going to be discarded. Is there a better, faster way to do this?

Answer 1

Basic Review

1. You should import print_function from __future__. So you can use print like you can in Python 3.

2. Your variable names are poor.

   • j should be _.
   • What do j, k and d mean?
   • Why not just type out parts rather than use pts?

3. The way you're generating key value pairs in not amazing. If you make a function to build 20 keys then it would be much easier to understand. This is as things are split into two core aspects.

   • Building key
   • Building the dictionary

4. You should really use some functions.

5. You should really follow PEP 8. Your code is really hard to read because it looks like a block of characters, rather than a Python program.

Functional changes

6. A trajectory is defined as a list of numbers separated by _.

   You should make it a tuple of numbers, (3, 7, 2, 5).

7. I also save the trajectories in separated dictionaries if they have different numbers of steps.

   I see no reason to do this.

8. You may benefit from using a trie instead.

   Since you're just printing the new dictionaries it doesn't make much sense. However it looks exactly like what you want datatype wise.

   I have included a build and an as_dict method to make understanding how it works a little simpler. You can easily remove the need for build by using it to build the trie directly from generate_keys.

from __future__ import print_function
import random


def generate_keys(amount, choices):
    for _ in range(amount):
        yield tuple(
            random.choice(choices[i])
            for i in range(random.randint(1, len(choices)))
        )


class Trie(dict):
    value = DEFAULT = object()

    @classmethod
    def build(cls, mapping):
        trie = cls()
        for keys, value in mapping.items():
            node = trie
            for key in keys:
                node = node.setdefault(key, cls())
            node.value = value
        return trie

    def _as_dict(self, path):
        for key, value in self.items():
            keys = path + (key,)
            if value.value is not self.DEFAULT:
                yield keys, value.value
            for item in value._as_dict(keys):
                yield item

    def as_dict(self):
        return dict(self._as_dict(()))


paths = {}
for key in generate_keys(20, [range(3), range(4), range(5)]):
    paths[key] = random.randrange(10)

trie = Trie.build(paths)
paths_new = trie[1].as_dict()

# Sort the output so it's easier to read
print('Initial dictionary =', dict(sorted(paths.items())))
print('Inital Trie =', trie)
print('Updated dictionaries =', dict(sorted(paths_new.items())))