树木修剪性能差

Question

我做了一个叫TreePruner的东西。它的目的是:给定一个从根级节点列表开始的层次结构，返回一个新的层次结构，其中新的根节点是满足一定条件的最高层节点。这是我的课。

public class BreadthFirstPruner<TResource>
{
    private IEnumerable<TResource> originalList;
    private IEnumerable<TResource> prunedList;
    private Func<TResource, ICollection<TResource>> getChildren;

    public BreadthFirstPruner(IEnumerable<TResource> list, Func<TResource, ICollection<TResource>> getChildren)
    {
        this.originalList = list;
        this.getChildren = getChildren;
    }

    public IEnumerable<TResource> GetPrunedTree(Func<TResource,bool> condition)
    {
        this.prunedList = new List<TResource>();
        this.Prune(this.originalList, condition);
        return this.prunedList;
    }

    private void Prune(IEnumerable<TResource> list, Func<TResource,bool> condition)
    {
        if (list.Count() == 0)
        {
            return;
        }

        var included = list.Where(condition);
        this.prunedList = this.prunedList.Union(included);
        var excluded = list.Except(included);
        this.Prune(excluded.SelectMany(this.getChildren), condition);
    }
}

这门课做的是它应该做的，但是它做得太慢了，我不知道为什么。在内存中已经存在完整层次结构的非常小的层次结构上使用了这种方法(因此不应该有linq到sql的意外)。但是，无论我多么急切或懒惰地尝试做一些事情，实际计算linq表达式结果的第一行代码最终都要花费3-4秒的时间来执行。

下面是当前正在使用剪枝器的代码：

Func<BusinessUnitLabel, ICollection<BusinessUnitLabel>> getChildren = l => l.Children;
var hierarchy = scope.ToList();
var pruner = new BreadthFirstPruner<BusinessUnitLabel>(hierarchy, getChildren);
Func<BusinessUnitLabel, bool> hasBusinessUnitsForUser = l =>
    l.BusinessUnits.SelectMany(bu => bu.Users.Select(u => u.IDGUID)).Contains(userId);
var labels = pruner.GetPrunedTree(hasBusinessUnitsForUser).ToList();

如前所述，我在执行时所使用的数据集非常小。它只有几个层次深，在大多数级别上只有一个节点。正如目前所写的，当我调用Prune时，对list.Count()的第一次递归调用将出现缓慢，因为这是计算层次结构的第二层(excluded.SelectMany(this.getChildren))的时候。

但是，如果我添加了类似于这样的.ToList调用：

var included = list.Where(condition).ToList()

那么，在这一点上就会出现慢度。

我该怎么做才能让这事进展得快些？

更新

在有人促使我更仔细地重新评估我的病情后，我意识到hasBusinessUnitsForUser中的那些关联并不是急于加载的。问题就在这里。

Answer 1

这些调用都是延迟执行的，结果没有缓存/物化：

    var included = list.Where(condition);
    this.prunedList = this.prunedList.Union(included);
    var excluded = list.Except(included);

即使在这个片段中，included也会运行两次。因为这是一个递归算法，可能会有更多的调用。

向可能多次执行的任何序列添加一个ToList调用。