相关疑难解决方法(0)

检测有向图中所有周期的最有效算法是什么？

我有一个有向图表示需要执行的作业计划,作业是节点,依赖是边缘.我需要检测此图中循环的错误情况,从而导致循环依赖.

根据我的理解,如果没有其他东西"指向"该对象,Java中的垃圾收集会清除一些对象.

我的问题是,如果我们有这样的事情会发生什么:

class Node {
    public object value;
    public Node next;
    public Node(object o, Node n) { value = 0; next = n;}
}

//...some code
{
    Node a = new Node("a", null), 
         b = new Node("b", a), 
         c = new Node("c", b);
    a.next = c;
} //end of scope
//...other code

a,b和c应该是垃圾收集,但它们都被其他对象引用.

Java垃圾收集如何处理这个问题？(或者它只是一个内存消耗？)

确定链表是否有循环的最佳(暂停)算法是什么？

[编辑]对时间和空间的渐近复杂性的分析将是甜蜜的,因此可以更好地比较答案.

[编辑]原始问题没有解决超过1的节点,但有一些关于它的讨论.这个问题更像是"在有向图中检测周期的最佳算法".

我的问题是为什么python使用引用计数和gc的标记和扫描？为什么不只是标记和扫描？

我最初的猜测是,使用引用计数可以轻松删除非循环引用的对象,这可能会加速标记和扫描并立即获得内存.不知道我的猜测是否正确？

有什么想法吗？

非常感谢.

C++ 11引入了引用计数的智能指针std::shared_ptr.作为引用计数,这些指针无法自动回收循环数据结构.但是,可以自动收集参考周期,例如Python和PHP.为了将此技术与垃圾收集区分开来,问题的其余部分将其称为循环中断.

鉴于似乎没有为C++添加等效功能的建议,是否有一个根本原因,为什么类似于已经部署在其他语言中的循环断路器不适用std::shared_ptr？

请注意,这个问题不能归结为"为什么没有GC for C++",这已经被问过了.C++ GC通常是指一个自动管理所有动态分配对象的系统,通常使用某种形式的Boehm保守收集器实现.有人指出,这样的收集器不适合RAII.由于垃圾收集器主要管理内存,甚至可能在内存不足之前就被调用,并且C++析构函数管理其他资源,依赖于GC来运行析构函数会在最坏情况下引入非确定性和资源不足.它还指出,在存在更明确和可预测的智能指针的情况下,完全不需要GC.

但是,基于库的智能指针循环断路器(类似于引用计数解释器使用的循环断路器)与通用GC有重要区别:

• 它只关心通过管理的对象shared_ptr.这些对象已经参与共享所有权,因此必须处理延迟的析构函数调用,其确切的时间取决于所有权结构.
• 由于其范围有限,循环断路器不关心破坏或减慢Boehm GC的模式,例如指针掩蔽或包含偶尔指针的巨大不透明堆块.
• 它可以选择加入,比如std::enable_shared_from_this.不使用它的对象不必为控制块中的额外空间付费以保存循环断路器元数据.
• 循环断路器不需要全面的"根"对象列表,这在C++中很难获得.与标记扫描GC不同,它会查找所有活动对象并丢弃其余对象,而循环断路器仅遍历可形成循环的对象.在现有实现中,类型需要以函数的形式提供帮助,该函数枚举对可以参与循环的其他对象的引用(直接或间接).
• 它依赖于常规的"当引用计数降至零时破坏"语义来破坏循环垃圾.一旦确定了一个循环,就会要求参与其中的对象清除其强大的引用,例如通过调用reset().这足以打破循环并自动销毁对象.要求对象提供并清除其强力引用(根据要求),确保循环断路器不会破坏封装.

缺乏自动循环中断的建议表明该想法因实际或哲学原因而被拒绝.我很好奇原因是什么.为了完整起见,这里有一些可能的反对意见:

• "它会引入循环shared_ptr对象的非确定性破坏." 如果程序员控制了循环断路器的调用,那么它就不是非确定性的.此外,一旦被调用,循环断路器的行为将是可预测的 - 它将破坏所有当前已知的循环.这类似于shared_ptr析构函数在引用计数降至零后如何销毁基础对象,尽管这可能会导致"非确定性"级联的进一步破坏.

• "就像任何其他形式的垃圾收集一样,循环断路器会在程序执行中引入暂停." 实现此功能的运行时的经验表明,暂停是最小的,因为GC只处理循环垃圾,所有其他对象都通过引用计数回收.如果永远不会自动调用循环检测器,则循环断路器的"暂停"可能是运行它的可预测结果,类似于破坏大型std::vector运行大量析构函数的方法.(在Python中,循环gc是自动运行的,但有一些API可以在不需要它的代码段暂时禁用它.稍后重新启用GC将获取同时创建的所有循环垃圾.)

• "循环断路器是不必要的,因为循环不是那么频繁,可以很容易地避免使用std::weak_ptr." 事实上,循环很容易在许多简单的数据结构中出现 - 例如,一个树,其中孩子有一个指向父项的后向指针,或一个双向链表.在某些情况下,复杂系统中的异质对象之间的循环仅偶尔与某些数据模式形成,并且难以预测和避免.在某些情况下,用弱变量替换哪个指针远非明显.