DFS(深さ優先探索)のコードを書いていて、main()関数内で処理する場合、グローバル名前空間で処理するよりもメモリ使用量が増えていることに気づきました。
競技プログラミングのあるテストケースでメモリ制限が256MBのとき、main()のものだとMLE(>256MB)だったのが括弧を外すと215MBとなりました。
関数内でローカルに処理するほうが実行時間が早くなるのは知っていたのですが、メモリに関しては調べても良い文献が出てきません。
どなたか理由をご存知ありませんか?
提出 #7024392 - AtCoder Typical Contest 001 (MLE)
Python
1# ATC001A - DFS 2import sys 3input = sys.stdin.readline 4sys.setrecursionlimit(10 ** 6) 5 6def main(): 7 def dfs(h: int, w: int) -> None: 8 if (h, w) == goal: 9 print("Yes") 10 exit() 11 for dx, dy in dxy: 12 x, y = h + dx, w + dy 13 if 0 <= x < H and 0 <= y < W and F[x][y] != "#": 14 F[x][y] = "#" 15 dfs(x, y) 16 17 H, W = tuple(map(int, input().rstrip().split())) 18 F = list(list(input().rstrip()) for _ in range(H)) 19 dxy = [(1, 0), (0, 1), (-1, 0), (0, -1)] 20 flg = 0 21 for i in range(H): 22 for j in range(W): 23 if F[i][j] == "s": 24 start = i, j 25 flg += 1 26 elif F[i][j] == "g": 27 goal = i, j 28 flg += 1 29 if flg == 2: 30 break 31 dfs(*start) 32 print("No") 33 34 35if __name__ == "__main__": 36 main()
提出 #7024438 - AtCoder Typical Contest 001 (AC)
Python
1# ATC001A - DFS 2import sys 3input = sys.stdin.readline 4sys.setrecursionlimit(10 ** 6) 5 6def dfs(h: int, w: int) -> None: 7 if (h, w) == goal: 8 print("Yes") 9 exit() 10 for dx, dy in dxy: 11 x, y = h + dx, w + dy 12 if 0 <= x < H and 0 <= y < W and F[x][y] != "#": 13 F[x][y] = "#" 14 dfs(x, y) 15 16H, W = tuple(map(int, input().rstrip().split())) 17F = list(list(input().rstrip()) for _ in range(H)) 18dxy = [(1, 0), (0, 1), (-1, 0), (0, -1)] 19flg = 0 20for i in range(H): 21 for j in range(W): 22 if F[i][j] == "s": 23 start = i, j 24 flg += 1 25 elif F[i][j] == "g": 26 goal = i, j 27 flg += 1 28 if flg == 2: 29 break 30dfs(*start) 31print("No")
追記
提出結果のスクリーンショットですが、軽いものを除けばほとんどのケースでグローバル空間に直接書いたほうがメモリ使用量が少なくなっています。
MLEになったものを含め、偶然の結果ではないと思うのですが...
(左がmain(), 右がグローバルのものです)
回答3件
あなたの回答
tips
プレビュー
バッドをするには、ログインかつ
こちらの条件を満たす必要があります。