0

编辑：我不是在寻找实现，而只是在寻找一些要搜索的关键字和让我开始的方法。

我正在努力生成一个依赖树，其中子节点由外部进程更新，并且要求更新已更新子节点的所有父节点。

示例：想象这样一棵树：O [父]、O(l) [左子]、O(r) [右子]、O(ll)、O(lr)、O(rl) 和 O( rr）。O(ll)、O(lr)、O(rl) 和 O(rr) 引用了以随机间隔更新的数据集合）。

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

这里的复杂性在于每个子节点在不同的树之间共享，这意味着一棵树的子节点也可以是另一棵树的任何子节点。这种结构的目的是避免在子节点已经是最新的时候重新计算它。如果不同的树实现具有与现有子节点完全相同的功能（函数和参数化）的子节点，则共享子节点。

我坚持这种结构的设计以及如何实施它。我还没有提供代码，因为我被设计思维过程困住了。本质上，每个孩子都是函数，并且依赖于依赖函数本身。

让我想知道的是，C# 是否提供了装饰方法和类的能力，以简化对节点是否更新的检查。惰性评估在这个过程中是否也起作用？

4

1 回答 1

1

我建议定义一个类来跟踪其子项是否已通过标志更新，例如名为 的布尔值Dirty。树中的节点可以通过引发事件来告诉其父节点变脏。当节点返回自己的值时，它应该检查标志并仅在需要时重新计算自己的值。重新计算时，它应该检查每个孩子的值，然后每个孩子都会检查自己的脏标志，以此类推。

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
    }
}
于 2019-06-18T02:40:38.113 回答