4

これらの関数は両方とも、本質的に同じ方法で同じもの (関連付けられたコラッツ シーケンスの長さが n 以下になるような整数の数) を計算します。唯一の違いは、前者はセットのみを使用するのに対し、後者はセットとリストの両方を使用することです。

2 つ目は (少なくとも Python 3.2 の IDLE で) メモリ リークを起こしますが、1 つ目はそうではありません。その理由はわかりません。私はいくつかの「トリック」（delステートメントの追加など）を試しましたが、何も役に立たないようです（驚くことではありません。これらのトリックは役に立たないはずです）。

何が起こっているのかを理解するのを手伝ってくれる人に感謝します。

コードをテストする場合は、おそらくn55 ～ 65 の範囲の値を使用する必要があります。75 を超えると、ほぼ確実に (完全に予想される) メモリ エラーが発生します。

def disk(n):
    """Uses sets for explored, current and to_explore. Does not leak."""
    explored = set()
    current = {1}
    for i in range(n):
        to_explore = set()
        for x in current:
            if not (x-1) % 3 and ((x-1)//3) % 2 and not ((x-1)//3) in explored:
                to_explore.add((x-1)//3)
            if not 2*x in explored:
                to_explore.add(2*x)
        explored.update(current)
        current = to_explore
    return len(explored)

def disk_2(n):
    """Does exactly the same thing, but Uses a set for explored and lists for
        current and to_explore. 
       Leaks (like a sieve :))
    """
    explored = set()
    current = [1]
    for i in range(n):
        to_explore = []
        for x in current:
            if not (x-1) % 3 and ((x-1)//3) % 2 and not ((x-1)//3) in explored:
                to_explore.append((x-1)//3)
            if not 2*x in explored:
                to_explore.append(2*x)
        explored.update(current)
        current = to_explore
    return len(explored)

EDIT : これは、インタプリタのインタラクティブ モード (IDLE なし) を使用する場合にも発生しますが、ターミナルからスクリプトを直接実行する場合には発生しません (その場合、メモリ使用量は、関数が返された後、またはすぐに通常に戻ります)。への明示的な呼び出しがあるためgc.collect())。

4

3 に答える 3

1

CPythonは、アリーナと呼ばれる 256 KiB ブロックで管理する 4 つの KiB プールから小さなオブジェクト(obmalloc.c、3.2.3) を割り当てます。各アクティブ プールのブロック サイズは、8 バイトから 256 バイトまで、8 刻みで固定されています。たとえば、14 バイトのオブジェクトは、ブロック サイズが 16 バイトの最初に使用可能なプールから割り当てられます。

mmap を使用する代わりにアリーナがヒープに割り当てられている場合 (これはmalloptM_MMAP_THRESHOLDによって調整可能です)、潜在的な問題があります。ヒープは、1 つのプールの 1 つのブロックが割り当てられている限り解放されない、割り当てられた最高のアリーナを下回ることができません。オブジェクトに (CPython はメモリ内でオブジェクトをフロートしません)。

上記を考えると、関数の次のバージョンはおそらく問題を解決するはずです。return len(explored)この行を次の 3 行に置き換えます。

    result = len(explored)
    del i, x, to_explore, current, explored
    return result + 0

コンテナーと参照されているすべてのオブジェクトの割り当てを解除した後 (アリーナをシステムに解放した後)、これはint式で new を返しますresult + 0。最初の結果オブジェクトへの参照がある限り、ヒープは縮小できません。この場合、関数が戻ると自動的に割り当てが解除されます。

「プラス 0」ステップなしでこれをインタラクティブにテストする場合は、REPL (読み取り、評価、印刷、ループ) が疑似変数「_」を介してアクセス可能な最後の結果への参照を保持していることを思い出してください。

Python 3.3 では、オブジェクト アロケータが変更され、利用可能な場合は Arenas に匿名の mmapを使用するようになったため、これは問題になりません。(オブジェクト アロケータの上限も、64 ビット プラットフォームに対応するために 512 バイトに引き上げられましたが、ここでは重要ではありません。)

手動ガベージ コレクションに関しては、追跡されたコンテナ オブジェクトの完全なコレクションを行いますが、組み込みタイプ (フレーム、メソッド、フロートなど) によって維持されるオブジェクトのフリーリストgc.collect()もクリアします。PyList_ClearFreeListPython 3.3 では、リスト ( )、dicts ( PyDict_ClearFreeList)、およびセット ( ) で使用されるフリーリストをクリアする API 関数が追加されましたPySet_ClearFreeList。フリーリストをそのまま保持したい場合は、 を使用しますgc.collect(1)。

于 2012-11-18T20:01:48.500 に答える
0

リークするのではないかと思いますが、ガベージコレクションがまだ開始されていないため、使用されるメモリが増え続けているに違いありません。これは、外部ループのすべてのラウンドで、前の現在のリストがガベージコレクションに使用できるようになりますが、いつでもガベージコレクションが行われないためです。

さらに、ガベージコレクションされた場合でも、メモリは通常OSに解放されないため、現在使用されているヒープサイズを取得するには、Pythonメソッドを使用する必要があります。

すべての外部ループの反復の最後にガベージコレクションを追加すると、Pythonがそれなしでヒープとガベージコレクションを正確に処理する方法に応じて、メモリ使用量が少し減るかどうかがわかります。

于 2012-11-17T16:08:50.640 に答える
0

メモリリークはありません。Linux上のプロセスは、終了するまでOSにメモリを解放しません。したがって、たとえばで表示される統計は、top上昇するだけです。

同じまたはより小さいサイズのジョブを実行した後、PythonがOSからより多くのメモリを取得し、ガベージであるはずのオブジェクトに使用していたメモリを再利用できた場合にのみ、メモリリークが発生します。集めました。

于 2012-11-17T17:25:57.053 に答える