python - 通过一道超越时间限制的竞赛题来了解 Python 的速度

Question

最近一直在做一些竞赛题。特别是这个:

https://open.kattis.com/problems/knightjump

问题的简要说明:

You are given a two dimensional (square) chess board of size N (1-based indexing). Some of the cells on this board are ‘.’ denoting an empty cell. Some of the cells on this board are ‘#’ denoting a blocked cell, which you are not allowed to visit. Exactly one of the cells on this board is ‘K’ denoting the initial position of the knight. Determine the minimum number of steps required for the Knight to reach cell (1,1) while avoiding cells with ‘#’ in the path.

我知道这是一个简单的 BFS 问题，并编写了以下代码来解决它:

from collections import deque
from sys import stdin

dirs = ((2,1), (2,-1), (-2,1), (-2,-1), (1,2), (1,-2), (-1,2), (-1,-2))

N = int(stdin.readline())
q = deque()
mat = [list(str(stdin.readline())) for _ in range(N)]
for i in range(N):
    for j in range(N):
        if mat[i][j] == "K":
            inX, inY = i+1, j+1
            break

q.append((inX,inY,0))
flag = False
visited = [[0]*N for _ in range(N)]
while q:
    ix,iy, moves = q.popleft()
    visited[ix-1][iy-1] = 1
    if (ix,iy) == (1,1):
        print(moves)
        flag = True
        break
    
    for d in dirs:
        dx,dy = d
        if 1 <= ix + dx < N+1 and 1 <= iy + dy < N+1 and mat[ix+dx-1][iy+dy-1] != "#" and visited[ix+dx-1][iy+dy-1] == 0:
            q.append((ix+dx,iy+dy, moves+1))
    
if not flag:
    print(-1)

我生成的所有测试数据都给出了正确答案，但在某些情况下我在网站上收到时间限制错误(并且在所有其他情况下更正)。输入限制为 N <= 100。我知道 C++ 更快，但我希望利用这个问题来了解为什么我的解决方案超时，但许多基于类似概念的 Python 解决方案执行速度很快，并希望能教我一些东西关于我不知道的 Python 细节和 bolt 。例如 - 我在某人的 Github 上找到了这个解决方案:

from collections import deque


n = int(input())
grid = [list(input()) for _ in range(n)]
for i in range(n):
    for j in range(n):
        if grid[i][j] == 'K':
            k_i, k_j = i, j
            break
visited = [[0 for x in range(n)] for y in range(n)]

# time complexity is number of configs (n^2) multiplied by
# work per configs (iterate through 8 deltas)
def k_jumps(i, j):
    q = deque()
    q.append((0, i, j))
    visited[i][j] = 1
    valid = False
    while len(q) > 0:
        d, i, j = q.popleft()
        if (i,j) == (0,0):
            print(d)
            valid = True
            break

        deltas = {(-2, 1), (-2, -1), (1, 2), (1, -2), (-1, 2), (2, 1), (2, -1), (-1, -2)} 
        for delta in deltas:
            di, dj = delta
            if 0 <= i + di < n and 0 <= j + dj < n and visited[i+di][j+dj] == 0 and grid[i+di][j+dj] != '#':
                visited[i+di][j+dj] = 1
                q.append((d+1, i+di, j+dj))
    if not valid:
        print(-1)
            
k_jumps(k_i, k_j)

(感谢用户 Case Pleog)。

从表面上看，解决方案是相同的 (BFS) - 但是第二个解决方案运行时间为 0.07 秒，而我的解决方案超时时间超过 1 秒。

虽然我们的解决方案之间存在一些细微差异，但我看不出有什么可以解释如此大的时间差异。我已经对我的代码进行了一些更改以查看这是否是问题所在，例如行:

if 1 <= ix + dx < N+1 and 1 <= iy + dy < N+1 and mat[ix+dx-1][iy+dy-1] != "#" and visited[ix+dx-1][iy+dy-1] == 0:

确实加快了速度，就像我之前使用的那样:

if min(point) > 0 and max(point) < N+1 and mat[point[0]+dx-1][point[1]+dy-1] != "#" and visited[point[0]+dx-1][point[1]+dy-1] == 0:

其中 point 是由 ix,iy 组成的元组。任何建议将不胜感激 - 我想更多地了解是什么导致时差大于 10 倍。这只是一个爱好，所以我的一些代码可能有业余的怪癖/低效，希望我能解释一下。谢谢!

Answer 1

当你执行 q.append((ix+dx,iy+dy, moves +1))，否则您可能会将同一个坐标多次放入队列中。