4
\$\begingroup\$

This is my first Python program. It is not very user friendly, but it works. I used some code snippets and tricks I found in various places. And generous people at Stack Overflow helped me with recursion.

This program generates all free polyominoes of given level N for two given tiles: root and tile. Here how it looks for first 4 levels for single square as root and as tile:

Simple free polyominoes up to N=4

But my program is capable of connecting any two given shapes, not just single squares.

The general algorithm is simple. We find free adjacent places around root and then put tile on those places in every possible way. Results then filtered from duplicates and used as tiles for next iteration until N.

The program works okay. You can test several commented shapes at the end. But don't enter too high N cause it will take much time and memory. I think it can run faster and use less memory. And I need advice on this. My first intentions was to reach something like N = 20 in reliable times, but with current code it will take forever.

I tried to implement multiprocessing here (level_multi function). It works faster but not lightning fast. My default (not commented) example takes around 50 seconds to find 5686 free polyominoes with level_linear function and around 30 seconds with level_multi function.

After some research with debugger I found bottleneck in level_multi function at lines 96-99. Multiprocessing generates data in few seconds but then removing duplicates takes much time and works in single process. I'm looking for ways to improve this and maybe make removing duplicates in multiple processes too.

I guess there are some excessive or useless loops and checks as well. I'm seekeng general advice how to make this program better and how to improve above topics. And please make your suggestions novice-friendly if possible.

from time import time
from concurrent.futures import ProcessPoolExecutor, wait

def get_free_edges(tile):
    free_edges = []
    for x,y in tile:
        if (x - 1, y) not in tile: free_edges.append((x - 1, y))
        if (x + 1, y) not in tile: free_edges.append((x + 1, y))
        if (x, y - 1) not in tile: free_edges.append((x, y - 1))
        if (x, y + 1) not in tile: free_edges.append((x, y + 1))
    return sorted(set(free_edges))

def rotate90(tile):
    rotated = []
    zerox,zeroy = tile[0][0],tile[0][1]
    for x,y in tile: rotated.append((-y+zeroy, x+zerox))
    return sorted(set(rotated))

def reflect(tile):
    reflected = []
    for x,y in tile: reflected.append((-x, y))
    return sorted(set(reflected))

def normalize(tile):
    xmin = min(tile, key=lambda t: t[0])[0]
    ymin = min(tile, key=lambda t: t[1])[1]
    normalized = []
    for x,y in tile: normalized.append((x - xmin, y - ymin))
    return sorted(normalized)

def remove_duplicates(tiles):
    seen = []
    seen_add = seen.append
    return [x for x in tiles if not (x in seen or seen_add(x))]

def all_variants(tile):
    tiles = []
    a = tile
    for _ in range(4):
        tiles.append(normalize(a))
        tiles.append(normalize(reflect(a)))
        a = rotate90(a)
    return remove_duplicates(tiles)

def is_valid(tile1,tile2):
    for x,y in tile2:
        if (x,y) in tile1:
            return False
        else:
            continue
    return True

def connect(tile, root):
    result = []
    seen = []
    root_variants = all_variants(root)
    tile_variants = all_variants(tile)
    for r in root_variants:
        free = get_free_edges(r)
        for dx,dy in free:
            for tile in tile_variants:
                for x,y in tile:
                    x2 = -x + dx
                    y2 = -y + dy
                    moved_tile = [(x + x2, y + y2) for x, y in tile]
                    if is_valid(r,moved_tile):
                        poly = normalize(r + moved_tile)
                        if poly not in seen:
                            seen += all_variants(poly)
                            result.append(poly)
    return result

def level_linear(tiles,root,n=2):
    if not isinstance(tiles[0], list): tiles = [tiles]
    result = []
    seen = []
    if n == 2:
        for tile in tiles:
            data = connect(tile, root)
            for i in data:
                if i not in seen:
                    result.append(i)
                    seen += all_variants(i)
        return result
    else:
        return level_linear(level_linear(tiles, root,n-1), root)

def level_multi(tiles,root,n=2):
    if not isinstance(tiles[0], list): tiles = [tiles]
    result = []
    seen = []
    if n == 2:
        futures = [executor.submit(connect, tile, root) for tile in tiles]
        a,b = wait(futures)
        for future in a:
            for i in future.result():
                if i not in seen:
                    result.append(i)
                    seen += all_variants(i)
        return result
    else:
        return level_multi(level_multi(tiles, root,n-1), root)

def pretty_print(tiles):
    for tile in tiles:
        x,y = zip(*tile)
        for i in range(max(x) + 1):
            for j in range(max(y) + 1):
                if (i, j) in tile:
                    print("\033[107m   \033[00m",end="")
                else:
                    print("\033[40m   \033[00m",end="")
            print()
        print()
        print()

if __name__ == '__main__':

    executor = ProcessPoolExecutor(max_workers=10)
    #root = [(0, 0), (0, 1), (1, 0), (1, 1)]
    #root = [(-2,-1),(-1,-1),(0,-1),(0,0)]
    #root = [(0,0),(0,1),(0,2),(0,3)]
    root = [(1,0),(0,1),(1,1),(2,1),(1,2)]
    #root = [(0,0)]

    ts = time()
    #result = level_linear(root,root,6)
    result = level_multi(root,root,6)
    #pretty_print(result)
    print('Total free polyominoes:',len(result))
    print('Took %s seconds'%(time() - ts))
\$\endgroup\$
2
  • 3
    \$\begingroup\$ Wow, that’s a lot of code for a “1st time” program. I suspect you have been coding in other languages as well. The most important thing you can do, when wanting to speed up a program, is to measure where the time is spent. You already did some of that in the debugger. Here is another good resource: docs.python.org/3/library/profile.html#module-cProfile \$\endgroup\$
    – J_H
    Feb 8, 2023 at 22:27
  • 1
    \$\begingroup\$ @J_H Thanks for the input. I'll read the link you suggested. I had some attempts in Python before, but this is my first finished program and it works as intended. I spent several days on this adding one function after another. Although I found a bottleneck here, I still have no idea how to resolve it properly. My general knowledge of Python is limited and I didn't find a suitable answer on Stack Overflow yet. \$\endgroup\$ Feb 9, 2023 at 3:54

1 Answer 1

2
\$\begingroup\$

set data structure

In Python the set data structure is simple to use and extremely fast for removing duplicates. It is a hashtable with dummy values.

I just rewrote the remove_duplicates function as:

def remove_duplicates(tiles):
    set_ = set(tuple(x) for x in tiles)
    return [list(x) for x in set_]

This weird way of writing is required because a list is mutable so it is un-hashable, so I had to convert to tuple that is immutable and thus hashable and back to list.

This lowers the runtime from 98 seconds to 73 seconds, for a 25% improvement.

pypy

Your code works without changes with PyPy, a Just In Time Python compiler. Running your code (with only the change above) with pypy lowers the runtime again from 73 seconds to 55 seconds, for an around 25% improvement again.

Optimal number of workers

You can get the maximum efficiency from multiprocessing by using a number of workers equal to the number of cores in your machine:

executor = ProcessPoolExecutor(max_workers=multiprocessing.cpu_count())

This improves the performance another 10% down to 48 seconds.

Avoid building the intermediate list of tiles

I avoid building the tiles list like this:

def all_variants_nonunique(tile):
    a = tile
    for _ in range(4):
        yield normalize(a)
        yield normalize(reflect(a))
        a = rotate90(a)

def all_variants(tile):
    return remove_duplicates(all_variants_nonunique(tile))

This makes the code cleaner and saves a bit of space, but does not make the code substantially faster. Also fascinatingly now Cpython (standard one) is around 10% faster than pypy. The runtime is still around 48 seconds for Python and 53 for pypy. The speed-up from pypy can be quite situational.

Huge optimization with set

As you said, checking for duplicates in level_multi was taking a really long time so I made this change to use set:

def level_multi(tiles,root,n=2):
    if not isinstance(tiles[0], list): tiles = [tiles]
    result = []
    seen = set()
    if n == 2:
        futures = [executor.submit(connect, tile, root) for tile in tiles] # maybe round brackets
        a,b = wait(futures)
        for future in a:
            for i in future.result():
                ti = tuple(i)
                if ti not in seen:
                    result.append(i)
                    seen.update(tuple(x) for x in all_variants(ti))
        return result
    else:
        return level_multi(level_multi(tiles, root,n-1), root)

As before I had to use tuple as lists cannot be hashed. Now the runtime is 4.3 seconds, a 90% improvement from before and a 95% improvement in total. Enjoy your fast code and remember to always use the right data structure for the job :)

Resign on N = 20

There is an exponential growth of the computation needed as N gets bigger so N = 20 maybe is be possible with perfect C code and a supercomputer, maybe not even then.

Here are the runtimes as function of N:

N = 2
Total free polyominoes: 2
Took 0.006714709001244046 seconds
N = 3
Total free polyominoes: 9
Took 0.005609088999335654 seconds
N = 4
Total free polyominoes: 69
Took 0.03604784200069844 seconds
N = 5
Total free polyominoes: 578
Took 0.37278968099963095 seconds
N = 6
Total free polyominoes: 5686
Took 4.547746743999596 seconds
N = 7
Total free polyominoes: 57957
Took 78.65434089600058 seconds

Each time N increases by one the runtime becomes 10x the one before. N = 20 will be 10^13 times slower then a minute. So it will take 19_013_258.8 years. You read that right, 19 millions years...

Final large possibility for optimization

If you change your code so that arguments to functions are always tuples or other hashable objects, you can try using functools.lru_cache to optimize for speed by saving the results of applying the function to a input in a hashmap. This may yield another significant improvement.

\$\endgroup\$
4
  • \$\begingroup\$ Wow, that's huge. Thank you for all your suggestions! As you can see I used list-set-list conversions in other parts of my program, but I would never figure out how to implement it everywhere. Now I want to try these improvements one by one and then all together. I'm sure I'll learn many new things in the process. \$\endgroup\$ Feb 9, 2023 at 16:26
  • \$\begingroup\$ @DmitryArch You are welcome, I am glad I could help. If you manage to implement the lru_cache tell me about the results as I am very curious. \$\endgroup\$
    – Caridorc
    Feb 9, 2023 at 16:39
  • 1
    \$\begingroup\$ Now that's speed! With all improvements on my system Intel 12600K it took just 18 seconds to generate N=7 and I was even able to make N=8 too! It ate all my RAM though and took 248 seconds. Total free polyominoes: 610404. Now I'll start to learn lru_cache. \$\endgroup\$ Feb 9, 2023 at 19:33
  • 1
    \$\begingroup\$ Also, I bring that improvement you made in level_multi function into connect function as well. It saved almost 1 second for N=7 and N=8 finished in 223 seconds. \$\endgroup\$ Feb 9, 2023 at 19:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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