Как я могу динамически передать условие и метод в рекурсивный метод - PullRequest
Новая
       33

Как я могу динамически передать условие и метод в рекурсивный метод

7 голосов
/ 24 октября 2011

Я хочу создать такой метод, 

public dynamic Traverse(dynamic entity, conditions, method)
{
    foreach (var propInfo in GetTraversableProperties(entity))
    {
        if (condition) method(propInfo.GetValue(etc));
        Traverse(propInfo, condition, method);
    }
    return entity;
}

Как я могу это сделать?Каков синтаксис для передачи условий и метода в качестве параметров?Кроме того, имеет ли смысл делать условия методом и проверять его возвращаемое значение?

Ответы [ 2 ]

12 голосов
/ 24 октября 2011

Ваш подход и ответ Гэри являются совершенно разумными способами переформулировать абстрактное понятие рекурсивного обхода графа объектов. Тем не менее, я вижу четыре потенциальных вопроса. Не зная вашего точного сценария, возможно, это не проблема для вас, или, возможно, вы должны рассмотреть их:

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

Во-вторых, вы предполагаете, что граф ацикличен; если график циклический, то вам, безусловно, не хватит места в стеке.

В-третьих, я не понимаю, почему алгоритм обхода возвращает объект. Почему этот метод не является недействительным? Или, если вы используете возврат в качестве накопителя для накопления значения, вычисленного путем обхода, то почему рекурсивный шаг не делает что-то с возвращенной сущностью?

В-четвертых, у вас, похоже, плохое разделение интересов. Вызывающий отвечает за определение (1) корня графа, (2) что делать с каждым узлом. Но вызываемый абонент отвечает за (3) выяснение, на какие объекты возиться. Это кажется странным для меня. Звонящий обеспечивает отправную точку; разве звонящий не должен иметь права голоса?

Обычно я решаю эту проблему следующим образом:

  • Использовать явный стек, выделенный в куче, вместо использования стека вызовов для потока управления
  • Отслеживать узлы, которые я посетил ранее, и не посещать их повторно
  • Пусть вызывающий абонент определит, когда у объекта есть перемещаемые дети. Если вызывающий объект желает, чтобы обход «снизу вверх» в базовом случае, он может вернуть пустой набор дочерних элементов.

Если бы я хотел аккумулятор, я мог бы реализовать что-то вроде этого наброска: 

static R DepthFirstGraphAccumulate<T, R>(
    T root, 
    Func<T, IEnumerable<T>> children, 
    Func<T, R, R> accumulate)
{
    var accumulator = default(R);
    var visited = new HashSet<T>();
    var stack = new Stack<T>;
    stack.Push(root);
    while(stack.Count != 0)
    {
        var current = stack.Pop();
        if (!visited.Contains(current))
        {
            visited.Add(current);
            foreach(var child in children(current))
                stack.Push(child);
            accumulator = accumulate(current, accumulator);
        }
    }
    return accumulator;
}

Так, например, если бы у меня был график целых чисел, и я хотел бы суммировать узлы, достижимые из определенного начального узла, я бы сказал: 

int total = DepthFirstGraphAccumulate<Node, int>(
    startNode, 
    node=>node.NeighbouringNodes, 
    (node, sum)=>node.Value + sum);

Однако я бы соблазнился пойти еще дальше на пути «давайте разделим наши проблемы» и скажу: эй, давайте просто напишем абстрактный traverser: 

static IEnumerable<T> DepthFirstGraphTraversal<T>(
    T root, 
    Func<T, IEnumerable<T>> children)
{
    var visited = new HashSet<T>();
    var stack = new Stack<T>;
    stack.Push(root);
    while(stack.Count != 0)
    {
        var current = stack.Pop();
        if (!visited.Contains(current))
        {
            visited.Add(current);
            foreach(var child in children(current))
                stack.Push(child);
            yield return current;
        }
    }
}

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

foreach(var node in DepthFirstGraphTraversal<Node>(startNode, n=>n.NeighbouringNodes))
     DoSomething(node);

Если бы я хотел выразить понятие «сделать что-то для каждого узла, соответствующего условию», я бы написал: 

var nodes = from node in DepthFirstGraphTraversal<Node>(startNode, n=>n.NeighbouringNodes)
            where condition(node)
            select node;
foreach(var matchingNode in nodes) DoSomething(matchingNode);
4 голосов
/ 24 октября 2011

Я думаю, что использование делегата Func для условий имеет смысл.Что касается того, как передавать методы, это снова будет использовать делегаты.Я бы сделал что-то вроде: 

public dynamic Traverse(dynamic entity, Func<dynamic, bool> conditions, Action<dynamic> method)
{
    foreach (var propInfo in GetTraversableProperties(entity))
    {
        if (conditions(entity)) method(propInfo.GetValue(etc));
        Traverse(propInfo, conditions, method);
    }
    return entity;
}

Func: http://msdn.microsoft.com/en-us/library/bb549151.aspx

Действие: http://msdn.microsoft.com/en-us/library/018hxwa8.aspx

...