Traversée d’arbres parallèles en C #

Le moyen le plus direct serait de créer une Task pour chaque nœud enfant, puis d’attendre chacun d’entre eux:

 public void Traverse(Node root) { if (node.Property == someValue) DoSomething(node); var tasks = new List(); 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 est assez légère, donc en créer beaucoup fonctionne assez bien. Mais ils ont des frais généraux, donc faire quelque chose de plus compliqué, comme avoir quelques tâches partageant une queue, sera probablement plus rapide. Si c’est ce que vous allez faire, n’oubliez pas que la queue vide ne signifie pas que tout le travail est terminé. Les classes de l’espace de noms System.Collections.Concurrent seront utiles si vous y êtes allé.

EDIT: En raison de la forme de l’arbre (la racine compte environ 500 enfants), le traitement du premier niveau en parallèle devrait donner de bonnes performances:

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

Étant donné que la traversée de l’arbre est extrêmement rapide, que les appels à Children sont atomiques et que c’est la nature coûteuse des delegates DoSomething qui doit être exécutée en parallèle, voici mon sharepoint vue sur la solution.

J’ai commencé avec l’idée qu’il me fallait une fonction qui prenne un nœud en paramètre, crée une tâche qui exécute DoSomething , s’appelle de manière récursive pour créer des tâches pour tous les nœuds enfants et renvoie enfin une tâche qui attend toutes les tâches internes. tâches à accomplir.

C’est ici:

 Func 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 => { }); }; 

Il suffit de l’appeler et d’attendre la fin de la traversée:

 createTask(root).Wait(); 

J’ai testé cela en créant une arborescence de nœuds avec 500 enfants de la racine avec 14 niveaux, avec 1 ou 2 enfants ultérieurs par nœud. Cela m’a donné un total de 319 501 nœuds.

J’ai créé une méthode DoSomething qui a effectué un travail – for (var i = 0; i < 100000 ; i++) { }; - puis a exécuté le code ci-dessus et l'a comparé au traitement du même arbre en série.

La version parallèle prenait 5 151 ms. La version séquentielle 13 746 ms.

J'ai également effectué un test où j'ai réduit le nombre de nœuds à 3 196 et augmenté le temps de traitement de DoSomething de 100 fois. Le TPL reprend très intelligemment son exécution séquentielle si ses tâches s’achèvent rapidement, ce qui allonge le temps de traitement et rend le code exécuté avec davantage de parallélisme.

Maintenant, la version parallèle a pris 3 203 ms. La version séquentielle a pris 11 581 ms. Et, si je createTask(root) que la fonction createTask(root) sans attendre son achèvement, il ne lui faudrait que 126 ms. Cela signifie que l’arbre est parcouru très rapidement et il serait alors logique de verrouiller l’arbre pendant le parcours et de le déverrouiller pendant le traitement.

J'espère que ça aide.

Il se peut que je manque quelque chose, mais je ne vois pas du tout la nécessité. Le while est juste de s’assurer que vous parcourez chaque noeud.

Au lieu de cela, appelez simplement votre fonction de manière récursive pour chaque nœud de l’arbre.

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

modifier: bien sûr, l’alternative, si vous préférez traiter horizontalement plutôt que verticalement et que votre opération onéreuse est DoSomething, est d’abord de faire la Traverse .

 public IEnumerable 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(Traverse(n), n => DoSomething(n)); 

En supposant que vous ayez p processeurs, vous ferez peut-être une opération Parallel.For sur root.Children avec p partitions. Chacune de celles-ci effectuerait le parcours traditionnel à un seul thread sur les sous-arbres, comparerait et, plutôt que DoSomething , mettrait en queue un délégué dans DoSomething dans une queue simultanée. Si la dissortingbution est fondamentalement aléatoire et équilibrée et que la traversée ne concerne que la traversée / la mise en queue, cette partie prend 1 / p ème temps. De plus, traversal s’épuiserait probablement avant que tous les DoSomethings ne s’exécutent, vous pouvez donc avoir p consommateurs (exécuteurs de DoSomething ) vous donnant une exécution parallèle maximale, en supposant que toutes ces opérations sont indépendantes.

Avec cette partition naïve sur le nombre d’enfants racine avec des sous-arbres dissortingbués de manière aléatoire, la traversée elle-même sera rapide. Avec vos consommateurs approximativement alloués par processeur, vous obtenez également une action DoSomething en parallèle maximale.

Peut-être qu’utiliser une liste ou un tableau au lieu d’une queue pourrait aider. Utilisez également une autre liste / masortingce pour renseigner les prochains nœuds à visiter. De toute façon, vous ne traiterez pas cette liste tant que vous n’aurez pas fini de traiter toute la largeur. Quelque chose comme ça:

 List todoList = new List(); 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 nextList = new ThreadSafeList(); //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; // eg do somehting, get childrenNodesToWorkOnNext, etc. // add any child nodes that need to be processed next // eg nextList.add(childrenNodesToWorkOnNext); }); // done with parallel processing by here so use the next todo list todoList = nextList; )