Параллельный обход дерева в С#

Ответ 1

Самый прямой способ - создать Task для каждого дочернего элемента node, а затем дождаться их всех:

public void Traverse(Node root)
{
    if (node.Property == someValue)
        DoSomething(node);

    var tasks = new List<Task>();

    foreach (var node in node.Children)
    {
        // tmp is necessary because of the way closures close over loop variables
        var tmp = node;
        tasks.Add(Task.Factory.StartNew(() => Traverse(tmp)));
    }

    Task.WaitAll(tasks.ToArray());
}

Task довольно легкая, поэтому создание многих из них работает достаточно хорошо. Но у них есть некоторые накладные расходы, поэтому делать что-то более сложное, например, иметь несколько задач, которые разделяют очередь, вероятно, будет быстрее. Если это так, как вы собираетесь идти, не забывайте, что пустая очередь не означает, что вся работа выполнена. Классы из пространства имен System.Collections.Concurrent будут полезны, если вы пошли этим путем.

РЕДАКТИРОВАТЬ: Из-за формы дерева (корень имеет около 500 детей), обработка только первого уровня параллельно должна обеспечивать хорошую производительность:

public void Traverse(Node root, bool parallel = true)
{
    if (node.Property == someValue)
        DoSomething(node);

    if (parallel)
    {
        Parallel.ForEach(node.Children, node =>
        {
            Traverse(node, false);
        });
    }
    else
    {
        foreach (var node in node.Children)
        {
            Traverse(node, false);
        }
    }
}

Ответ 2

Мне может быть что-то не хватает, но я не вижу необходимости в while вообще. while просто гарантирует, что вы будете перебирать все node.

Вместо этого просто вызовите вашу функцию рекурсивно для каждого node в дереве.

public void Traverse(Node root)
{         
    if (root.Property = someValue) DoSomething(node);    
    Parallel.ForEach<Node>(root.Children, node => Traverse(node));
} 

edit: конечно, альтернатива, если вы предпочитаете обрабатывать горизонтально, а не вертикально, а ваша дорогостоящая операция - DoSomething, - сначала выполнить Traverse.

public IEnumerable<Node> Traverse(Node root)
{
    // return all the nodes on this level first, before recurring
    foreach (var node in root.Children)
    {
        if (node.Property == someValue)
            yield return node;
    }

    // next check children of each node
    foreach (var node in root.Children)
    {
        var children = Traverse(node);
        foreach (var child in children)
        {
            yield return child;
        }
    }
}

Parallel.ForEach<Node>(Traverse(n), n => DoSomething(n));

Ответ 3

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

Я начал с идеи, что мне нужна функция, которая принимает node как параметр, создает задачу, которая выполняет DoSomething, рекурсивно вызывает себя для создания задач для всех дочерних узлов и, наконец, возвращает задачу который ждет выполнения всех внутренних задач.

Вот он:

Func<Node, Task> createTask = null;
createTask = n =>
{
    var nt = Task.Factory.StartNew(() =>
    {
        if (n.Property == someValue)
            DoSomething(n);
    });
    var nts = (new [] { nt, })
        .Concat(n.Children.Select(cn => createTask(cn)))
        .ToArray();

    return Task.Factory.ContinueWhenAll(nts, ts => { });
};

Все, что требуется для вызова и ожидания завершения обхода:

createTask(root).Wait();

Я проверил это, создав дерево узлов с 500 дочерними элементами из корня с 14 уровнями, с 1 или 2 последующими детьми на node. Это дало мне 319 501 узел.

Я создал метод DoSomething, который выполнил некоторую работу - for (var i = 0; i < 100000 ; i++) { }; - и затем выполнил вышеуказанный код и сравнил его с обработкой одного и того же дерева последовательно.

Параллельная версия заняла 5,151 мс. Последовательная версия 13,746 мс.

Я также выполнил тест, в котором я уменьшил количество узлов до 3,196 и увеличил время обработки для DoSomething на 100x. TPL очень умно возвращается к выполнению последовательно, если его задачи выполняются быстро, поэтому удлинение времени обработки заставит код работать с большим количеством parallelism.

Теперь параллельная версия заняла 3,203 мс. Последовательная версия заняла 11 581 мс. И, если я только вызвал функцию createTask(root), не дожидаясь ее завершения, потребовалось всего 126 мс. Это означает, что дерево проходит очень быстро, и тогда имеет смысл блокировать дерево во время обхода и разблокировать его при обработке.

Надеюсь, это поможет.

Ответ 4

Предполагая, что у вас есть p-процессоры, возможно, вы выполняете Parallel.For над root.Children с p-разделами. Каждый из них будет выполнять традиционный однопоточный траверс по поддеревьям, сравнивать и, а не DoSomething, помещает делегата в DoSomething в параллельную очередь. Если распределение в основном случайное и сбалансированное, и поскольку обход только обходит/обходит, эта часть занимает 1/pth времени. Кроме того, обход, скорее всего, исчерпает себя, прежде чем все DoSomethings будут выполняться, поэтому вы могли бы иметь p-пользователей (исполнителей DoSomething), давая вам максимальное параллельное выполнение, предполагая, что все эти операции независимы.

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

Ответ 5

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

List<Node> todoList = new List<Node>();
todoList.Add(node);
while (todoList.Count > 0)
{
    // we'll be adding next nodes to process to this list so it needs to be thread-safe
    // or just sync access to a non-threadsafe list
    // if you know approx how many nodes you expect, you can pre-size the list
    ThreadSafeList<Node> nextList = new ThreadSafeList<Node>();  

    //todoList is readonly/static so can cache Count in simple variable
    int maxIndex  =  todoList.Count-1;
    // process todoList in parallel
    Parallel.For(0, maxIndex, i =>
    {
        // if list reads are thread-safe then no need to sync, otherwise sync
        Node x = todoList[i];

        //process x;
        // e.g. do somehting, get childrenNodesToWorkOnNext, etc.

        // add any child nodes that need to be processed next
        // e.g. nextList.add(childrenNodesToWorkOnNext);
    });

   // done with parallel processing by here so use the next todo list
   todoList = nextList;
)