0

我正在尝试开发一种反应式 DFS 实现，它可以产生不同的节点，而不需要遍历不必要的路径。树可能包含重复/相等的节点。如果一个节点已经被遍历，那么它的所有子节点也都被遍历了，因此如果我们再次遇到一个节点，我们可以停止扩展遍历。

class Traversal {
  //exposed method with understandable signature
  public IObservable<Node> DepthFirst(Node root) {
    return DepthFirstRecursive(root, new List<Node>(), new SomeStatefulHelper());
  }

  //hidden method with accumulator for cutting
  private IObservable<Node> DepthFirstRecursive(Node root, List<Node> accuFilter, SomeHelper helper) {
    return root.GetChildren().AsObservable()

      //here we cut traversal:
      .Where(n => !accuFilter.Contains(n))

      //cannot do SelectMany, because we want sequential processing:
      .Select(n => DepthFirstRecursive(n, accuFilter, helper)).Concat()
      .Concat(Observable.Return(root))

      //adding results to accumulator
      .Do(accuFilter.Add)
  }
}

class Node : IEquatable<Node> {
  public IEnumerable<Node> GetChildren(SomeHelper helper) {
    //produce child nodes
  }
  ...
}

蓄能器并不漂亮。它基本上是通过其他优雅的响应式实现编织的副作用。如何使用 Rx 摆脱它？ Observable.Distinct()不会削减它（双关语），因为它只能在链的最末端（在哪里.Do）运行。

此外，使用助手，我=>在.Where. 我不认为这个警告是相关的。是吗？我该如何摆脱它？

4

1 回答 1

0

我不认为 RX 是适合这里工作的工具。

此外，您应该使用 HashSet 来跟踪访问过的节点。
List.Contains() 迭代所有元素，因此您将引入 O(n^2) 行为。

要展平结果，最简单的方法是使用 Enumerable.SelectMany()

Func<T, IEnumerable<T>> getChildren您可以简单地使用指定如何获取相关节点类型的子节点的委托，而不是依赖额外的类来实现 GetChildren() 。

我会这样做：

    public static IEnumerable<T> DepthFirst<T>(T node, 
                                               Func<T, IEnumerable<T>> getChildren, 
                                               HashSet<T> visitedNodes)
    {
        return getChildren(node)
              .Where(visitedNodes.Add)
              .SelectMany(child => DepthFirst(child, getChildren, visitedNodes))
              .Concat(new[] { node });
    }

    public static IEnumerable<T> DepthFirst<T>(T root, 
                                               Func<T, IEnumerable<T>> getChildren) 
    {
        return DepthFirst(root, getChildren, new HashSet<T> {root});
    }
于 2013-06-14T11:00:46.743 回答