Dot.Blog

C#, XAML, Xamarin, UWP/Android/iOS

XML, arbres, LINQ et parallélisme

Traiter des données arborescentes est toujours un peu délicat car cela implique l’usage de code récursif, sorte d’épouvantail à informaticien… Pire si tout cela doit être parallélisé c’est un cauchemar pour certains ! Mais c’est oublier que ces problèmes complexes peuvent être résolus par quelques lignes de C# avec l’aide de LINQ !

Arborescences

Un arbre c’est beau. Il y a un tronc et des ramifications, les branches. Elles-mêmes se ramifient en sous-branches jusqu’à atteindre les feuilles. On oublie souvent que la partie la plus importante d’un arbre ce sont ses racines, ce qu’on en voit n’est là que pour les faire vivre Mais de notre point de vue c’est idem car si on veut on peut tout aussi bien étudier l’arborescence de son système racinaire, c’est tout aussi complexe et ramifié. A l’endroit ou à l’envers, un arbre est ramifié !

De nombreux problèmes font intervenir en informatique des structures de données arborescentes. Les créer, mais surtout les traiter (donc les parcourir) posent néanmoins des problèmes à beaucoup d’informaticiens car cela fait intervenir l’épouvantail que j’évoquais plus haut : la récursivité. Les algorithmes récursifs sont eux aussi très beaux, comme les arbres. En peu de code ils peuvent traiter des ramifications complexes. La clé étant qu’une structure arborescente est une structure “self replicating”, auto récplicative.

Vouloir la traiter et l’aborder comme une structure de données classique est une erreur qui rend le problème très difficile à résoudre. La réponse est dans l’utilisation d’un code lui-même auto réplicatif. Non pas qu’il va se démultiplié en mémoire par enchantement, mais dans le sens où son exécution va pouvoir s’auto répliquer grâce à l’utilisation de la pile qui lui servira de fil d’Ariane pour ne pas se perdre dans le labyrinthe du Minotaure !

Code et arbre

Mais voilà le problème, écrire un code capable de se comporter ainsi, de savoir balayer tous les chemins d’un arbre et de retrouver son chemin vers la sortie n’est pas un exercice mental avec lequel tout le monde est à l’aise.

Créer une arborescence est assez simple, mais la traiter l’est beaucoup moins.

Surtout de nos jours où tout traitement digne de ce nom ce doit en plus d’utiliser tous les cœurs de la machine, donc d’être multitâche, et même encore plus complexe ici : parallélisé.

Création d’arbre parallélisée

Pour faire simple car les données de test ne sont jamais très simples à trouver dans ce genre de cas nous allons choisir comme source l’arborescence d’un disque dur. C’est assez gros et diversifié pour créer un arbre bien costaud.

Nous allons créer cette structure sous la forme d’un fichier XML qui pourra ensuite être exploité soit directement en mémoire soit après été stocké sur disque.

public static XElement BuildTree(string dirName)
	{
		var di = new DirectoryInfo(dirName);
		FileInfo[] files;
		try
		{
			files = di.GetFiles();
		}
		catch { files = null; }
		var dirsize = 0L;
		if (files != null)
			Parallel.ForEach(files, current => 	dirsize += current.Length);
		DirectoryInfo[] subdirs;
		try
		{
			subdirs = di.GetDirectories();
		}
		catch { subdirs = null; }
		// each item is a "directory" having 5 attributes
		// name is the name of the folder
		// fullpath is the full path including the name of the folder
		// size is the size of all files in the folder (in bytes)
		// files is the number of files in the folder
		// subdirs is the count of possible sub directories in the folder
		var elem = new XElement("directory",
			new XAttribute("name", di.Name),
			new XAttribute("fullpath", dirName),
			new XAttribute("size", dirsize),
			new XAttribute("files", files?.Count()??0),
			new XAttribute("subdirs", subdirs?.Count()??0));
		if (subdirs != null)
			Parallel.ForEach (subdirs, dinf =>
			{
				var elemDir = BuildTree(dirName + "\\" + dinf.Name);
				elem.Add(elemDir);
			});

		return elem;
	}

La méthode ci-dessus créée un document XML en mémoire en balayant toute l’arborescence d’un disque à partir de l’emplacement spécifié qui peut être autre chose que la racine. Je vous le conseille même pour vos tests ! Sur mon portable dont le disque de 3To est loin d’être plein, le fichier qui est créé en sortie fait plusieurs Go si je pars de la racine, si votre machine n’est pas équipée généreusement de RAM vous allez tout faire sauter !

Mais armé d’un tel fichier votre disque dur (ou toute autre structure de données) n’aura plus de secret pour vous ! Grâce à LINQ il va être possible d’interroger la structure sans trop se perdre dans les méandres de la pensée récursive…

On notera au passage que la méthode de création de l’arbre exploite les extensions parallèles pour traiter l’arborescence le plus efficacement possible. Vous verrez qu’à l’exécution tous les cœurs de votre machine seront à 100%.

Le vidage sur disque de la structure en mémoire peut prendre ainsi bien plus de temps que sa création, car l’écriture du fichier XML par le Save du XDocument n’est pas parallèle…et si le disque n’est pas très rapide ça peut ramer un bon moment ne vous inquiétez pas… D’où l’intérêt de choisir un sous arbre pas trop gros pour vos tests.

La taille du fichier de sortie peut être énorme car XML est verbeux mais en plus ici nous mémorisons pour chaque fichier son path complet ce qui fait une quantité de texte phénoménale.

Voici un exemple de sortie juste pour le sous répertoire NDepend (très bel outil au passage) placé à la racine de C: :

<?xml version="1.0" encoding="UTF-8" standalone="true"?>
<!--Structure au 05/03/2018 20:43:36-->
<directories>
<directory subdirs="4" files="5" size="322725" fullpath="c:\ndepend" name="ndepend">
… (je fais court car on va retrouver ce code plus bas !)
</directory>
</directory>
</directories>

Il n’y a pas beaucoup d’imbrications dans cet exemple mais à vous de choisir quelque chose de plus gros, pour cet article cela suffira largement.

Traiter l’arbre

Un arbre se traite avec délicatesse… Et qu’y a t il de plus doux que LINQ pour ça��

Par exemple imaginons qu’on veuille connaître la liste exacte de tous les répertoires vides…

Voici un petit bout de programme qui va exploiter la séquence de création de l’arbre pour le parcourir :

        var d = DirToXml.BuildTreeDocument(@"c:\ndepend");
	//d.Save(@"C:\Temp\Test.xml");

	Console.WriteLine(d.ToString());
	Console.WriteLine(new string('-', 60));

	var q = from e in d.Descendants("directory")
			where (int)e.Attribute("files") == 0
				 && (int)e.Attribute("subdirs") == 0
			orderby (string)e.Attribute("fullpath")
			select e.Attribute("fullpath");

	Console.WriteLine("Répertoires vides");
	foreach (var element in q)
	{ Console.WriteLine(element); }
	Console.WriteLine(string.Format("{0} répertoires vides", q.Count()));

Sur l’exemple d’arbre plus haut la sortie sera :

<!--Structure au 05/03/2018 20:53:07-->
<directories>
  <directory name="ndepend" fullpath="c:\ndepend" size="322725" files="5" subdirs="4">
    <directory name="ENaxos" fullpath="c:\ndepend\ENaxos" size="0" files="0" subdirs="0" />
    <directory name="BuildProcessResources" fullpath="c:\ndepend\BuildProcessResources" size="1442" files="11" subdirs="3">
      <directory name="MSBuild" fullpath="c:\ndepend\BuildProcessResources\MSBuild" size="12166" files="2" subdirs="0" />
      <directory name="NAnt" fullpath="c:\ndepend\BuildProcessResources\NAnt" size="11227" files="2" subdirs="0" />
      <directory name="ReportXsl" fullpath="c:\ndepend\BuildProcessResources\ReportXsl" size="39285" files="2" subdirs="0" />
    </directory>
    <directory name="Lib" fullpath="c:\ndepend\Lib" size="27203256" files="38" subdirs="0" />
    <directory name="NDepend.PowerTools.SourceCode" fullpath="c:\ndepend\NDepend.PowerTools.SourceCode" size="59793" files="7" subdirs="21">
      <directory name="Base" fullpath="c:\ndepend\NDepend.PowerTools.SourceCode\Base" size="164" files="1" subdirs="0" />
      <directory name="AnalyzeAssemblyInFolder" fullpath="c:\ndepend\NDepend.PowerTools.SourceCode\AnalyzeAssemblyInFolder" size="4745" files="1" subdirs="0" />
      <directory name="APIChanges" fullpath="c:\ndepend\NDepend.PowerTools.SourceCode\APIChanges" size="10198" files="2" subdirs="0" />
      <directory name="DeadCode" fullpath="c:\ndepend\NDepend.PowerTools.SourceCode\DeadCode" size="10221" files="2" subdirs="0" />
      <directory name="DotNetFrameworkAnalysis" fullpath="c:\ndepend\NDepend.PowerTools.SourceCode\DotNetFrameworkAnalysis" size="2265" files="1" subdirs="0" />
      <directory name="CodeQueryConsole" fullpath="c:\ndepend\NDepend.PowerTools.SourceCode\CodeQueryConsole" size="75956" files="17" subdirs="0" />
      <directory name="AnalyzeCodeOnDisk" fullpath="c:\ndepend\NDepend.PowerTools.SourceCode\AnalyzeCodeOnDisk" size="3755" files="1" subdirs="0" />
      <directory name="Evolution" fullpath="c:\ndepend\NDepend.PowerTools.SourceCode\Evolution" size="4062" files="1" subdirs="0" />
      <directory name="AppWords" fullpath="c:\ndepend\NDepend.PowerTools.SourceCode\AppWords" size="16503" files="4" subdirs="0" />
      <directory name="DetectAssemblyIssues" fullpath="c:\ndepend\NDepend.PowerTools.SourceCode\DetectAssemblyIssues" size="13340" files="3" subdirs="0" />
      <directory name="bin" fullpath="c:\ndepend\NDepend.PowerTools.SourceCode\bin" size="0" files="0" subdirs="1">
        <directory name="Release" fullpath="c:\ndepend\NDepend.PowerTools.SourceCode\bin\Release" size="0" files="0" subdirs="0" />
      </directory>
      <directory name="DotNetFrameworkCoreAPIChanges" fullpath="c:\ndepend\NDepend.PowerTools.SourceCode\DotNetFrameworkCoreAPIChanges" size="4203" files="1" subdirs="0" />
      <directory name="CQL2CQLinq" fullpath="c:\ndepend\NDepend.PowerTools.SourceCode\CQL2CQLinq" size="4564" files="1" subdirs="0" />
      <directory name="Properties" fullpath="c:\ndepend\NDepend.PowerTools.SourceCode\Properties" size="1408" files="1" subdirs="0" />
      <directory name="Trend" fullpath="c:\ndepend\NDepend.PowerTools.SourceCode\Trend" size="2366" files="1" subdirs="0" />
      <directory name="SearchForDuplicateCode" fullpath="c:\ndepend\NDepend.PowerTools.SourceCode\SearchForDuplicateCode" size="29396" files="6" subdirs="0" />
      <directory name="SharedUtils" fullpath="c:\ndepend\NDepend.PowerTools.SourceCode\SharedUtils" size="29549" files="5" subdirs="0" />
      <directory name="ReviewMethodChanges" fullpath="c:\ndepend\NDepend.PowerTools.SourceCode\ReviewMethodChanges" size="2968" files="2" subdirs="0" />
      <directory name="SearchTypesByName" fullpath="c:\ndepend\NDepend.PowerTools.SourceCode\SearchTypesByName" size="15712" files="5" subdirs="0" />
      <directory name="TestDebuggerDisplay" fullpath="c:\ndepend\NDepend.PowerTools.SourceCode\TestDebuggerDisplay" size="1881" files="1" subdirs="0" />
      <directory name="obj" fullpath="c:\ndepend\NDepend.PowerTools.SourceCode\obj" size="0" files="0" subdirs="1">
        <directory name="Debug" fullpath="c:\ndepend\NDepend.PowerTools.SourceCode\obj\Debug" size="578489" files="5" subdirs="1">
          <directory name="TempPE" fullpath="c:\ndepend\NDepend.PowerTools.SourceCode\obj\Debug\TempPE" size="0" files="0" subdirs="0" />
        </directory>
      </directory>
    </directory>
  </directory>
</directories>
------------------------------------------------------------
Répertoires vides

fullpath="c:\ndepend\ENaxos"

fullpath="c:\ndepend\NDepend.PowerTools.SourceCode\bin\Release"

fullpath="c:\ndepend\NDepend.PowerTools.SourceCode\obj\Debug\TempPE"
3 répertoires vides

Mais pour aller au bout de la démarche parallèlisée je vous propose de réécrire la fin du code de cette façon :

        var q = from e in d.Descendants("directory").AsParallel()
			where (int)e.Attribute("files") == 0
				 && (int)e.Attribute("subdirs") == 0
			orderby (string)e.Attribute("fullpath")
			select e.Attribute("fullpath");

	Console.WriteLine("Répertoires vides");
	Parallel.ForEach (q, element =>  Console.WriteLine(element) );

Vous noterez ici l’utilisation de Parallel.ForEach déjà utilisé et de PLINQ, l’extension parallèle de LINQ qui se manifeste dans la requête par l’utilisation de AsParalel() sur la source de données…

Conclusion

Il n’y a pas de des grandes nouvelles explosives en informatique, il y a aussi les petites choses bien utiles qu’on doit faire et devant lesquelles on reste parfois sans idées… Créer un arbre, le sauvegarder en XML, le traiter par des requêtes LINQ, le tout parallélisé, ce n’est pas de la bombe, certes, mais c’est ce qui fait le bon code, celui qui va vite, qui est lisible et dont on peut raisonnablement être fier !

Stay Tuned !

blog comments powered by Disqus