How to optimise a Python function (loops, append, tkinter, update image)-CodePudding

I have a world map (water is white, land is grey). I have a dictionary of various civilisations and their colours. And I have a function that calls another function (presented below) that fills in this world map with the civilisations' colours. This is 'turn based', in that the function below is sequentially executed e.g. a thousand times.

I don't know much about how to optimise code for performance. I know that for-loops can be replaced in various ways; e.g. 'i in range' can use numpy's arange, and calculations can be vectorised. But... None of this largely theoretical knowledge helps me optimise the code below.

I have added comments for clarity:

def GenerateWorld(basemap, civilisationdictionary):
# For every civilisation, find the civilisation's colour
    for i in civilisationdictionary.keys():
        colour = civilisationdictionary[i]['colour1']
# Compare the civilisation's colour to the colours present on the world map
        tempcolour = list(colour)
        tempcolour.append(255)
        colour = tuple(tempcolour)
        civcolourcheck = str(colour)
        mapcolourcheck = str(basemap.getcolors())
# Check if the civilisation's colour already exists on the world map
        if not (civcolourcheck in mapcolourcheck):
# If not, find a spot to place the first pixel of this civilisation, first by selecting one of a variable amount of square regions
            xylen = random.randint(1,len(worldmapdictionary[i]['minx']))-1
# Find a spot to place the first pixel of this civilisation by selecting a random x/y coordinate within the selected square region
            x = random.randint(worldmapdictionary[i]['minx'][xylen],worldmapdictionary[i]['maxx'][xylen])
            y = random.randint(worldmapdictionary[i]['miny'][xylen],worldmapdictionary[i]['maxy'][xylen])
# If the selected x/y coordinate is white (i.e. water), select another one, until we find land (not white), try again next turn if it takes too long to prevent infinite loops
            whilecounter = 0
            while (basemap.getpixel((x,y)) == (255,255,255,255))  and whilecounter < 1000:
                xylen = random.randint(1,len(worldmapdictionary[i]['minx']))-1
                x = random.randint(worldmapdictionary[i]['minx'][xylen],worldmapdictionary[i]['maxx'][xylen])
                y = random.randint(worldmapdictionary[i]['miny'][xylen],worldmapdictionary[i]['maxy'][xylen])
                whilecounter  = 1
            if whilecounter != 1000:
                basemap.putpixel((x,y), colour)
# If the civilisation already has a pixel on the map
        else:
            ownpixels = []
# For all the pixels on the map, check if they are the civilisation's colour and if yes, save them to a list
            allpixels = basemap.load()
            for xmap in range(basemap.size[0]):
                for ymap in range(basemap.size[1]):
                    if allpixels[xmap,ymap] == colour:
                        ownpixels.append([xmap,ymap])
            allnewpixels = []
# For all these civilisation's pixels, obtain all the surrounding pixels
            for pixel in ownpixels:
                allnewpixels.append([pixel[0]-1,pixel[1]-1])
                allnewpixels.append([pixel[0]-1,pixel[1]])
                allnewpixels.append([pixel[0]-1,pixel[1] 1])
                allnewpixels.append([pixel[0],pixel[1]-1])
                allnewpixels.append([pixel[0],pixel[1] 1])
                allnewpixels.append([pixel[0] 1,pixel[1]-1])
                allnewpixels.append([pixel[0] 1,pixel[1]])
                allnewpixels.append([pixel[0] 1,pixel[1] 1])
# Save only those pixels that are adjacent to a civilisation's pixel, but are not currently part of this civilisation (i.e. not coloured in the civilisation's colour, i.e. not present in the earlier list)
            newpixels = [j for j in allnewpixels if j not in ownpixels]
# Pick a new pixel to colour in this civilisation's colour
            x = random.choice(newpixels)[0]
            y = random.choice(newpixels)[1]
# If the selected x/y coordinate is white (i.e. water), select another one, until we find land (not white), try again next turn if it takes too long to prevent infinite loops
            whilecounter = 0
            while (basemap.getpixel((x,y)) == (255,255,255,255)) and whilecounter < 1000:
                x = random.choice(newpixels)[0]
                y = random.choice(newpixels)[1]
                whilecounter  = 1
            if whilecounter != 1000:
                basemap.putpixel((x,y), colour)
# Return the updated map to the calling function
    return basemap

As you can see, there are many for-loops and .append-operations. I assume - but, I know nothing - that this can be done much faster than it currently runs, but, I don't know how. Through Google, I find examples such as people using a for-loop to sum up amounts, and, yeah, I understand how to optimise that - but the kind of usecase I have here, I cannot really find through Google. How would you go about optimising this, if at all possible?

Thank you in advance!

And, maybe it helps, the actual code without the comments I added here, as well as the function that calls the function described above (because now that I am writing this - could it be that the function itself is fine enough, but that tkinter / updating the map is what slows it down?):

def GenerateWorldMapMain():
    global tkbasemap
    for i in range(1000):
        print('Turn:',i)
        if tkbasemap == '':
            basemap = Image.open('basemap.png')
        else:
            basemap = ImageTk.getimage(tkbasemap)
        basemap = history.GenerateWorld(basemap,d1.civilisationdictionary)
        tkbasemap = ImageTk.PhotoImage(basemap)
        imagelabel.configure(image=tkbasemap)
        imagelabel.image=tkbasemap
        imagelabel.update()



def GenerateWorld(basemap, civilisationdictionary):
    for i in civilisationdictionary.keys():
        colour = civilisationdictionary[i]['colour1']
        tempcolour = list(colour)
        tempcolour.append(255)
        colour = tuple(tempcolour)
        civcolourcheck = str(colour)
        mapcolourcheck = str(basemap.getcolors())
        if not (civcolourcheck in mapcolourcheck):
            xylen = random.randint(1,len(worldmapdictionary[i]['minx']))-1
            x = random.randint(worldmapdictionary[i]['minx'][xylen],worldmapdictionary[i]['maxx'][xylen])
            y = random.randint(worldmapdictionary[i]['miny'][xylen],worldmapdictionary[i]['maxy'][xylen])
            whilecounter = 0
            while (basemap.getpixel((x,y)) == (255,255,255,255))  and whilecounter < 1000:
                xylen = random.randint(1,len(worldmapdictionary[i]['minx']))-1
                x = random.randint(worldmapdictionary[i]['minx'][xylen],worldmapdictionary[i]['maxx'][xylen])
                y = random.randint(worldmapdictionary[i]['miny'][xylen],worldmapdictionary[i]['maxy'][xylen])
                whilecounter  = 1
            if whilecounter != 1000:
                basemap.putpixel((x,y), colour)
        else:
            ownpixels = []
            allpixels = basemap.load()
            for xmap in range(basemap.size[0]):
                for ymap in range(basemap.size[1]):
                    if allpixels[xmap,ymap] == colour:
                        ownpixels.append([xmap,ymap])
            allnewpixels = []
            for pixel in ownpixels:
                allnewpixels.append([pixel[0]-1,pixel[1]-1])
                allnewpixels.append([pixel[0]-1,pixel[1]])
                allnewpixels.append([pixel[0]-1,pixel[1] 1])
                allnewpixels.append([pixel[0],pixel[1]-1])
                allnewpixels.append([pixel[0],pixel[1] 1])
                allnewpixels.append([pixel[0] 1,pixel[1]-1])
                allnewpixels.append([pixel[0] 1,pixel[1]])
                allnewpixels.append([pixel[0] 1,pixel[1] 1])
            newpixels = [j for j in allnewpixels if j not in ownpixels]
            x = random.choice(newpixels)[0]
            y = random.choice(newpixels)[1]
            whilecounter = 0
            while (basemap.getpixel((x,y)) == (255,255,255,255)) and whilecounter < 1000:
                x = random.choice(newpixels)[0]
                y = random.choice(newpixels)[1]
                whilecounter  = 1
            if whilecounter != 1000:
                basemap.putpixel((x,y), colour)
    return basemap

Again, thank you in advance! :)

CodePudding user response：

there are many(...).append-operations.

You are using .append method of list instance, if this is main time consumer, you should get noticable improvement, after replacing it with deque, as it is data structure optimized for appends. It is iterable so you might then use it in list-comprehension, consider following simple example

import collections
d = collections.deque()
for i in range(100):
    d.append(i)
selected = [i for i in d if i==0]
print(selected)

gives output

[0, 10, 20, 30, 40, 50, 60, 70, 80, 90]

Edit after more profile data given: note that .size of PIL Image takes most tottime, if size of basemap is fixed, then you might store basemap.size[0] and basemap.size[1] in variables, say size0 and size1 before outermost for loop and then use them in your ranges to avoid bothering PIL more times then neccessary.

CodePudding user response：

I ended up moving a few things to global dictionaries that can be passed back and forth, so that the code doesn't need to look at every pixel on the map for every civilisation every single turn. I also chose a smaller map, and probably changed some other things, but the main improvement/conclusion is what I just wrote. Perhaps someday it helps someone:

def GenerateWorld(basemap,basemapx,basemapy,pixeldictionary,ownpixels,civilisationdictionary):
for civilisation in civilisationdictionary.keys():
    colour = civilisationdictionary[civilisation]['colour1']
    tempcolour = list(colour)
    tempcolour.append(255)
    colour = tuple(tempcolour)
    civcolourcheck = str(colour)
    mapcolourcheck = str(basemap.getcolors())
    if not (civcolourcheck in mapcolourcheck):
        xylen = random.randint(1,len(worldmapdictionary[civilisation]['minx']))-1
        x = random.randint(worldmapdictionary[civilisation]['minx'][xylen],worldmapdictionary[civilisation]['maxx'][xylen])
        y = random.randint(worldmapdictionary[civilisation]['miny'][xylen],worldmapdictionary[civilisation]['maxy'][xylen])
        whilecounter = 0
        while (basemap.getpixel((x,y)) != (192,192,192,255)) and whilecounter < 1000:
            xylen = random.randint(1,len(worldmapdictionary[civilisation]['minx']))-1
            x = random.randint(worldmapdictionary[civilisation]['minx'][xylen],worldmapdictionary[civilisation]['maxx'][xylen])
            y = random.randint(worldmapdictionary[civilisation]['miny'][xylen],worldmapdictionary[civilisation]['maxy'][xylen])
            whilecounter  = 1
        if whilecounter != 1000:
            basemap.putpixel((x,y), colour)
    else:
        allpixels = basemap.load()
        if not pixeldictionary:
            for xmap,ymap in itertools.product(range(basemapx),range(basemapy)):
                pixelvalue = allpixels[xmap,ymap]
                pixeldictionary[xmap,ymap] = (pixelvalue)
        if ownpixels.get(civilisation) is None:
            ownpixels[civilisation] = [list(j) for j in pixeldictionary.keys() if pixeldictionary[j] == (colour)]
        allnewpixels = collections.deque() #[] #Quite possibly slower?
        for pixel in ownpixels[civilisation]:
            allnewpixels.append([pixel[0]-1,pixel[1]-1])
            allnewpixels.append([pixel[0]-1,pixel[1]])
            allnewpixels.append([pixel[0]-1,pixel[1] 1])
            allnewpixels.append([pixel[0],pixel[1]-1])
            allnewpixels.append([pixel[0],pixel[1] 1])
            allnewpixels.append([pixel[0] 1,pixel[1]-1])
            allnewpixels.append([pixel[0] 1,pixel[1]])
            allnewpixels.append([pixel[0] 1,pixel[1] 1])
        newpixels = [k for k in allnewpixels if k not in ownpixels[civilisation]]
        for l in range(3):
            x = random.choice(newpixels)[0]
            y = random.choice(newpixels)[1]
            whilecounter = 0
            while (pixeldictionary[x,y] != (192,192,192,255)) and whilecounter < 1000:
                x = random.choice(newpixels)[0]
                y = random.choice(newpixels)[1]
                whilecounter  = 1
            if whilecounter != 1000:
                pixeldictionary[x,y] = (colour)
                ownpixels[civilisation].append([x,y])
                basemap.putpixel((x,y), colour)
return basemap, pixeldictionary, ownpixels