7

Heapyなどの一般的なツールをいくつか調べて、各トラバーサル手法で使用されているメモリの量を測定しましたが、正しい結果が得られるかどうかはわかりません。コンテキストを提供するコードを次に示します。

このコードは、グラフ内の一意のノードの数を測定するだけです。2 つのトラバーサル手法が提供されました。count_bfsとcount_dfs

import sys
from guppy import hpy
class Graph:
    def __init__(self, key):
        self.key = key       #unique id for a vertex 
        self.connections = []
        self.visited = False 

def count_bfs(start):
    parents = [start]
    children = []
    count = 0
    while parents:
        for ind in parents:
            if not ind.visited:
                count += 1
                ind.visited = True
                for child in ind.connections:
                        children.append(child)

        parents = children
        children = []
    return count

def count_dfs(start):
    if not start.visited:
          start.visited = True
    else:
          return 0

    n = 1
    for connection in start.connections:
        n += count_dfs(connection)
    return n


def construct(file, s=1): 
    """Constructs a Graph using the adjacency matrix given in the file

    :param file: path to the file with the matrix
    :param s: starting node key. Defaults to 1

    :return start vertex of the graph
    """
    d = {}
    f = open(file,'rU')
    size = int(f.readline())
    for x in xrange(1,size+1):
        d[x] = Graph(x)
    start = d[s]
    for i in xrange(0,size):
           l = map(lambda x: int(x), f.readline().split())
           node = l[0]
           for child in l[1:]:
               d[node].connections.append(d[child])
    return start


if __name__ == "__main__":
    s = construct(sys.argv[1])
    #h = hpy()
    print(count_bfs(s))
    #print h.heap()
    s = construct(sys.argv[1])
    #h = hpy()
    print(count_dfs(s))
    #print h.heap()

2つのトラバーサル手法で合計メモリ使用率がどのような要因で異なるのかを知りたい. count_dfsそしてcount_bfs？dfs関数呼び出しごとに新しいスタックが作成されるため、費用がかかる可能性があるという直観があるかもしれません。各トラバーサル手法でのメモリ割り当ての合計はどのように測定できますか?
(コメントされた)hpyステートメントは、望ましい尺度を示していますか?

接続を含むサンプル ファイル:

4
1 2 3
2 1 3
3 4 
4
4

5 に答える 5

3

これは Python の質問です。総メモリ量よりもスタック スペースの使用量の方が重要かもしれません。Cpython は、コール スタックを c コール スタックと共有するため、1000 フレームという低い制限があります。これは、ほとんどの場所で 1 メガバイトのオーダーに制限されています。このため、再帰の深さが制限されていない場合は、ほとんど*常に再帰的なソリューションよりも反復的なソリューションを優先する必要があります。

* Python の他の実装には、この制限がない場合があります。cpython と pypy のスタックレスバリアントには、まさにこのプロパティがあります

于 2013-03-09T03:15:43.753 に答える
1

スタック フレームの実装方法はシステムによって異なるため、メモリの使用量を正確に測定することは困難です。一般に、再帰アルゴリズムは反復アルゴリズムよりもはるかに多くのメモリを使用します。これは、新しい関数呼び出しが発生するたびに、各スタック フレームがその変数の状態を格納する必要があるためです。動的計画法のソリューションと再帰的なソリューションの違いを考えてみましょう。実行時間は、再帰的なアルゴリズムよりもアルゴリズムの反復的な実装の方がはるかに高速です。

コードが使用するメモリの量を本当に知る必要がある場合は、ソフトウェアを OllyDbg ( http://www.ollydbg.de/ ) などのデバッガにロードし、バイト数を数えます。ハッピーコーディング！

于 2013-03-09T02:34:13.993 に答える
1

あなたの特定の問題について、簡単な解決策があるかどうかはわかりません。これは、グラフ トラバーサルのピーク メモリ使用量がグラフ自体の詳細に依存するためです。

深さ優先トラバーサルの場合、アルゴリズムが最も深い深さに達したときに最大の使用量が発生します。あなたの例のグラフでは、トラバースし1->2->3->4、各レベルのスタック フレームを作成します。したがって、4 にある間は、最も多くのメモリが割り当てられています。

幅優先トラバーサルの場合、使用されるメモリは、各深さのノード数と次の深さの子ノードの数に比例します。これらの値は、おそらくスタック フレームよりも効率的なリストに格納されます。この例では、最初のノードが他のすべてのノードに接続されているため、最初のステップですぐに発生し[1]->[2,3,4]ます。

いずれかの検索ではるかにうまくいくグラフがいくつかあると確信しています。

たとえば、リンクされたリストのように見えるグラフを想像してください。すべての頂点が 1 つの長いチェーンになっています。深さ優先トラバーサルは、各レベルにスタック フレームを割り当てて、チェーン全体を再帰するため、ピーク時のメモリ使用量が非常に高くなります。幅優先トラバーサルは、各ステップで追跡する 1 つの子を持つ 1 つの頂点しか持たないため、使用するメモリははるかに少なくなります。

これを深さ 2 の木であるグラフと比較してみましょう。つまり、相互に接続されていない非常に多くの子に接続されている単一のルート要素があります。深さ優先トラバーサルは、バックアップして別のブランチを試す前に 2 つのノードをトラバースするだけでよいため、特定の時点で多くのメモリを使用しません。一方、深さ優先トラバーサルは、すべての子ノードを一度にメモリに配置するため、大きなツリーの場合は問題になる可能性があります。

現在のプロファイリング コードでは、 を呼び出した時点でヒープ上のオブジェクトによって使用されているメモリのみが検出されるため、必要なピーク メモリ使用量は検出されませんheap。これは、トラバーサルの前後で同じである可能性があります。代わりに、トラバーサル関数自体にプロファイリング コードを挿入する必要があります。自分で試すためのビルド済みのパッケージが見つかりませんが、guppyこの未テストのコードは機能すると思います。

from guppy import hpy

def count_bfs(start):
    hp = hpy()
    base_mem = hpy.heap().size
    max_mem = 0
    parents = [start]
    children = []
    count = 0
    while parents:
        for ind in parents:
            if not ind.visited:
                count += 1
                ind.visited = True
                for child in ind.connections:
                        children.append(child)
        mem = hpy.heap().size - base_mem
        if mem > max_mem:
            max_mem = mem
        parents = children
        children = []
    return count, max_mem

def count_dfs(start, hp=hpy(), base_mem=None):
    if base_mem is None:
        base_mem = hp.heap().size

    if not start.visited:
          start.visited = True
    else:
          return 0, hp.heap().size - base_mem

    n = 1
    max_mem = 0
    for connection in start.connections:
        c, mem = count_dfs(connection, base_mem)
        if mem > max_mem:
            max_mem = mem
        n += c
    return n, max_mem

(count, max-memory-used)両方のトラバーサル関数がタプルを返すようになりました。さまざまなグラフで試して、違いを確認できます。

于 2013-03-11T05:19:53.280 に答える
0

2 つのうち、深さ優先は、ほとんどのトラバーサルがグラフの大部分に到達する場合、メモリの使用量が少なくなります。

幅優先は、ターゲットが開始ノードの近くにある場合、またはノードの数がすぐに上がらないため、コード内の親/子配列が小さいままである場合に適しています (たとえば、リンクされたリストを最悪のケースとして言及した別の回答)。 DFS の場合)。

検索しているグラフが空間データである場合、または「許容ヒューリスティック」として知られているものがある場合、A* はかなり優れた別のアルゴリズムです: http://en.wikipedia.org/wiki/A_star

ただし、時期尚早の最適化は諸悪の根源です。使用したい実際のデータを見てください。妥当な量のメモリに収まり、妥当な時間内に検索が実行される場合は、どのアルゴリズムを使用しても問題ありません。NB、「合理的」とは、それを使用しているアプリケーションと、それを実行するハードウェア上のリソースの量によって異なります。

于 2013-03-17T04:23:15.157 に答える
0

O(n)それを記述する標準データ構造 (BFS の場合はキュー、DFS の場合はスタック) を使用して反復的に実装された検索順序のいずれについても、メモリを簡単に使用するグラフを作成できます。BFS の場合は n スター、DFS の場合は n チェーンです。一般的なケースでそれよりもうまく機能するようにそれらのいずれかを実装できるとは思わないため、Omega(n)最大メモリ使用量の下限も与えられます。したがって、それぞれを効率的に実装すれば、通常はウォッシュする必要があります。

ここで、入力グラフにこれらの極端な値または別の値に偏る特性がある場合、実際にどちらを使用するかの決定に役立つ可能性があります。

于 2013-03-17T05:21:57.467 に答える