优化慢速代码：获取 android 锁模式的递归程序

Question

我正在做一个项目，想找到 android 模式解锁的所有解决方案。如果您以前没有看过它，这里有 link 到堆栈溢出 post 更详细地讨论它。

基本规则是：

只访问一个节点0次或1次
不跳过未访问的节点
没有循环路径

我的实现涉及解决 N 乘 M 网格的问题，并对模式的最大长度设置上限。这是：

def get_all_sols(grid_size: (int, int), max_len: int) -> list:
    """
    Return all solutions to the android problem as a list
    :param grid_size: (x, y) size of the grid
    :param max_len: maximum number of nodes in the solution
    """
    sols = []

    def r_sols(current_sol):
        current_y = current_sol[-1] // grid_size[1]        # The solution values are stored as ids ->>   0, 1, 2     for an example 3x3 grid
        current_x = current_sol[-1] - current_y * grid_size[1]  # Cache x and y of last visited node     3, 4, 5
        grid = {}  # Prepping a dict to store options for travelling                                     6, 7, 8
        grid_id = -1

        for y in range(grid_size[1]):
            for x in range(grid_size[0]):
                grid_id += 1
                if grid_id in current_sol:  # Avoid using the same node twice
                    continue
                dist = (x - current_x) ** 2 + (y - current_y) ** 2   # Find some kind of distance, no need to root since all values will be like this
                slope = math.atan2((y - current_y), (x - current_x))  # Likely very slow, but need to hold some kind of slope value,
                # so that jumping over a point can be detected

                # If the option table doesnt have the slope add a new entry with distance and id
                # if it does, check distances and pick the closer one
                grid[slope] = (dist, grid_id) if grid.get(slope) is None or grid[slope][0] > dist else grid[slope]

        # The code matches the android login criteria, since:
        # - Each node is visited either 0 or 1 time(s)
        # - The path cannot jump over unvisited nodes, but can over visited ones
        # - The path is not a cycle

        r_sol = [current_sol]
        if len(current_sol) == max_len:  # Stop if hit the max length and return
            return r_sol

        for _, opt in grid.values():  # Else recurse for each possible choice
            r_sol += r_sols(current_sol + [opt])
        return r_sol

    for start in range(grid_size[0] * grid_size[1]):
        sols += r_sols([start])
    return sols

我当前的问题是路径或网格变大时的运行时间。我可以得到一些帮助来优化功能吗？为了进行验证，4x4 网格应具有以下路径统计信息：

1 nodes: 16 paths
2 nodes: 172 paths
3 nodes: 1744 paths
4 nodes: 16880 paths
5 nodes: 154680 paths
6 nodes: 1331944 paths
7 nodes: 10690096 paths

Answer 1

假设算法正确，您可以应用一些小的优化。最大的一个是通过更早地移动 len(current_sol) == max_len 来更早地削减算法。然后，您可以计算 set(current_sol) 以便加快列表搜索。然后，您可以将 val**2 替换为 val*val 并存储一些临时结果而不是重新计算它们。事实上，CPython 的每个基本操作都很慢，而且它几乎没有执行任何优化。这是结果代码：

def get_all_sols_faster(grid_size: (int, int), max_len: int) -> list:
    sols = []

    def r_sols(current_sol):
        r_sol = [current_sol]

        if len(current_sol) == max_len:
            return r_sol

        current_y = current_sol[-1] // grid_size[1]
        current_x = current_sol[-1] - current_y * grid_size[1]
        grid = {}
        grid_id = -1

        current_sol_set = set(current_sol)
        for y in range(grid_size[1]):
            for x in range(grid_size[0]):
                grid_id += 1
                if grid_id in current_sol_set:
                    continue
                diff_x, diff_y = x - current_x, y - current_y
                dist = diff_x * diff_x + diff_y * diff_y
                slope = math.atan2(diff_y, diff_x)

                tmp = grid.get(slope)
                grid[slope] = (dist, grid_id) if tmp is None or tmp[0] > dist else tmp

        for _, opt in grid.values():
            r_sol += r_sols(current_sol + [opt])
        return r_sol

    for start in range(grid_size[0] * grid_size[1]):
        sols += r_sols([start])
    return sols

此代码大约快 3 倍。

老实说，对于这样的暴力算法，CPython 是一团糟。我认为您应该使用本机编译语言来获得更快的代码（当然至少快一个数量级）。请注意，计算结果而不是生成所有解决方案也应该更快。

优化慢速代码：获取 android 锁模式的递归程序

Optimising slow code: recurrsive program for getting android lock patterns

python

optimization