Как использовать LINQ для выбора всех потомков составного объекта

Как я могу улучшить ComponentTraversal.GetDescendants() с помощью LINQ?

Вопрос

public static class ComponentTraversal
{
    public static IEnumerable<Component> GetDescendants(this Composite composite)
    {
        //How can I do this better using LINQ?
        IList<Component> descendants = new Component[]{};
        foreach(var child in composite.Children)
        {
            descendants.Add(child);
            if(child is Composite)
            {
                descendants.AddRange((child as Composite).GetDescendants());
            }
        }
        return descendants;
    }
}
public class Component
{
    public string Name { get; set; }
}
public class Composite: Component
{
    public IEnumerable<Component> Children { get; set; }
}
public class Leaf: Component
{
    public object Value { get; set; }
}

Отвечать

Я отредактировал ответ Криса, чтобы предоставить общий метод расширения, который я добавил в свою общую библиотеку. Я вижу, что это полезно и для других людей, так что вот оно:

    public static IEnumerable<T> GetDescendants<T>(this T component, Func<T,bool> isComposite, Func<T,IEnumerable<T>> getCompositeChildren)
    {
        var children = getCompositeChildren(component);
        return children
            .Where(isComposite)
            .SelectMany(x => x.GetDescendants(isComposite, getCompositeChildren))
            .Concat(children);
    }

Спасибо Крис!

Также,

Пожалуйста, посмотрите ответ Люка на http://blogs.msdn.com/b/wesdyer/archive/2007/03/23/all-about-iterators.aspx . Его ответ дает лучший способ подойти к этой проблеме в целом, но я не выбрал его, потому что это не был прямой ответ на мой вопрос.


person smartcaveman    schedule 10.03.2011    source источник
comment
Если это работает сейчас, зачем менять? Просто потому, что Linq выглядит лучше? Или вы ожидаете прироста производительности? Лично я бы не стал менять метод работы только по этим причинам, поэтому лучше очень субъективно.   -  person Bazzz    schedule 10.03.2011
comment
@Bazzz, в каждом дочернем композите я создаю новый массив. Я надеюсь, что есть более экономичный способ, и есть смысл использовать LINQ. Я также мог бы захотеть сделать что-то подобное с IQueryable, и в этом случае LINQ определенно принесет выигрыш в производительности. Однако самая большая причина, по которой я хочу знать, как это сделать в LINQ, заключается в том, что я еще не смог этого понять.   -  person smartcaveman    schedule 10.03.2011


Ответы (4)


var result = composite.Children.OfType<Composite>().SelectMany(child => child.GetDescendants()).Concat(composite.Children);
return result.ToList();

При переводе с империтивного синтаксиса на LINQ обычно довольно легко выполнять перевод по одному шагу за раз. Вот как это работает:

  1. Это зацикливание на композите.Children, так что это будет коллекция, к которой мы применим LINQ.
  2. В цикле происходят две основные операции, поэтому давайте выполним одну из них за раз.
  3. Оператор «если» выполняет фильтр. Обычно мы использовали бы «Где» для выполнения фильтра, но в этом случае фильтр основан на типе. В LINQ для этого встроена функция OfType.
  4. Для каждого дочернего композита мы хотим рекурсивно вызывать GetDescendants и добавлять результаты в один список. Всякий раз, когда мы хотим преобразовать элемент во что-то другое, мы используем либо Select, либо SelectMany. Поскольку мы хотим преобразовать каждый элемент в список и объединить их все вместе, мы используем SelectMany.
  5. Наконец, чтобы добавить в составной файл component.Children, мы объединяем эти результаты в конец.
person Chris Pitman    schedule 10.03.2011
comment
Помните, что вложенные итераторы могут привести к огромным потерям производительности. См. раздел «Стоимость итераторов» в блогах. .msdn.com/b/wesdyer/archive/2007/03/23/ для получения дополнительной информации. - person LukeH; 10.03.2011
comment
@LukeH, этот код, по крайней мере, не страдает от связанных проблем, потому что он особенно глубоко вложен и сводит результаты к списку на каждом шаге. - person Chris Pitman; 10.03.2011
comment
В вопросе я поставил общую версию метода расширения. Я просто немного изменил ваш код. Для будущих пользователей может быть полезно, если вы включите его в конце своего ответа (поскольку они не ожидают увидеть его в вопросе). Большое спасибо за твою помощь. - person smartcaveman; 10.03.2011

Часто есть веские причины избегать (1) рекурсивных вызовов методов, (2) вложенных итераторов и (3) множества одноразовых распределений. Этот метод позволяет избежать всех этих потенциальных ловушек:

public static IEnumerable<Component> GetDescendants(this Composite composite)
{
    var stack = new Stack<Component>();
    do
    {
        if (composite != null)
        {
            // this will currently yield the children in reverse order
            // use "composite.Children.Reverse()" to maintain original order
            foreach (var child in composite.Children)
            {
                stack.Push(child);
            }
        }

        if (stack.Count == 0)
            break;

        Component component = stack.Pop();
        yield return component;

        composite = component as Composite;
    } while (true);
}

И вот общий эквивалент:

public static IEnumerable<T> GetDescendants<T>(this T component,
    Func<T, bool> hasChildren, Func<T, IEnumerable<T>> getChildren)
{
    var stack = new Stack<T>();
    do
    {
        if (hasChildren(component))
        {
            // this will currently yield the children in reverse order
            // use "composite.Children.Reverse()" to maintain original order
            // or let the "getChildren" delegate handle the ordering
            foreach (var child in getChildren(component))
            {
                stack.Push(child);
            }
        }

        if (stack.Count == 0)
            break;

        component = stack.Pop();
        yield return component;
    } while (true);
}
person LukeH    schedule 10.03.2011
comment
+1, спасибо за ваш ответ. Я обновил вопрос, чтобы включить примечание об этом. Вы, вероятно, предложили лучший подход к решению, но я не выбрал вас, потому что это не был ответ на фактический вопрос, который я разместил. - person smartcaveman; 10.03.2011
comment
@smartcaveman: Достаточно справедливо, хотя часто необходимо написать метод расширения и добавить его в свою библиотеку инструментов, а не пытаться изменить встроенные методы LINQ в соответствии с вашими требованиями. Например, с общей версией моего ответа вы можете сделать что-то вроде var descendents = rootComponent.GetDescendents(x => x is Composite, x => ((Composite)x).Children);. - person LukeH; 10.03.2011
comment
Я бы использовал ваш метод расширения с реализациями IEnumerable‹T›, но у него есть недостаток в том, что он несовместим с IQueryable‹T› (по этой причине иногда имеет смысл сгибать встроенные методы LINQ — чтобы быть совместимыми с существующими поставщиками LINQ). - person smartcaveman; 10.03.2011

Я не знаю, как лучше, но я думаю, что это выполняет ту же логику:

public static IEnumerable<Component> GetDescendants(this Composite composite)
{
    return composite.Children
                .Concat(composite.Children
                            .Where(x => x is Composite)
                            .SelectMany(x => x.GetDescendants())
                );
}

Это может быть короче, но в том, что у вас есть, нет ничего плохого. Как я сказал выше, это должно выполнять то же самое, и я сомневаюсь, что производительность функции улучшится.

person diceguyd30    schedule 10.03.2011
comment
Есть небольшое важное отличие: этот метод использует отложенное выполнение и оплачивает стоимость выполнения только по мере повторения структуры. Если всю структуру не нужно исследовать (например, мы можем закоротить, когда найдем результат), то в этом есть свои преимущества. - person Chris Pitman; 10.03.2011
comment
Остерегайтесь, однако, что вложенные итераторы могут потенциально привести к огромным потерям производительности. См. раздел «Стоимость итераторов» в блогах. .msdn.com/b/wesdyer/archive/2007/03/23/ для получения дополнительной информации. - person LukeH; 10.03.2011

Это хороший пример, когда вы можете захотеть реализовать итератор. Это имеет преимущество ленивых вычислений в немного более читаемом синтаксисе. Кроме того, если вам нужно добавить дополнительную пользовательскую логику, эта форма более расширяема.

 public static IEnumerable<Component> GetDescendants(this Composite composite)
    {
        foreach(var child in composite.Children)
        {
            yield return child;
            if(!(child is Composite))
               continue;

            foreach (var subChild in ((Composite)child).GetDescendants())
               yield return subChild;
        }
    }
person cordialgerm    schedule 10.03.2011
comment
Помните, что вложенные итераторы могут привести к огромным потерям производительности. См. раздел «Стоимость итераторов» в блогах. .msdn.com/b/wesdyer/archive/2007/03/23/ для получения дополнительной информации. - person LukeH; 10.03.2011