python - 低效的扩展算法

Question

所以我正在尝试编写一个程序，它采用网格和网格上的起点，并向外扩展该点，用到达该位置所需的扩展次数标记每个单元格。

对于我的应用程序，扩展无法查看其他单元格并将它们的值用作引用或覆盖先前设置的单元格的值。我已经编写了代码来执行此操作，并且它完全按照我想要的方式工作，但是当我尝试进行 8 次或更多次扩展时，我的计算机会遇到困难。

任何人都可以在我的代码中找到任何会使它变得如此低效的地方并就如何改进它提出建议吗？

提前致谢!

grid = [[9 for col in range(25)] for row in range(25)]

start = [12, 12]
grid[start[0]][start[1]] = 0
numRips = 7

def handler():
    allExpanded = [start]
    expanded = [start]
    num = 1
    for r in range(numRips):
        toExpand = []
        for n in expanded:
            toExpand = toExpand + (getUnvisitedNeighbors(n, allExpanded))
        expanded = []
        for u in toExpand:
            grid[u[0]][u[1]] = num
            expanded.append(u)
            allExpanded.append(u)
        num += 1




def getUnvisitedNeighbors(loc, visitedCells):
    x, y = loc[0], loc[1]

    neighbors = [[x - 1, y], [x + 1, y], [x, y - 1], [x, y + 1], \
                 [x - 1, y - 1], [x - 1, y + 1], [x + 1, y - 1], [x + 1, y + 1]]

    f = lambda p: p[0] >=0 and p[0] < len(grid) and \
                    p[1] >= 0 and p[1] < len(grid[0]) and \
                    not p in visitedCells

    unvisitedNeighbors = filter(f, neighbors)

    return unvisitedNeighbors

handler()
for i in range(len(grid)):
    print grid[i]

Answer 1

我修改了你的代码，所以它可以计时:

import os
import sys
import timeit

setup_str = \
'''
from __main__ import setup, handler

setup()
'''
def setup():
    global grid
    grid = [[9 for col in range(25)] for row in range(25)]

    global start
    start = [12, 12]
    grid[start[0]][start[1]] = 0
    global numRips
    numRips = 8

def handler():
    global grid
    global start
    global numRips
    allExpanded = [start]
    expanded = [start]
    num = 1
    for r in range(numRips):
        toExpand = []
        for n in expanded:
            toExpand = toExpand + (getUnvisitedNeighbors(n, allExpanded))
        expanded = []
        for u in toExpand:
            grid[u[0]][u[1]] = num
            expanded.append(u)
            allExpanded.append(u)
        num += 1

def getUnvisitedNeighbors(loc, visitedCells):
    global grid
    x, y = loc[0], loc[1]

    neighbors = [[x - 1, y], [x + 1, y], [x, y - 1], [x, y + 1], \
                 [x - 1, y - 1], [x - 1, y + 1], [x + 1, y - 1], [x + 1, y + 1]]

    f = lambda p: p[0] >=0 and p[0] < len(grid) and \
                    p[1] >= 0 and p[1] < len(grid[0]) and \
                    not p in visitedCells

    unvisitedNeighbors = filter(f, neighbors)

    return unvisitedNeighbors

print timeit.repeat(stmt="handler()", setup=setup_str, repeat=3, number=1)
for i in range(len(grid)):
    print grid[i]

花费了:[63.33822661788784, 64.53106826397212, 61.407282939290724] 秒。

保持程序的粗略结构，我将其更改为:

import os
import sys
import timeit

setup_str = \
'''
from __main__ import setup, handler

setup()
'''

dirs = \
(
    ( - 1,   0),
    ( + 1,   0),
    (   0, - 1),
    (   0, + 1),
    ( - 1, - 1),
    ( - 1, + 1),
    ( + 1, - 1),
    ( + 1, + 1)
)

def setup():
    global grid_max_x
    grid_max_x = 25
    global grid_max_y
    grid_max_y = 25
    global grid
    grid = [[9 for col in range(grid_max_y)] for row in range(grid_max_x)]

    global start
    start = (12, 12)
    grid[start[0]][start[1]] = 0
    global numRips
    numRips = 8

def handler():
    global grid
    global start
    global numRips
    border_expanded = set([start])
    allExpanded = set([start])
    num = 1
    for r in range(numRips):
        toExpand = set([])
        map(lambda x: toExpand.update(x), [(getUnvisitedNeighbors(n, allExpanded)) for n in border_expanded])
        border_expanded = toExpand
        allExpanded.update(toExpand)
        for u in toExpand:
            grid[u[0]][u[1]] = num
        num += 1

def getUnvisitedNeighbors(loc, visitedCells):
    global grid_max_x
    global grid_max_y
    global dirs

    x, y = loc

    neighbors = set([((x + dx) % grid_max_x, (y + dy) % grid_max_y) for (dx, dy) in dirs])

    unvisitedNeighbors = neighbors - visitedCells

    return unvisitedNeighbors

print timeit.repeat(stmt="handler()", setup=setup_str, repeat=3, number=1)
for i in range(len(grid)):
    print grid[i]

这花了 [0.0016090851488842293, 0.0014349565512783052, 0.0014186988443765235] 秒。

基本上，您希望尽量减少分配、复制和迭代的数量。