Перечисление коллекций, которые по своей сути не являются IEnumerable? - PullRequest
Новая
       50

Перечисление коллекций, которые по своей сути не являются IEnumerable?

21 голосов
/ 29 ноября 2009

Если вы хотите рекурсивно перечислить иерархический объект, выбирая некоторые элементы на основе некоторых критериев, существует множество примеров таких методов, как «выравнивание» и последующая фильтрация с использованием Linq: например, те, что найдены здесь:

текст ссылки

Но когда вы перечисляете что-то вроде коллекции Controls формы или коллекции Nodes TreeView, я не смог использовать эти типы методов, потому что они, кажется, требуют аргумента (для метода расширения), который коллекция IEnumerable: передача в SomeForm.Controls не компилируется.

Самым полезным, что я нашел, было следующее:

текст ссылки

Что дает вам метод расширения для Control.ControlCollection с IEnumerable результатом, который вы затем можете использовать с Linq.

Я изменил приведенный выше пример, чтобы проанализировать узлы TreeView без проблем. 

public static IEnumerable<TreeNode> GetNodesRecursively(this TreeNodeCollection nodeCollection)
{
    foreach (TreeNode theNode in nodeCollection)
    {
        yield return theNode;

        if (theNode.Nodes.Count > 0)
        {
            foreach (TreeNode subNode in theNode.Nodes.GetNodesRecursively())
            {
                yield return subNode;
            }
        }
    }
}

Это код, который я пишу сейчас, используя метод расширения: 

    var theNodes = treeView1.Nodes.GetNodesRecursively();

    var filteredNodes = 
    (
        from n in theNodes
            where n.Text.Contains("1")
                select n
    ).ToList();

И я думаю, что может быть более элегантный способ сделать это, когда передаются ограничения.

Что я хочу знать, возможно ли определить такие процедуры общим образом, чтобы: во время выполнения я мог передать тип коллекции, а также фактическую коллекцию, универсальному параметру, поэтому код независимо от того, является ли это TreeNodeCollection или Controls.Collection.

Мне также было бы интересно узнать, есть ли другой способ (более дешевый? Более быстрый?), Чем тот, который показан во второй ссылке (выше), для получения TreeNodeCollection или Control.ControlCollection в форме, используемой Linq.

Комментарий Леппи о «SelectMany» в сообщении SO, связанном с первым (выше), выглядит как подсказка.

Мои эксперименты с SelectMany были: ну, назовите их "бедствия". :)

Цените любые указатели. Я потратил несколько часов, читая каждый SO-пост, который касался этих областей, и пробирался к такой экзотике, как «y-combinator». «Унизительный» опыт, я мог бы добавить:)

Ответы [ 5 ]

31 голосов
/ 29 ноября 2009

Этот код должен сделать трюк 

public static class Extensions
{
    public static IEnumerable<T> GetRecursively<T>(this IEnumerable collection,
        Func<T, IEnumerable> selector)
    {
        foreach (var item in collection.OfType<T>())
        {
            yield return item;

            IEnumerable<T> children = selector(item).GetRecursively(selector);
            foreach (var child in children)
            {
                yield return child;
            }
        }
    }
}

Вот пример того, как его использовать 

TreeView view = new TreeView();

// ...

IEnumerable<TreeNode> nodes = view.Nodes.
    .GetRecursively<TreeNode>(item => item.Nodes);

Обновление: В ответ на сообщение Эрика Липперта.

Вот значительно улучшенная версия, использующая технику, обсуждаемую в Все об итераторах . 

public static class Extensions
{
    public static IEnumerable<T> GetItems<T>(this IEnumerable collection,
        Func<T, IEnumerable> selector)
    {
        Stack<IEnumerable<T>> stack = new Stack<IEnumerable<T>>();
        stack.Push(collection.OfType<T>());

        while (stack.Count > 0)
        {
            IEnumerable<T> items = stack.Pop();
            foreach (var item in items)
            {
                yield return item;

                IEnumerable<T> children = selector(item).OfType<T>();
                stack.Push(children);
            }
        }
    }
}

Я провел простой тест производительности, используя следующую методику бенчмаркинга . Результаты говорят сами за себя. Глубина дерева оказывает лишь незначительное влияние на производительность второго решения; тогда как производительность первого решения быстро снижается, что в итоге приводит к StackOverflowException, когда глубина дерева становится слишком большой.

benchmarking

22 голосов
/ 29 ноября 2009

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

Предположим, что у рассматриваемого дерева есть всего n узлов с максимальной глубиной дерева d <= n. </p>

Во-первых, они занимают место в системном стеке в глубине дерева. Если древовидная структура очень глубокая, это может привести к перегрузке стека и падению программы. Глубина дерева d составляет O (lg n), в зависимости от коэффициента ветвления дерева. В худшем случае это совсем не ветвление - это просто связанный список, и в этом случае дерево, содержащее всего несколько сотен узлов, разрушит стек.

Во-вторых, то, что вы делаете здесь, - это создание итератора, который вызывает итератор, который вызывает итератор ... так что каждый MoveNext () на верхнем итераторе фактически выполняет цепочку вызовов, которая снова O (d) Стоимость. Если вы делаете это на каждом узле, то общая стоимость вызовов составляет O (nd), что является наихудшим случаем O (n ^ 2) и наилучшим случаем O (n lg n). Вы можете сделать лучше, чем оба; нет никаких причин, почему это не может быть линейным во времени.

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

Вы должны добавить в свой список чтения статью Уэса Дайера об этом:

https://blogs.msdn.microsoft.com/wesdyer/2007/03/23/all-about-iterators/

В конце он дает несколько хороших приемов написания рекурсивных итераторов.

2 голосов
/ 29 ноября 2009

На основе решения Мриденгрена: 

public static IEnumerable<T> GetRecursively<T>(this IEnumerable collection,
    Func<T, IEnumerable> selector,
    Func<T, bool> predicate)
{
    foreach (var item in collection.OfType<T>())
    {
        if(!predicate(item)) continue;

        yield return item;

        IEnumerable<T> children = selector(item).GetRecursively(selector, predicate);
        foreach (var child in children)
        {
            yield return child;
        }
    }
}


var theNodes = treeView1.Nodes.GetRecursively<TreeNode>(
    x => x.Nodes,
    n => n.Text.Contains("1")).ToList();

Редактировать: для BillW

2 голосов
/ 29 ноября 2009

Я не уверен насчет TreeNodes, но вы можете сделать коллекцию Controls формы IEnumerable с помощью System.Linq и, например, 

var ts = (from t in this.Controls.OfType<TextBox>
                 where t.Name.Contains("fish")
                 select t);
//Will get all the textboxes whose Names contain "fish"

Извините, что не знаю, как сделать это рекурсивным, с макушки головы.

1 голос
/ 29 ноября 2009

Полагаю, вы просите что-то подобное. 

public static IEnumerable<T> <T,TCollection> GetNodesRecursively(this TCollection nodeCollection, Func<T, TCollection> getSub)
 where T, TCollection: IEnumerable
{   
    foreach (var theNode in )
    {
        yield return theNode;
        foreach (var subNode in GetNodesRecursively(theNode, getSub))
        {
            yield return subNode;
        }
    }
}

var all_control = GetNodesRecursively(control, c=>c.Controls).ToList();
...