Tree walk di banyak utas

Halo semuanya, saya ingin berbagi dengan publik sejumlah informasi, yang menurut saya sulit ditemukan di Internet.

Apa itu pohon, lihat Wikipedia .


1 Contoh pohon.

Jadi, mengapa Anda bahkan perlu melintasi pohon itu dalam banyak utas? Dalam kasus saya, itu adalah kebutuhan untuk mencari file pada disk. Jelas bahwa secara fisik disk bekerja dalam satu aliran, tetapi bagaimanapun, pencarian file multi-threaded dapat memberikan percepatan, dalam kasus ketika aliran tunggal mencari file dalam hierarki multi-level, dan file yang diinginkan terletak di folder yang berdekatan dengan satu level. Juga bukti relevansi menggunakan pencarian multithreaded adalah penerapannya di banyak produk komersial yang sukses. Saya tidak mengecualikan bahwa varian lain dari aplikasi algoritma dimungkinkan, tulis di komentar.

Untuk mulai dengan, saya mengusulkan untuk mempertimbangkan animasi:



Apa yang sedang terjadi di sini? Inti dari algoritma ini adalah:

1. Aliran pertama melewati pohon mulai dari akar ke seluruh kedalaman di sepanjang jalan "kiri ekstrim", yaitu selalu bergerak ke kiri saat bergerak ke dalam, atau dengan kata lain selalu memilih simpul anak terakhir.
2. Secara paralel, utas pertama mengumpulkan semua simpul anak yang hilang dan mengirimkannya ke antrian (atau ke tumpukan) di mana utas lain membawanya, antrian atau tumpukan harus menerapkan pendekatan multi-utas, dan algoritme berulang, menggantikan simpul yang baru saja diambil sebagai pengganti root.
   
   Faktanya, secara umum, algoritmenya terlihat seperti ini (satu warna - satu utas):
   

Faktanya, secara umum, algoritmenya terlihat seperti ini (satu warna - satu utas):

Implementasi perangkat lunak Java

Saya memberikan contoh kode yang mungkin berguna bagi seseorang, saya mencarinya untuk waktu yang lama, tetapi tidak menemukannya:

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

Kesimpulan

Seperti yang Anda lihat, multithreading di Java dapat diimplementasikan cukup sederhana melalui BlockingQueue, struktur data yang menyediakan akses beberapa utas ke data yang disimpan.

Secara umum, itu saja, singkatnya, menulis komentar tentang apa metode lain atau metode traversal pohon ada, saya ingin mendengar pendapat guru dalam hal ini. Tulis pertanyaan, harapan.

Tautan ke GitHub . Ada juga mesin pencari JavaFX terdekat, jika seseorang ingin menguji, saya hanya akan senang.