3

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

对于我的应用程序，扩展无法查看其他单元格并将它们的值用作参考或覆盖先前设置的单元格的值。我已经编写了代码来执行此操作，并且它完全按照我的意愿工作，但是当我尝试进行 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]
4

2 回答 2

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] 秒。

基本上，您希望最小化完成的分配、复制和迭代的数量。

于 2013-07-03T04:42:15.863 回答
0

所以这就是我最终想出的，运行速度非常快，也非常简单。如果有人试图实现类似的算法：

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

start = [12,12]

rippleLoss = .01
rippleLimit = .5
reward = .6

def expansion(curLoc):
    edge = int((reward - rippleLimit) / rippleLoss)
    c = 0

    for y in range(-edge, edge + 1):
        for x in range(-edge, edge + 1):
            if isValidCell([curLoc[0] + x, curLoc[1] + y]):
                if abs(x) > abs(y):
                    c = abs(x) - abs(y)
                else:
                    c = 0
                grid[curLoc[1] + y][curLoc[0] + x] = abs(y) + c

def isValidCell(loc):
    return loc[0] >=0 and loc[0] < len(grid) and loc[1] >= 0 and loc[1] < len(grid[0])

expansion(start)
for i in range(len(grid)):
    print grid[i]
于 2013-07-03T04:03:54.940 回答