递归与迭代图遍历中的内存利用率

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

这是一个Python问题，使用多少堆栈空间可能比多少总内存更重要。Cpython 的下限为 1000 帧，因为它与 c 调用堆栈共享其调用堆栈，而 c 调用堆栈在大多数地方又限制为 1 MB 的量级。因此，当递归深度无界时，您几乎*总是更喜欢迭代解决方案而不是递归解决方案。

_{* python 的其他实现可能没有此限制。cpython 和 pypy 的无堆栈变体具有这个确切的属性}