如何实现更新objects的依赖树?

How to implement a dependency tree of updating objects?

编辑:我不是在寻找实现,而是在寻找一些要搜索的关键字和让我入门的方法。

我正在努力生成一个依赖树,其中 child 节点由外部进程更新,要求是更新更新的 child 节点的所有 parent 节点。

示例:想象一棵这样的树:O [parent], O(l) [left child], O(r) [right child], O (ll)、O(lr)、O(rl) 和 O(rr)。 O(ll)、O(lr)、O(rl) 和 O(rr) 引用了以随机间隔更新的数据集合。

我想实施一个拉取过程,其中一个过程以特定的时间间隔检查 O 是否更新。 "Updated" 定义为在所有 child 节点更新时更新,否则仅使用该节点的缓存值(结果)。拉取进程的工作是确保在任何 child 节点未更新时更新 O。这意味着该过程需要遍历树并检查 O(ll)、O(lr)、O(rl) 和 O(rr) 是否更新。如果数据集合,即那些 child 节点引用,自上次更新那些 child 节点后更新,那么那些 child 节点需要根据更改的数据集合进行更新。如果数据集合更新,因此 child 个节点 O(ll)、O(lr)、O(rl) 和 O(rr) 也更新,这意味着 O(l) 和 O( r) 也需要更新,随后 O 也将被更新。每个 child 节点都输入到其 parent 节点。

这里的复杂性在于每个 child 节点在不同的树之间共享,这意味着,一棵树的 child 节点也可以是另一棵树的任何 child 节点。此结构的目的是避免 re-calculation 已经是 up-to-date 的 child 节点。如果不同的树实现了一个 child 节点,其功能(功能和参数化)与已经存在的 child 节点完全相同,那么 child 节点将被共享。

我对这个结构的设计以及如何实现它感到困惑。我还没有提供代码,因为我坚持设计思维过程。本质上每个 child 都是函数并且依赖于相关函数本身。

让我疑惑的是,C# 是否提供了修饰方法的能力,类 以简化对节点是否更新的检查。惰性评估是否也在此过程中发挥作用?

我建议定义一个 class 来跟踪其 children 是否已通过标志更新,例如一个名为 Dirty 的布尔值。树中的节点可以通过引发事件告诉其 parents 变脏。当一个节点 returns 它自己的值时,它应该检查标志并仅在需要时重新计算它自己的值。重新计算时,它应该检查每个 child 的值,然后每个

将检查自己的脏标志,依此类推。

class Node<T> 
{
    event EventHandler Changed;

    private T _value;
    private bool _dirty = true;
    private List<Node<T>> _children = new List<Node<T>>();

    public void AddChild(Node<T> child)
    {
        child.Changed += (s,e) => _dirty = true;
        _children.Add(child);
    }

    protected void OnChanged()
    {
        if (Changed != null) Changed(this, new EventArgs());
    }

    public T Value
    {
        get
        {
            if (_dirty)
            {
                this.Value = ComputeValueFromChildren();
                _dirty = false;
            }
            return _value;
        }
        set
        {
            _value = value;
            OnChanged();
        }
    }

    private T ComputeValueFromChildren()
    {
        var values = _children.Select( child => child.Value );
        //Return the new value based on the children
    }
}