質問をすることでしか得られない、回答やアドバイスがある。

15分調べてもわからないことは、質問しよう!

ただいまの
回答率

88.81%

グローバルとmain()関数内で処理する場合のメモリ使用量の差

解決済

回答 3

投稿 編集

  • 評価
  • クリップ 4
  • VIEW 1,361

solzard

score 102

DFS(深さ優先探索)のコードを書いていて、main()関数内で処理する場合、グローバル名前空間で処理するよりもメモリ使用量が増えていることに気づきました。
競技プログラミングのあるテストケースでメモリ制限が256MBのとき、main()のものだとMLE(>256MB)だったのが括弧を外すと215MBとなりました。
関数内でローカルに処理するほうが実行時間が早くなるのは知っていたのですが、メモリに関しては調べても良い文献が出てきません。
どなたか理由をご存知ありませんか?

提出 #7024392 - AtCoder Typical Contest 001 (MLE)

# ATC001A - DFS
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 6)

def main():
    def dfs(h: int, w: int) -> None:
        if (h, w) == goal:
            print("Yes")
            exit()
        for dx, dy in dxy:
            x, y = h + dx, w + dy
            if 0 <= x < H and 0 <= y < W and F[x][y] != "#":
                F[x][y] = "#"
                dfs(x, y)

    H, W = tuple(map(int, input().rstrip().split()))
    F = list(list(input().rstrip()) for _ in range(H))
    dxy = [(1, 0), (0, 1), (-1, 0), (0, -1)]
    flg = 0
    for i in range(H):
        for j in range(W):
            if F[i][j] == "s":
                start = i, j
                flg += 1
            elif F[i][j] == "g":
                goal = i, j
                flg += 1
            if flg == 2:
                break
    dfs(*start)
    print("No")


if __name__ == "__main__":
    main()

提出 #7024438 - AtCoder Typical Contest 001 (AC)

# ATC001A - DFS
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 6)

def dfs(h: int, w: int) -> None:
    if (h, w) == goal:
        print("Yes")
        exit()
    for dx, dy in dxy:
        x, y = h + dx, w + dy
        if 0 <= x < H and 0 <= y < W and F[x][y] != "#":
            F[x][y] = "#"
            dfs(x, y)

H, W = tuple(map(int, input().rstrip().split()))
F = list(list(input().rstrip()) for _ in range(H))
dxy = [(1, 0), (0, 1), (-1, 0), (0, -1)]
flg = 0
for i in range(H):
    for j in range(W):
        if F[i][j] == "s":
            start = i, j
            flg += 1
        elif F[i][j] == "g":
            goal = i, j
            flg += 1
        if flg == 2:
            break
dfs(*start)
print("No")

追記

提出結果のスクリーンショットですが、軽いものを除けばほとんどのケースでグローバル空間に直接書いたほうがメモリ使用量が少なくなっています。
MLEになったものを含め、偶然の結果ではないと思うのですが...
(左がmain(), 右がグローバルのものです)
イメージ説明
イメージ説明

  • 気になる質問をクリップする

    クリップした質問は、後からいつでもマイページで確認できます。

    またクリップした質問に回答があった際、通知やメールを受け取ることができます。

    クリップを取り消します

  • 良い質問の評価を上げる

    以下のような質問は評価を上げましょう

    • 質問内容が明確
    • 自分も答えを知りたい
    • 質問者以外のユーザにも役立つ

    評価が高い質問は、TOPページの「注目」タブのフィードに表示されやすくなります。

    質問の評価を上げたことを取り消します

  • 評価を下げられる数の上限に達しました

    評価を下げることができません

    • 1日5回まで評価を下げられます
    • 1日に1ユーザに対して2回まで評価を下げられます

    質問の評価を下げる

    teratailでは下記のような質問を「具体的に困っていることがない質問」、「サイトポリシーに違反する質問」と定義し、推奨していません。

    • プログラミングに関係のない質問
    • やってほしいことだけを記載した丸投げの質問
    • 問題・課題が含まれていない質問
    • 意図的に内容が抹消された質問
    • 過去に投稿した質問と同じ内容の質問
    • 広告と受け取られるような投稿

    評価が下がると、TOPページの「アクティブ」「注目」タブのフィードに表示されにくくなります。

    質問の評価を下げたことを取り消します

    この機能は開放されていません

    評価を下げる条件を満たしてません

    評価を下げる理由を選択してください

    詳細な説明はこちら

    上記に当てはまらず、質問内容が明確になっていない質問には「情報の追加・修正依頼」機能からコメントをしてください。

    質問の評価を下げる機能の利用条件

    この機能を利用するためには、以下の事項を行う必要があります。

回答 3

+4

注意:ここに書いてあることはすべて推測・憶測・個人的な感覚に基づく情報です

まず、main()ありとmain()なしの以下の2つのコードでは、速度に2倍近くの差が出ます。また一般論ですが、速度を出したいときには高速な記憶域をじゃぶじゃぶ使う、記憶域を節約したいときにはCPUをぶんぶん振り回す、というセオリーがコンピュータプログラムにはあると思います。


環境:Python 3.7.0 (v3.7.0:1bf9cc5093, Jun 27 2018, 04:59:51) [MSC v.1914 64 bit (AMD64)]

# main()あり:速い
from time import perf_counter

def main():
    a = 0
    t = perf_counter()
    for _ in range(10 ** 8):
        a += 1
    print("%.03f sec" % (perf_counter() - t))

main()
# main()なし:遅い
from time import perf_counter

a = 0
t = perf_counter()
for _ in range(10 ** 8):
    a += 1
print("%.03f sec" % (perf_counter() - t))

そして記憶域という観点から考えた上記の2つのコードの違いは、main()の名前空間です。main()の名前空間分、記憶域を多く使うことによってmain()ありのコードは速度が出るようになったと考えることができます。

さて、これらの前提を踏まえた上で質問のmain()ありのdfs関数を見てみると、dfs関数はmain関数の内部関数、かつ再起しながら関数の外側の変数を参照するという、うまく言えないですが名前空間的なじゃぶじゃぶ感が否めません。dfs関数が再起していくなかで「たぶん」名前空間が膨れ上がっているんじゃなかろうかと思います。

(駄目だ、時間を掛けたのに上手く論理を展開できない。。。力不足です。)

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

checkベストアンサー

+2

推測でしかありませんが、上の方は関数内関数になっているため、普通の関数が実行される時に必要な(ローカル変数用の)メモリの他に、もう1つ"外の関数"への(あるいは"外の関数"のローカル変数の辞書への?)参照が保持されるのが、地味に効いているのではないでしょうか?

傍証として、グローバル変数への参照を一切持たないトップレベル関数として実装するとMLEがでませんが、

# これは通る
import sys

sys.setrecursionlimit(10 ** 6)


def dfs(h: int, w: int, goal, dxy, H, W, F) -> None:
    if (h, w) == goal:
        print("Yes")
        sys.exit()
    for dx, dy in dxy:
        x, y = h + dx, w + dy
        if 0 <= x < H and 0 <= y < W and F[x][y] != "#":
            F[x][y] = "#"
            dfs(x, y, goal, dxy, H, W, F)


def main():
    H, W = tuple(map(int, input().rstrip().split()))
    F = list(list(input().rstrip()) for _ in range(H))
    dxy = [(1, 0), (0, 1), (-1, 0), (0, -1)]
    flg = 0
    for i in range(H):
        for j in range(W):
            if F[i][j] == "s":
                start = i, j
                flg += 1
            elif F[i][j] == "g":
                goal = i, j
                flg += 1
            if flg == 2:
                break
    dfs(start[0], start[1], goal, dxy, H, W, F)
    print("No")


if __name__ == "__main__":
    main()

これを関数内関数にするとそれだけで(つまり、"外の関数"の変数を一切参照していないのでクロージャではないただの関数内関数であるにも関わらず)MLEになります。

# これはMLE
import sys

sys.setrecursionlimit(10 ** 6)


def main():
    def dfs(h: int, w: int, goal, dxy, H, W, F) -> None:
        if (h, w) == goal:
            print("Yes")
            sys.exit()
        for dx, dy in dxy:
            x, y = h + dx, w + dy
            if 0 <= x < H and 0 <= y < W and F[x][y] != "#":
                F[x][y] = "#"
                dfs(x, y, goal, dxy, H, W, F)

    H, W = tuple(map(int, input().rstrip().split()))
    F = list(list(input().rstrip()) for _ in range(H))
    dxy = [(1, 0), (0, 1), (-1, 0), (0, -1)]
    flg = 0
    for i in range(H):
        for j in range(W):
            if F[i][j] == "s":
                start = i, j
                flg += 1
            elif F[i][j] == "g":
                goal = i, j
                flg += 1
            if flg == 2:
                break
    dfs(start[0], start[1], goal, dxy, H, W, F)
    print("No")


if __name__ == "__main__":
    main()

投稿

編集

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2019/08/22 11:36

    ありがとうございます。
    quiquiさんの予想が最も頷けるものだったので、ベストアンサーにしました。

    キャンセル

+1

元々がギリギリすぎるというだけでは?

あまり細かく検証していませんが、GCが走るタイミング次第では下のコードでも215MBでは走らなくてエラーになるとか、そんなパターンな気がします。

投稿

編集

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2019/08/20 15:20

    確かにメモリ制限が厳しいのは事実なのですが、追記の画像の通り、処理が重めのケースでは軒並みメモリ使用量に差が出ています。
    今後のためにも、その理由が知りたいです。
    よろしくお願いします

    キャンセル

  • 2019/08/20 18:42

    理屈の上では、そんな大きな差は生じないはずです。単純に私が見落としている可能性もありますが(わかった方は回答していただけると幸いです)。
    処理系内部のメモリ管理の最適化の話とかになってしまうと、正直お手上げなので、わからないかもしれません。

    キャンセル

  • 2019/08/20 18:44

    あと、関係ないとは思うけど、exitはプログラム中では呼ぶべきではないとされます。
    グローバルで書いた方はsys.exitする、mainで書いた方はreturnとかでいいでしょう。
    exitする瞬間に送出された例外がスタックフレームを膨れ上がらせるみたいな妄想もしたけど、さすがにないか。

    キャンセル

15分調べてもわからないことは、teratailで質問しよう!

  • ただいまの回答率 88.81%
  • 質問をまとめることで、思考を整理して素早く解決
  • テンプレート機能で、簡単に質問をまとめられる

関連した質問

同じタグがついた質問を見る