Optimization by using lists instead of dicts in Python

Question

I have some Python code that is far, far slower than it really ought to be.

#Generate planets
for t in range(stars*3): #There are 3 planets for every star, but not every star will have 3 planets
    theplanet=Planet()

    if random.randint(0,100) <= 25: #25% of planets have life
        theplanet.tl=random.randint(1,9)    #With a random tech level
    else:
        theplanet.tl=0  #The rest don't

    theplanet.star=stardict[random.choice(list(stardict.keys()))]     #Choose a random star
    theplanet.star.planets+=(theplanet,)    #Append the new planet to the star's list of planets
    theplanet.name=theplanet.star.name+"-"+str(len(theplanet.star.planets)) #Name the planet Starname-X, where X is the length of the star's planets tuple. Since this increases every time a planet is added, it will be 1 for the first planet, 2 for the next, etc...

    if math.floor((t/(stars*3))*100)==(t/(stars*3))*100: print("Generating planets: "+str((t/(stars*3))*100)+"% done.")

I'm pretty sure the bottleneck is in the star=stardict[random.choice(list( etc... line. I'm guessing here, but I assume dicts work by searching through every entry in the dict and seeing which one has the right key. Lists, I assume again, would just read off the information at a memory location derived from the entry number, and for extremely large (200,000 entries, to be exact) lists/dicts be much faster.

Would converting the dict's entries to a list make this code faster? How would I do this (I thought I saw a function for it, reviewing the docs now...)? Are there any other ways anyone notices to make this faster?

Answer 1

You're creating a list every time through the loop, but that list is unchanging. Move it outside of the loop.

starlist=list(stardict.keys())
...
    theplanet.star=stardict[random.choice(starlist)]     #Choose a random star

The problem almost certainly isn't in the dict lookup. They're based on hash tables which are quite fast.

Answer 2

1. Move the list generation list(stardict.keys()) outside the loop

2. Try to profile your code (documentation)

3. Assuming you are running CPython, check if your code could run with Pypy. This could lead to better performances due to its optimised JIT

Answer 3

You only use the key as in intermediate value to select a random item in stardict. You can use the dictionary's value list directly instead:

#Generate planets
starlist = stardict.values()
for t in range(stars*3): #There are 3 planets for every star, but not every star will have 3 planets
    theplanet=Planet()

    if random.randint(0,100) <= 25: #25% of planets have life
        theplanet.tl=random.randint(1,9)    #With a random tech level
    else:
        theplanet.tl=0  #The rest don't

    theplanet.star=random.choice(starlist)     #Choose a random star
    theplanet.star.planets+=(theplanet,)    #Append the new planet to the star's list of planets
    theplanet.name=theplanet.star.name+"-"+str(len(theplanet.star.planets)) #Name the planet Starname-X, where X is the length of the star's planets tuple. Since this increases every time a planet is added, it will be 1 for the first planet, 2 for the next, etc...

    if math.floor((t/(stars*3))*100)==(t/(stars*3))*100: print("Generating planets: "+str((t/(stars*3))*100)+"% done.")