Плохая производительность при обрезке дерева

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

Как я уже говорил ранее, набор данных, что я работаю с тем, когда это выполняется довольно мало. Это всего лишь несколько уровней в глубину, только на одном уровне на одном уровне. Как это написано в настоящее время, медленность будет возникать на первом рекурсивном вызове на Prune, когда я вызываю list.Count(), потому что тогда выполняется оценка второго уровня иерархии (excluded.SelectMany(this.getChildren)).

Если, однако, я добавить .ToList вызов следующим образом:

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

Тогда будет происходить медленность в этой точке.

Что мне нужно сделать, чтобы сделать это быстро?

Update

После кто-то побудило меня более внимательно пересмотреть свое состояние, я понял, что эти ассоциации в hasBusinessUnitsForUser не были готовы загружены. Это была проблема.

Answer 1

Эти вызовы все лениво выполняются, и результаты не кэшируются/материализовались:

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

Даже в этом фрагменте included работает в два раза. Поскольку это рекурсивный алгоритм, может быть еще много вызовов.

Добавить вызов ToList в любую последовательность, которая может быть выполнена более одного раза.