شجرة المشي في مواضيع متعددة

مرحباً بالجميع ، أريد أن أشارك الجمهور كمية معينة من المعلومات ، والتي بدا لي أنه من الصعب العثور عليها على الإنترنت.

ما هي الشجرة ، انظر ويكيبيديا .


الشكل 1 مثال على شجرة.

لذا ، لماذا تحتاج حتى لاجتياز الشجرة في خيوط متعددة؟ في حالتي ، كانت هناك حاجة للبحث عن الملفات الموجودة على القرص. من الواضح أن القرص يعمل فعليًا في دفق واحد ، ولكن مع ذلك ، يمكن أن يوفر البحث عن ملفات متعددة الخيوط تسارعًا ، في حالة قيام دفق واحد بالبحث عن ملف في تسلسل هرمي متعدد المستويات ، ويقع الملف المطلوب في مجلد مجاور بمستوى واحد. والدليل أيضًا على أهمية استخدام البحث متعدد مؤشرات الترابط هو تنفيذه في العديد من المنتجات التجارية الناجحة. أنا لا أستبعد أن المتغيرات الأخرى لتطبيق الخوارزمية ممكنة ، اكتب في التعليقات.

بادئ ذي بدء ، أقترح النظر في الرسوم المتحركة:



ما الذي يحدث هنا؟ جوهر الخوارزمية كله هو:

1. يتجاوز التيار الأول الشجرة التي تبدأ من الجذر إلى العمق بأكمله على طول المسار "أقصى اليسار" ، أي ينتقل دائمًا إلى اليسار عند الانتقال إلى الداخل ، أو بمعنى آخر ، يحدد دائمًا العقدة الفرعية الأخيرة.
2. بالتوازي مع ذلك ، يجمع مؤشر الترابط الأول جميع العقد الفرعية المفقودة ويرسلها إلى قائمة الانتظار (أو إلى المجموعة) حيث يأخذها مؤشر ترابط آخر ، ويجب أن تقوم قائمة الانتظار أو المكدس بتنفيذ نهج متعدد الخيوط ، وتكرر الخوارزمية ، مع استبدال العقدة التي تم التقاطها للتو بدلاً من الجذر.
   
   في الواقع ، بشكل عام ، تبدو الخوارزمية هكذا (لون واحد - خيط واحد):
   

في الواقع ، بشكل عام ، تبدو الخوارزمية هكذا (لون واحد - خيط واحد):

تنفيذ برنامج جافا

أعطي مثالاً على الكود الذي قد يكون مفيدًا لشخص ما ، لقد بحثت عنه لفترة طويلة ، لكنني لم أجده:

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

استنتاج

كما ترى ، يمكن تنفيذ تعدد العمليات في Java ببساطة شديدة من خلال BlockingQueue ، وهي بنية بيانات توفر الوصول إلى عدة مؤشرات ترابط إلى البيانات المخزنة.

بشكل عام ، هذا كله ، باختصار ، يكتب تعليقات حول الأساليب والطرق الأخرى لاجتياز الأشجار ، أود أن أسمع رأي المعلم حول هذه المسألة. اكتب أسئلة ، رغبات.

رابط إلى جيثب . يوجد أيضًا محرك بحث JavaFX قريب ، إذا كان هناك من يريد الاختبار ، فسوف أكون سعيدًا فقط.