计算 A* 寻路算法的执行时间时缺少 Python 列表中的项目
Missing item from Python List when counting execution time for A* Pathfinding algorithm
我已经构建了一个 A* 寻路算法，可以找到从 A 点到 B 点的最佳路线，有一个计时器可以开始和结束 post 算法的执行和路径是绘制的，这是解析为全局变量。所以当我 运行 算法不止一次（以获得平均时间）时它是可访问的。
全局变量被添加到列表中，除了当我 运行 算法 5 次时，只有 4 个值被添加（我可以看到 5 次被记录为算法在完成后打印时间）。当显示列表时，它总是错过第一次，如果我 运行 算法 5 次，则只有 2、3、4、5 次。这里是 main.py
import astar
import pygame
def main():
timing_list = []
WIDTH = 800
WIN = pygame.display.set_mode((WIDTH, WIDTH))
for x in range(0, 4):
astar.main(WIN, WIDTH)
timing_list.insert(x, astar.full_time)
print(timing_list)
if __name__ == "__main__":
main()
和
astar.py
from queue import PriorityQueue
from random import randint
import pygame
from timing import Timing
WIDTH = 800
WIN = pygame.display.set_mode((WIDTH, WIDTH))
pygame.display.set_caption("A* Path Finding Algorithm")
RED = (255, 0, 0)
GREEN = (0, 255, 0)
BLUE = (0, 255, 0)
YELLOW = (255, 255, 0)
WHITE = (255, 255, 255)
BLACK = (0, 0, 0)
PURPLE = (128, 0, 128)
ORANGE = (255, 165, 0)
GREY = (128, 128, 128)
TURQUOISE = (64, 224, 208)
global full_time
class Spot:
def __init__(self, row, col, width, total_rows):
self.row = row
self.col = col
self.x = row * width
self.y = col * width
self.color = WHITE
self.neighbors = []
self.width = width
self.total_rows = total_rows
def get_pos(self):
return self.row, self.col
def is_closed(self):
return self.color == RED
def is_open(self):
return self.color == GREEN
def is_barrier(self):
return self.color == BLACK
def is_start(self):
return self.color == ORANGE
def is_end(self):
return self.color == TURQUOISE
def reset(self):
self.color = WHITE
def make_start(self):
self.color = ORANGE
def make_closed(self):
self.color = RED
def make_open(self):
self.color = GREEN
def make_barrier(self):
self.color = BLACK
def make_end(self):
self.color = TURQUOISE
def make_path(self):
self.color = PURPLE
def draw(self, win):
pygame.draw.rect(win, self.color, (self.x, self.y, self.width, self.width))
def update_neighbors(self, grid):
self.neighbors = []
if self.row < self.total_rows - 1 and not grid[self.row + 1][self.col].is_barrier(): # DOWN
self.neighbors.append(grid[self.row + 1][self.col])
if self.row > 0 and not grid[self.row - 1][self.col].is_barrier(): # UP
self.neighbors.append(grid[self.row - 1][self.col])
if self.col < self.total_rows - 1 and not grid[self.row][self.col + 1].is_barrier(): # RIGHT
self.neighbors.append(grid[self.row][self.col + 1])
if self.col > 0 and not grid[self.row][self.col - 1].is_barrier(): # LEFT
self.neighbors.append(grid[self.row][self.col - 1])
def __lt__(self, other):
return False
def generate_num(x, y):
return randint(x, y)
def h(p1, p2):
x1, y1 = p1
x2, y2 = p2
return abs(x1 - x2) + abs(y1 - y2)
def reconstruct_path(came_from, current, draw):
while current in came_from:
current = came_from[current]
current.make_path()
draw()
def algorithm(draw, grid, start, end):
count = 0
open_set = PriorityQueue()
open_set.put((0, count, start))
came_from = {}
g_score = {spot: float("inf") for row in grid for spot in row}
g_score[start] = 0
f_score = {spot: float("inf") for row in grid for spot in row}
f_score[start] = h(start.get_pos(), end.get_pos())
open_set_hash = {start}
while not open_set.empty():
for event in pygame.event.get():
if event.type == pygame.QUIT:
pygame.quit()
current = open_set.get()[2]
open_set_hash.remove(current)
if current == end:
reconstruct_path(came_from, end, draw)
end.make_end()
return True
for neighbor in current.neighbors:
temp_g_score = g_score[current] + 1
if temp_g_score < g_score[neighbor]:
came_from[neighbor] = current
g_score[neighbor] = temp_g_score
f_score[neighbor] = temp_g_score + h(neighbor.get_pos(), end.get_pos())
if neighbor not in open_set_hash:
count += 1
open_set.put((f_score[neighbor], count, neighbor))
open_set_hash.add(neighbor)
neighbor.make_open()
draw()
if current != start:
current.make_closed()
return False
def make_grid(rows, width):
grid = []
gap = width // rows
for i in range(rows):
grid.append([])
for j in range(rows):
spot = Spot(i, j, gap, rows)
grid[i].append(spot)
return grid
def draw_grid(win, rows, width):
gap = width // rows
for i in range(rows):
pygame.draw.line(win, GREY, (0, i * gap), (width, i * gap))
for j in range(rows):
pygame.draw.line(win, GREY, (j * gap, 0), (j * gap, width))
def draw(win, grid, rows, width):
win.fill(WHITE)
for row in grid:
for spot in row:
spot.draw(win)
draw_grid(win, rows, width)
pygame.display.update()
def get_clicked_pos(pos, rows, width):
gap = width // rows
y, x = pos
row = y // gap
col = x // gap
return row, col
def main(win, width):
rows = 50
grid = make_grid(rows, width)
start = None
end = None
t = Timing()
run = True
setup_config = True
while run:
draw(win, grid, rows, width)
for event in pygame.event.get():
if event.type == pygame.QUIT:
run = False
setup_config = False
if event.type == pygame.KEYDOWN:
if event.key == pygame.K_ESCAPE:
run = False
setup_config = False
while setup_config:
for x in range(0, 800):
row_pos = generate_num(0, rows - 1)
col_pos = generate_num(0, rows - 1)
spot = grid[row_pos][col_pos]
if not start and spot != end:
start = spot
start.make_start()
elif not end and spot != start:
end = spot
end.make_end()
elif spot != end and spot != start:
spot.make_barrier()
t.start()
for row in grid:
for spot in row:
spot.update_neighbors(grid)
algorithm(lambda: draw(win, grid, rows, width), grid, start, end)
global full_time
full_time = t.stop()
setup_config = False
run = False
pygame.QUIT
main(WIN, WIDTH)
和timing.py我的计时器class
import time
class TimerError(Exception):
"""A custom exception used to report errors in use of Timer class"""
class Timing:
def __init__(self):
self._start_time = None
def start(self):
"""Start a new timer"""
if self._start_time is not None:
raise TimerError(f"Timer is running. Use .stop() to stop it")
self._start_time = time.perf_counter()
def stop(self):
"""Stop the timer, and report the elapsed time"""
if self._start_time is None:
raise TimerError(f"Timer is not running. Use .start() to start it")
elapsed_time = time.perf_counter() - self._start_time
self._start_time = None
print(f"Elapsed time: {elapsed_time:0.4f} seconds")
return elapsed_time
编辑：
神秘的第 5 版当然是从这一行来的
full_time = t.stop()
在主循环的 4 次迭代中，您到达该行 5 次。这就是你有 5 张照片的原因。
当您使用命令导入 astar 时，您的评论非常正确
import astar
在您的 main.py 文件中，您正在执行 astar.py 末尾的 main(WIN, WIDTH)。因此导致 5 打印。
>>> for i in range(0, 4):
... print(i)
...
0
1
2
3
>>>
您的主 for 循环迭代了 4 次，每次都将一个元素插入到您的空列表中。顺便说一下，我会这样而不是繁琐的插入。
list.append(astar.full_time) # append inserts at the end of the list
我很惊讶你有 5 个格式的输出
print(f"Elapsed time: {elapsed_time:0.4f} seconds")
对了，我也想知道你为什么会有这些说法：
run = True
while run:
run = False
和一个类似的语句，其中包含一个名为 setup_config 的布尔值。您可以通过抑制 while 来获得更清晰的代码，因为它只执行一次。如果我错了或者我从你的上下文中遗漏了什么，请纠正我。
请注意，您还可以删除与传递命令相关的 ifs。
def main(win, width):
rows = 50
grid = make_grid(rows, width)
start = None
end = None
t = Timing()
draw(win, grid, rows, width)
for event in pygame.event.get():
if event.type == pygame.QUIT:
pass
if event.type == pygame.KEYDOWN:
if event.key == pygame.K_ESCAPE:
pass
for x in range(0, 800):
row_pos = generate_num(0, rows - 1)
col_pos = generate_num(0, rows - 1)
spot = grid[row_pos][col_pos]
if not start and spot != end:
start = spot
start.make_start()
elif not end and spot != start:
end = spot
end.make_end()
elif spot != end and spot != start:
spot.make_barrier()
t.start()
for row in grid:
for spot in row:
spot.update_neighbors(grid)
algorithm(lambda: draw(win, grid, rows, width), grid, start, end)
global full_time
full_time = t.stop()
pygame.QUIT
额外的打印主要来自这个 for 循环的一个令人惊讶的额外迭代
for event in pygame.event.get():
检查事件的值，通过打印它并检查那里是否有异常。
我已经构建了一个 A* 寻路算法，可以找到从 A 点到 B 点的最佳路线，有一个计时器可以开始和结束 post 算法的执行和路径是绘制的，这是解析为全局变量。所以当我 运行 算法不止一次（以获得平均时间）时它是可访问的。
全局变量被添加到列表中，除了当我 运行 算法 5 次时，只有 4 个值被添加（我可以看到 5 次被记录为算法在完成后打印时间）。当显示列表时，它总是错过第一次，如果我 运行 算法 5 次，则只有 2、3、4、5 次。这里是 main.py
import astar
import pygame
def main():
timing_list = []
WIDTH = 800
WIN = pygame.display.set_mode((WIDTH, WIDTH))
for x in range(0, 4):
astar.main(WIN, WIDTH)
timing_list.insert(x, astar.full_time)
print(timing_list)
if __name__ == "__main__":
main()
和
astar.py
from queue import PriorityQueue
from random import randint
import pygame
from timing import Timing
WIDTH = 800
WIN = pygame.display.set_mode((WIDTH, WIDTH))
pygame.display.set_caption("A* Path Finding Algorithm")
RED = (255, 0, 0)
GREEN = (0, 255, 0)
BLUE = (0, 255, 0)
YELLOW = (255, 255, 0)
WHITE = (255, 255, 255)
BLACK = (0, 0, 0)
PURPLE = (128, 0, 128)
ORANGE = (255, 165, 0)
GREY = (128, 128, 128)
TURQUOISE = (64, 224, 208)
global full_time
class Spot:
def __init__(self, row, col, width, total_rows):
self.row = row
self.col = col
self.x = row * width
self.y = col * width
self.color = WHITE
self.neighbors = []
self.width = width
self.total_rows = total_rows
def get_pos(self):
return self.row, self.col
def is_closed(self):
return self.color == RED
def is_open(self):
return self.color == GREEN
def is_barrier(self):
return self.color == BLACK
def is_start(self):
return self.color == ORANGE
def is_end(self):
return self.color == TURQUOISE
def reset(self):
self.color = WHITE
def make_start(self):
self.color = ORANGE
def make_closed(self):
self.color = RED
def make_open(self):
self.color = GREEN
def make_barrier(self):
self.color = BLACK
def make_end(self):
self.color = TURQUOISE
def make_path(self):
self.color = PURPLE
def draw(self, win):
pygame.draw.rect(win, self.color, (self.x, self.y, self.width, self.width))
def update_neighbors(self, grid):
self.neighbors = []
if self.row < self.total_rows - 1 and not grid[self.row + 1][self.col].is_barrier(): # DOWN
self.neighbors.append(grid[self.row + 1][self.col])
if self.row > 0 and not grid[self.row - 1][self.col].is_barrier(): # UP
self.neighbors.append(grid[self.row - 1][self.col])
if self.col < self.total_rows - 1 and not grid[self.row][self.col + 1].is_barrier(): # RIGHT
self.neighbors.append(grid[self.row][self.col + 1])
if self.col > 0 and not grid[self.row][self.col - 1].is_barrier(): # LEFT
self.neighbors.append(grid[self.row][self.col - 1])
def __lt__(self, other):
return False
def generate_num(x, y):
return randint(x, y)
def h(p1, p2):
x1, y1 = p1
x2, y2 = p2
return abs(x1 - x2) + abs(y1 - y2)
def reconstruct_path(came_from, current, draw):
while current in came_from:
current = came_from[current]
current.make_path()
draw()
def algorithm(draw, grid, start, end):
count = 0
open_set = PriorityQueue()
open_set.put((0, count, start))
came_from = {}
g_score = {spot: float("inf") for row in grid for spot in row}
g_score[start] = 0
f_score = {spot: float("inf") for row in grid for spot in row}
f_score[start] = h(start.get_pos(), end.get_pos())
open_set_hash = {start}
while not open_set.empty():
for event in pygame.event.get():
if event.type == pygame.QUIT:
pygame.quit()
current = open_set.get()[2]
open_set_hash.remove(current)
if current == end:
reconstruct_path(came_from, end, draw)
end.make_end()
return True
for neighbor in current.neighbors:
temp_g_score = g_score[current] + 1
if temp_g_score < g_score[neighbor]:
came_from[neighbor] = current
g_score[neighbor] = temp_g_score
f_score[neighbor] = temp_g_score + h(neighbor.get_pos(), end.get_pos())
if neighbor not in open_set_hash:
count += 1
open_set.put((f_score[neighbor], count, neighbor))
open_set_hash.add(neighbor)
neighbor.make_open()
draw()
if current != start:
current.make_closed()
return False
def make_grid(rows, width):
grid = []
gap = width // rows
for i in range(rows):
grid.append([])
for j in range(rows):
spot = Spot(i, j, gap, rows)
grid[i].append(spot)
return grid
def draw_grid(win, rows, width):
gap = width // rows
for i in range(rows):
pygame.draw.line(win, GREY, (0, i * gap), (width, i * gap))
for j in range(rows):
pygame.draw.line(win, GREY, (j * gap, 0), (j * gap, width))
def draw(win, grid, rows, width):
win.fill(WHITE)
for row in grid:
for spot in row:
spot.draw(win)
draw_grid(win, rows, width)
pygame.display.update()
def get_clicked_pos(pos, rows, width):
gap = width // rows
y, x = pos
row = y // gap
col = x // gap
return row, col
def main(win, width):
rows = 50
grid = make_grid(rows, width)
start = None
end = None
t = Timing()
run = True
setup_config = True
while run:
draw(win, grid, rows, width)
for event in pygame.event.get():
if event.type == pygame.QUIT:
run = False
setup_config = False
if event.type == pygame.KEYDOWN:
if event.key == pygame.K_ESCAPE:
run = False
setup_config = False
while setup_config:
for x in range(0, 800):
row_pos = generate_num(0, rows - 1)
col_pos = generate_num(0, rows - 1)
spot = grid[row_pos][col_pos]
if not start and spot != end:
start = spot
start.make_start()
elif not end and spot != start:
end = spot
end.make_end()
elif spot != end and spot != start:
spot.make_barrier()
t.start()
for row in grid:
for spot in row:
spot.update_neighbors(grid)
algorithm(lambda: draw(win, grid, rows, width), grid, start, end)
global full_time
full_time = t.stop()
setup_config = False
run = False
pygame.QUIT
main(WIN, WIDTH)
和timing.py我的计时器class
import time
class TimerError(Exception):
"""A custom exception used to report errors in use of Timer class"""
class Timing:
def __init__(self):
self._start_time = None
def start(self):
"""Start a new timer"""
if self._start_time is not None:
raise TimerError(f"Timer is running. Use .stop() to stop it")
self._start_time = time.perf_counter()
def stop(self):
"""Stop the timer, and report the elapsed time"""
if self._start_time is None:
raise TimerError(f"Timer is not running. Use .start() to start it")
elapsed_time = time.perf_counter() - self._start_time
self._start_time = None
print(f"Elapsed time: {elapsed_time:0.4f} seconds")
return elapsed_time
编辑：
神秘的第 5 版当然是从这一行来的
full_time = t.stop()
在主循环的 4 次迭代中，您到达该行 5 次。这就是你有 5 张照片的原因。
当您使用命令导入 astar 时，您的评论非常正确
import astar
在您的 main.py 文件中，您正在执行 astar.py 末尾的 main(WIN, WIDTH)。因此导致 5 打印。
>>> for i in range(0, 4):
... print(i)
...
0
1
2
3
>>>
您的主 for 循环迭代了 4 次，每次都将一个元素插入到您的空列表中。顺便说一下，我会这样而不是繁琐的插入。
list.append(astar.full_time) # append inserts at the end of the list
我很惊讶你有 5 个格式的输出
print(f"Elapsed time: {elapsed_time:0.4f} seconds")
对了，我也想知道你为什么会有这些说法：
run = True
while run:
run = False
和一个类似的语句，其中包含一个名为 setup_config 的布尔值。您可以通过抑制 while 来获得更清晰的代码，因为它只执行一次。如果我错了或者我从你的上下文中遗漏了什么，请纠正我。
请注意，您还可以删除与传递命令相关的 ifs。
def main(win, width):
rows = 50
grid = make_grid(rows, width)
start = None
end = None
t = Timing()
draw(win, grid, rows, width)
for event in pygame.event.get():
if event.type == pygame.QUIT:
pass
if event.type == pygame.KEYDOWN:
if event.key == pygame.K_ESCAPE:
pass
for x in range(0, 800):
row_pos = generate_num(0, rows - 1)
col_pos = generate_num(0, rows - 1)
spot = grid[row_pos][col_pos]
if not start and spot != end:
start = spot
start.make_start()
elif not end and spot != start:
end = spot
end.make_end()
elif spot != end and spot != start:
spot.make_barrier()
t.start()
for row in grid:
for spot in row:
spot.update_neighbors(grid)
algorithm(lambda: draw(win, grid, rows, width), grid, start, end)
global full_time
full_time = t.stop()
pygame.QUIT
额外的打印主要来自这个 for 循环的一个令人惊讶的额外迭代
for event in pygame.event.get():
检查事件的值，通过打印它并检查那里是否有异常。