2
\$\begingroup\$

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?

\$\endgroup\$
  • 1
    \$\begingroup\$ (Please include an import such that random.choice() works by just cut&paste. Please tag python-2.x (or add parentheses to the print).) For [update I] loop over all keys, even though most [are] discarded For really helpful reviews, please provide more context: Why are those entries in the dictionary in the first place? What is special about trajectories starting from '1'? (What about those starting from 0?) \$\endgroup\$ – greybeard Jun 28 at 2:50
  • \$\begingroup\$ @greybeard In my example, I assume that I actually made the choice '1'.Therefore the trajectories must be updated, keeping only those that were starting by '1'. The choice of 1 specifically is arbitrary, I could have chosen 0 or any number in my example. \$\endgroup\$ – 3sm1r Jun 28 at 19:38
1
\$\begingroup\$

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

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

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

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

    I see no reason to do this.

  3. 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())))
| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ TY. When I try to run your code, it returns the following error yield from value._as_dict(keys) ^ SyntaxError: invalid syntax \$\endgroup\$ – 3sm1r Jun 28 at 22:31
  • 1
    \$\begingroup\$ @3sm1r Ah yes, I forgot that's not in Python 2. I have changed to a Python 2 version. \$\endgroup\$ – Peilonrayz Jun 29 at 7:31
  • \$\begingroup\$ Very nice. When you write class Trie(dict):, does it serve to be able to give all the properties of dictionaries to the instances of the class? Also, what is the use of value = DEFAULT = object() ? What does object() do and why are you writing DEFAULT like that ? \$\endgroup\$ – 3sm1r Jul 4 at 1:33
  • \$\begingroup\$ ^ the first question of my previous comment was just about why you need to write class Trie(dict): instead of just class Trie:. \$\endgroup\$ – 3sm1r Jul 4 at 3:46
  • 1
    \$\begingroup\$ @3sm1r "why you need to write" where would node.setdefault, self.items and trie[1] come from? If you're happy to write your own version of each of these functions then you can just use class Trie(object): since you're in Python 2. DEFAULT is a constant and is following PEP 8. object() makes an empty object, which is used here value.value is not self.DEFAULT. \$\endgroup\$ – Peilonrayz Jul 4 at 8:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.