7

我查看了一些常用工具，如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
4

5 回答 5

3

这是一个 python 问题，使用多少堆栈空间可能比多少总内存更重要。Cpython 的下限为 1000 帧，因为它与 c 调用堆栈共享其调用堆栈，而 c 调用堆栈又在大多数地方限制为 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]。

我敢肯定，有一些图表在一种搜索或另一种搜索中会做得更好。

例如，想象一个看起来像链表的图，所有顶点都在一条长链中。深度优先遍历将有一个非常高的峰值内存使用，因为它会一直递归到链中，为每个级别分配一个堆栈帧。广度优先遍历将使用更少的内存，因为它只有一个顶点和一个子节点来跟踪每一步。

现在，将其与深度 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

在这两者中，如果大多数遍历最终触及大部分图形，则深度优先使用较少的内存。

当目标靠近起始节点时，广度优先可能会更好，或者当节点数量没有很快增加时，代码中的父/子数组保持较小（例如，另一个答案提到链表是最坏的情况对于 DFS）。

如果您正在搜索的图形是空间数据，或者具有所谓的“可接受的启发式”，A* 是另一种非常好的算法： http ://en.wikipedia.org/wiki/A_star

然而，过早的优化是万恶之源。查看您要使用的实际数据；如果它适合合理的内存量，并且搜索在合理的时间内运行，那么您使用哪种算法并不重要。注意，什么是“合理的”取决于您使用它的应用程序以及将运行它的硬件上的资源量。

于 2013-03-17T04:23:15.157 回答
0

对于使用描述它的标准数据结构（BFS 的队列，DFS 的堆栈）迭代实现的任一搜索顺序，我可以构造一个使用O(n)内存的图。对于 BFS，它是一个 n-star，对于 DFS，它是一个 n-chain。我不相信它们中的任何一个都可以在一般情况下做得比这更好，因此这也给出了Omega(n)最大内存使用的下限。因此，通过有效实施每一个，它通常应该是一个清洗。

现在，如果您的输入图有一些特征使它们更倾向于这些极端之一或另一个，这可能会通知您决定在实践中使用哪个。

于 2013-03-17T05:21:57.467 回答