递归与迭代图遍历的内存利用相比

Question

我查看了一些常见的工具，比如Heapy，想要测量每种遍历方法使用的内存量，但我不确定它们给出的结果是否准确。这里有一些代码可以提供背景信息。

这段代码简单地测量图中唯一节点的数量。提供了两种遍历方法，分别是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()

我想知道这两种遍历方法count_dfs和count_bfs的总内存使用量差别有多大？人们可能会觉得dfs会比较耗内存，因为每次函数调用都会创建一个新的栈。我们怎么能测量每种遍历方法的总内存分配呢？
被注释掉的hpy语句能给出我们想要的测量结果吗？

带有连接的示例文件：

4
1 2 3
2 1 3
3 4 
4

Answer 1

要准确测量使用了多少内存其实挺难的，因为不同的系统在处理栈帧时的方法不一样。一般来说，递归算法比迭代算法使用的内存要多得多，因为每次调用新函数时，都会在栈帧中存储变量的状态。可以想象一下动态规划的解决方案和递归解决方案之间的区别。迭代实现的算法运行速度通常比递归实现快得多。

如果你真的想知道你的代码使用了多少内存，可以在像OllyDbg这样的调试器中加载你的软件，然后数一数字节。祝你编码愉快！

Answer 2

针对你的具体问题，我不确定是否会有简单的解决办法。这是因为，图的遍历所需的最高内存使用量取决于图本身的具体情况。

对于深度优先遍历，内存使用量最大的时候是算法走到最深的地方。在你的示例图中，它会遍历 1->2->3->4，并为每一层创建一个堆栈帧。所以当它到达4的时候，分配的内存是最多的。

而对于广度优先遍历，使用的内存量与每一层的节点数量加上下一层的子节点数量成正比。这些值会存储在列表中，可能比堆栈帧更有效率。在这个例子中，由于第一个节点连接到所有其他节点，所以在第一步就会立刻发生 [1]->[2,3,4]。

我相信有些图在某种遍历方式下表现会更好。

比如，想象一个像链表一样的图，所有的顶点都在一条长链上。深度优先遍历会有非常高的内存使用峰值，因为它会一直递归到链的最底部，为每一层分配一个堆栈帧。而广度优先遍历使用的内存会少得多，因为每一步只需要跟踪一个顶点和它的一个子节点。

现在，和一个深度为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) 的元组。你可以在各种图上试试看它们之间的差异。

Answer 3

这是一个关于Python的问题，可能更重要的是使用了多少栈空间，而不是总共用了多少内存。Cpython的栈帧限制比较低，最多只能有1000个帧，因为它和C语言的调用栈是共享的，而C语言的调用栈在大多数情况下限制在大约一兆字节。因此，当递归深度没有限制时，你几乎总是应该选择迭代的方法，而不是递归的方法。

_{* 其他Python的实现可能没有这个限制。Cpython和pypy的无栈版本正好具备这个特性}