效率低下的擴展算法

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

基本上，你想盡量減少分配，複製和迭代的數量。

Answer 2

所以這是我最終想出來的，工作非常快，而且非常簡單。如果有人試圖實現類似的算法：

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]