Promenade dans les arbres en plusieurs fils

Bonjour à tous, je souhaite partager avec le public une certaine quantité d'informations qui me semblait difficile à trouver sur Internet.

Qu'est-ce qu'un arbre, voir Wikipedia .


Fig. 1 Exemple d'arbre.

Alors, pourquoi avez-vous même besoin de parcourir l'arborescence dans plusieurs threads? Dans mon cas, c'était la nécessité de rechercher des fichiers sur le disque. Il est clair que physiquement le disque fonctionne dans un flux, mais néanmoins, la recherche de fichiers multithread peut donner une accélération, dans le cas où un flux unique recherche un fichier dans une hiérarchie à plusieurs niveaux, et le fichier souhaité se trouve dans un dossier adjacent avec un niveau. La mise en œuvre de nombreux produits commerciaux à succès est également une preuve de la pertinence de l'utilisation de la recherche multithread. Je n'exclus pas que d'autres variantes de l'application de l'algorithme soient possibles, écrivez dans les commentaires.

Pour commencer, je propose de considérer l'animation:



Que se passe-t-il ici? L'essence même de l'algorithme est que:

1. Le premier ruisseau contourne l'arbre à partir de la racine jusqu'à toute la profondeur le long du chemin «extrême gauche», c'est-à-dire se déplace toujours vers la gauche lorsque vous vous déplacez vers l'intérieur ou, en d'autres termes, sélectionne toujours le dernier nœud enfant.
2. En parallèle, le premier thread collecte tous les nœuds enfants manquants et les envoie à la file d'attente (ou à la pile) où un autre thread les emmène, la file d'attente ou la pile doit implémenter une approche multithread et l'algorithme se répète, en substituant le nœud qui vient d'être pris à la place de la racine.
   
   En fait, en général, l'algorithme ressemble à ceci (une couleur - un fil):
   

En fait, en général, l'algorithme ressemble à ceci (une couleur - un fil):

Implémentation de logiciels Java

Je donne un exemple de code qui pourrait être utile pour quelqu'un, je l'ai cherché longtemps, mais je ne l'ai pas trouvé:

import java.io.File; import java.util.concurrent.BlockingQueue; import java.util.concurrent.Executor; import java.util.concurrent.Executors; import java.util.concurrent.LinkedBlockingDeque; public class MultiThreadTreeWalker extends Thread { private static BlockingQueue<File> nodesToReview = new LinkedBlockingDeque<>(); private File f; public MultiThreadTreeWalker(File f) { this.f = f; } public MultiThreadTreeWalker() { } public static void main(String[] args) { Executor ex = Executors.newFixedThreadPool(2); MultiThreadTreeWalker mw = new MultiThreadTreeWalker(new File("C:\\")); mw.run(); for (int i = 0;i<2;i++) { ex.execute(new MultiThreadTreeWalker()); } } @Override public void run() { if (f != null) { //    reviewFileSystem(f); } else { try { while (true) { f = nodesToReview.take(); reviewFileSystem(f); } } catch (InterruptedException e) { e.printStackTrace(); } } } void reviewFileSystem(File f) { if (f == null) { return; } if (f.isFile()) { //  (+ ) System.out.println(" " + f.getName() + "   " + Thread.currentThread()); return; } File[] files = f.listFiles(); if (files.length != 0) { for (int i = 0; i < files.length - 1; i++) { nodesToReview.add(files[i]); //     } //       File last = files[files.length - 1]; reviewFileSystem(last); } } } 

Conclusion

Comme vous pouvez le voir, le multithreading en Java peut être implémenté tout simplement via BlockingQueue, une structure de données qui donne accès à plusieurs threads aux données stockées.

En général, c'est tout, bref, écrivez des commentaires sur les autres méthodes ou méthodes de traversée d'arbre qui existent, je voudrais entendre l'opinion du gourou à ce sujet. Écrivez des questions, des souhaits.

Lien vers GitHub . Il y a aussi un moteur de recherche JavaFX à proximité, si quelqu'un veut tester, je serai content.