补全：从根出发标记

👁️ 2 人浏览 💬 0 人评论 ❤️ 添加收藏

（这一节用一个自造的小堆 Heap 模拟运行时：alloc(名) 造对象，link(持有者, 名) 让持有者引用它（持有者 None 表示「根」，比如一个变量），unlink 解除引用；计数归零就 free，free 会连带解除它对别人的引用。freed 记录释放顺序。）

补全 reachable(h, roots)：从 roots（名字列表）出发沿 refs 走，交回能走到的对象集合（含根）；再补 garbage(h, roots)：堆里存在但走不到的对象，按名字排序。用它找出引用计数漏掉的环。

提交你的答案

请登录后提交答案。

去登录

← 补全：释放的连锁补全：把 VM 的环境当根 →

更多题目

代码编辑器

语言： Ctrl + Enter 运行

class Heap:
    """一个只有引用计数的小堆：obj 是名字，refs[obj] 是它引用的对象，count[obj] 是有几个地方引用它。"""

def __init__(self):
        self.count, self.refs, self.freed = {}, {}, []

def alloc(self, name):
        self.count[name] = 0
        self.refs[name] = []

def link(self, holder, name):
        if holder is not None:
            self.refs[holder].append(name)
        self.count[name] += 1

def unlink(self, holder, name):
        if holder is not None:
            self.refs[holder].remove(name)
        self.count[name] -= 1
        if self.count[name] == 0:
            self.free(name)

def free(self, name):
        self.freed.append(name)
        for child in list(self.refs[name]):
            self.unlink(name, child)
        del self.count[name]
        del self.refs[name]

def reachable(h, roots):
    # TODO
    return set()

def garbage(h, roots):
    # TODO
    return []

h = Heap()
for n in ("a", "b", "c", "d"):
    h.alloc(n)
h.link("a", "b")
h.link("b", "a")
h.link(None, "c")
h.link("c", "d")
print(str(h.count["a"]) + "," + str(h.count["b"]) + "/" + ",".join(sorted(reachable(h, ["c"]))) + "/" + ",".join(garbage(h, ["c"])))

本次输入：

输出：

👩‍🏫

AI

💬 题目评论

补全：从根出发标记

更多题目

全部评论