我阅读了很多有关垃圾收集的资源,他们在其中解释了不同的算法。但是,我没有找到任何解释图对象表示的解释。
我的想法很简单:一个面向图,其中顶点表示分配的内存块(在堆上),并且表示所有者关系的边缘。示例:考虑2个内存块m1和m2,如果m1包含对m2内部一个块的引用,则添加一条边(m1,m2)。这些边使用m1包含的对m2的引用数(此处仅为1)加权。最后,我得到了一个表示堆栈的“虚拟”内存顶点,称为M0。不能从M0到达的每个Mi都被垃圾收集。
好的,现在考虑您要向图形添加一个内存块。如果我们将顶点保留在集合内,则添加内存块的复杂度应为O(log(n))。
第一个问题:我们能做得更好吗?
同上删除。
现在,我被要求将此算法与C++(shared_ptr)中的引用计数机制一起使用。首先,引用计数器是否与顶点的度数无关?
其次,关键思想是最好的引用计数器(O(1)删除/添加)与最好的垃圾收集器算法(清理引用周期)一起使用,但是添加/删除对象中每个节点的开销却很大图不是有点效率不高吗?
在已知的垃圾收集器(java / C#/…)中添加/删除的复杂性是什么?
谢谢 !
最佳答案
好吧...你的前提不对了。已知的垃圾收集器实际上并不能维护很多状态,每个对象最多只能有几个位,并且只有某种结构,仅此而已。取而代之的是,它们在每次收集过程中建立某种状态,并在过程结束时使其死亡。这样,他们几乎不需要(甚至不需要)所有权关系的检测。