破坏链表对 Python 的垃圾收集器有帮助吗？

Question

我在想，当我有机会的时候，我是否应该在 Python 中分解一个单向链表，当我不再需要它时，或者我是否不应该为它烦恼.

列表示例：

class Link:
    def __init__(self, next=None):
        self.next = next


L = Link(Link(Link(Link())))

断开链接：

def break_(link):
    if link is not None:
        break_(link.next)
        link.next = None  # link broken

# application
break_(L)

树示例：

class Node:
    def __init__(self, l=None, r=None):
        self.l = l
        self.r = r

T = \
Node(
    Node(
        Node(), 
        Node()
    ),
    Node(
        Node(), 
        Node()
    ),
)

断开链接：

def break_(node):
    if node is not None:
        break_(node.l)
        break_(node.r)
        node.l = None  # link broken
        node.r = None  # link broken
        
# application
break_(T)

基本上，我想知道的是，在这种情况下编写代码的性能最佳方式是什么。 GC 准备好处理大型链接结构了吗？它不需要运行可能很长的带计数器的 DFS 来确定哪些对象可以被释放吗？打破链接并给 GC 一堆零引用的松散对象不是更简单吗？

我可以对此进行基准测试，但我正在寻找解释（最好来自 Karl），如果有的话。谢谢。

Answer 1

您可以在 class 中添加一个 __del__ 方法来查看对象何时将被清理：

class Node:
    def __init__(self, name, l=None, r=None):
        self.name = name
        self.l = l
        self.r = r

    def __del__(self):
        print(f'__del__ {self.name}')


T = \
Node('0',
    Node('0L',
        Node('0LL'), 
        Node('0LR'),
    ),
    Node('0R',
        Node('0RL'), 
        Node('0RR'),
    ),
)
del T  # decreases the reference count of T by 1

del T发生的事情是T引用的对象的引用计数减1。在这种情况下，恰好引用计数达到0。CPython知道这一点因为它存储了每个对象的引用计数。当一个对象的引用计数达到 0 时，该对象将被标记为清理。此清理发生在将控制权交还给用户代码之前。所以对于上面的例子来说，意味着T原来引用的对象被立即清理了。这首先调用 __del__ 然后调用相应的 C 代码进行清理。这依次通过对象的实例字典，并将存储在那里的每个其他对象的引用计数减少 1。如果另一个对象的引用计数在该过程中达到 0，它也被标记为清理。然后重复此过程，直到没有对象被标记为要清理并且控制权交还给主循环。

这是示例的输出：

__del__ 0
__del__ 0L
__del__ 0LL
__del__ 0LR
__del__ 0R
__del__ 0RL
__del__ 0RR

如上所述，当 0 被清理时，它引用的所有其他对象的引用计数都会减少 1（即 0L 和 0R）并被清理为好吧，如果引用计数达到 0。

如果您通过将相应的实例属性设置为 None 来手动断开列表的链接，这会增加额外的开销，因为它必须实际修改内存中的所有这些对象（更新它们的实例字典）。达到 0 的子对象的引用计数在这里更像是一个副产品。另请注意，由于 clean 函数首先进入深度，因此清理顺序发生了变化：

def clean(node):
    if node is not None:
        clean(node.l)
        clean(node.r)
        node.l = None  # this updates the object in memory
        node.r = None

clean(T)

产生

__del__ 0LL
__del__ 0LR
__del__ 0RL
__del__ 0RR
__del__ 0L
__del__ 0R
__del__ 0

破坏链表对 Python 的垃圾收集器有帮助吗？

Does breaking a linked list help Python's garbage collector?

python

garbage-collection

linked-list