c# - 树木修剪性能不佳

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);
    }
}

类(class)按预期进行，但速度很慢，我不明白为什么。我已经在非常小的层次结构上使用了它，其中完整的层次结构已经在内存中(因此应该没有 linq-to-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();

如前所述，执行此操作时我使用的数据集非常小。它只有几层深，大多数层上只有一个节点。正如目前所写的那样，当我调用 list.Count() 时，第一次递归调用 Prune 时会出现缓慢，因为那是正在评估层次结构的第二级 (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 调用添加到任何可能被执行多次的序列。