使用多線程在巨大樹結構中查找文件的方法

Question

我有一棵樹，其中包含所有目錄和文件作爲其節點。我想搜索一個特定的文件。說樹廣泛傳播，我想先做一個廣度優先搜索來找到一些特定的文件，也使用多線程。我應該怎麼做使用多線程？什麼是好方法？

Answer 1

假設樹中的每個節點代表一個目錄（及其中的文件），並假設有在線程的數量沒有限制，你可以打開：

輸入根節點，如果它有n子目錄，創建n - 1線程在第一個n - 1中搜索並繼續搜索最後一個子目錄。根據需要重複。

Answer 2

多線程在每個分支未知的工作分配樹搜索任務是不平凡的（這出現了很多中說，約束滿足問題。）

最簡單的方法是創建一個任務隊列（受保護由一個互斥體填充）。將該隊列填充到根節點的所有子節點。產生N個線程（每個可用CPU核心一個）並讓它們通過每個節點進行搜索。您可以採取各種技巧來避免一些不良情況（如果任何線程發現其節點「意外深」，您可以讓他們將新任務添加到對應於其他線程需要探索的子目錄的隊列中）。如果節點深度分佈良好，並且根節點有很多孩子，你可以完全避免這個隊列 - 只要給每個線索分配索引i探索X％N + i的任務（其中X是根節點的子節點數）。

Answer 3

我的第一反應是說「只使用nftw，忘記做多線程」。如果你碰巧有一個nftw實現，樹以多線程的方式走，那麼你可以免費獲得多線程（我不知道任何這樣的實現）。如果你真的想要做多個線程，我會建議使用nftw併爲回調中的每個目錄產生一個新的線程，但並不是馬上就會明白這比任何Kanopus的建議更容易（或者不同）。考慮了一會兒之後，我回到我的第一個建議，並想知道爲什麼你想用多個線程來做到這一點。擁有更多線程不太可能加快搜索速度。使用nftw。不要擔心線程。

Answer 4

樹結構通常不適用於並行化。假設你已經把所有的節點加載到內存中，嘗試並組織它們，使它們佔據一個數組 - 畢竟，它們需要存儲在串行的RAM中 - 並且爲了搜索的目的而忽略它們的樹結構。然後使用某種並行for循環遍歷數組的元素。一個流行的選擇是OpenMP或者你可以在Visual Studio中嘗試parallel_for_each。

Answer 5

有些情況下，多線程搜索將提供有用的加速 - 例如，如果樹跨越多個磁盤，或者某些磁盤/節點通過某個網絡間接連接。

我當然不想嘗試爲每個文件夾創建線程。這是成千上萬的創建/運行/終止，成千上萬的堆棧分配/免費等總量，可避免的開銷。

多線程搜索可以完成，但正如其他海報所說，先查看可用的替代方案。然後閱讀這篇文章的其餘部分。然後再看看

我曾經使用類似於馬特建議的隊列方法做過這樣的事情。

我不想永遠做一遍：

我用這6個線程等待工作的生產者 - 消費者工作隊列，（6因爲測試表明這是最佳的與我的問題）。線程全部在啓動時創建並永不終止。沒有一個持續的創建/加載/運行/ waitFor/getResult/terminateIfYoureLucky的東西，儘管表現不佳，關閉AVs，216/217 messageBoxes等等，但是開發人員似乎很受歡迎。

這項工作以一種形式出現'folderSearch'類包含要搜索的路徑，要調用的文件匹配函數事件以及FindFirst/FindNext循環方法來執行搜索。我在一個池中創建了幾百個這樣的文件（比如推送到另一個P-C池隊列:)。當FF/FN迭代文件夾中的文件以查找匹配的文件時，遇到子文件夾導致從池中提取另一個folderSearch實例，將其加載到新路徑&將其推送到工作隊列 - 某些線程會然後選取它並迭代子文件夾。這個類有一個匹配文件的路徑和一個要調用的'results'事件的列表（當然，這個參數是'this'），如果它發現感興趣的話。如果一個文件夾搜索到了樹枝的盡頭，沒有發現任何東西，並且沒有任何東西可以搜索，它會將自己釋放回池中（好吧，線程會這樣做，但你知道我的意思:)。

不需要任何明確的「負載平衡」。如果一個節點特別深，它會自然而然地結束所有六個線程在其子樹上工作，因爲其他路徑已經耗盡。

搜索3個磁盤全部意味着彈出3個文件夾從池中搜索，用'C：\'，'E：\'，'F：\'和文件匹配方法加載它們，然後將它們推送到工作隊列。然後磁盤發出咔嚓聲，事件最終會觸發結果。在我的情況下（Windows），事件PostMessaged將folderSearch對象傳遞給UI線程，其中結果顯示在treeView中，然後再重新安裝folderSearch以供重用。

該系統的速度是跨3個磁盤的簡單順序搜索的2.5倍，即使在僅有一個內核的舊開發盒中，僅因爲所有3個磁盤都是並行搜索的。我懷疑它會在現代盒子上顯示出同樣的優勢，因爲限制因素可能主要由IO在磁盤上等待。

令人驚訝的是，只有一個磁盤也有一個加速，但沒有那麼多。不知道爲什麼 - 由於所有額外的複雜因素，應該由於權利而變慢。

當然，有問題。其中一個是，由於搜索引發了大量結果，因爲UI無法跟上線程，所以所有的folderSearch對象都被阻塞在排隊等待UI的PostMessage中，因此池會空置，因此減慢了搜索線程的速度他們不得不在隊列中等待，直到PostMessages得到處理，然後將folderSearch返回到池中。這也意味着用戶界面被有效屏蔽，直到搜索結束，並且可以趕上，否定了搜索的優勢之一：（使用小結果集，它工作正常）。

另一個可能的問題是，結果以「非自然」的方式返回，以如此混亂的方式交織，像組裝樹視圖這樣的事情比單線程遞歸搜索複雜得多 - 您必須在整個將結果填充到正確的位置，這會加載GUI並帶來額外的工作，並可能因爲大量結果而影響搜索速度優勢，因爲我發現了這種設計可以同時運行多個搜索。作爲一個測試，我會一次加載多個3盤搜索，（不要在加載treeView的時候 - 我只是將在GUI消息處理程序中找到的文件的數量轉儲到備註行中）。這造成了大量的嘎嘎聲，並放緩了所有的爬行，但最終確實完成了所有搜索而沒有崩潰。我沒有經常這樣做，因爲我害怕我的可憐的磁盤。不要在家裏試試這個

我從來不知道有多少線程掛掉隊列。六是關於我的舊盒子本地磁盤上的最佳。如果組合中有網絡磁盤，則更多可能會更好，因爲網絡調用會比本地磁盤讀取阻塞一個線程更長的時間。從未嘗試過，但加載更多的線程不會影響本地磁盤的性能，只是使用更多的內存而沒有額外的優勢。

另一個問題是發現搜索是否真的結束 - 是所有的結果..還是某個線程仍在等待一個緩慢或實際上無法訪問的網絡驅動器？只有一次搜索，我可以告訴，因爲當搜索結束時池再次變滿（我將池級轉儲到1s GUI定時器上的stausBar）。這在我的應用程序中並不重要，但在其他應用程序中，它可能...

取消搜索也是一個類似的問題。這些事情需要另一個'searchClass'來控制每個搜索。每個分配給搜索的folderSearch必須保持對searchClass的引用，以便處理folderSearch的任何線程都能找出是否已設置中止，如果是，則停止對該文件夾進行操作。我不需要這個，所以沒有實現它。

有錯誤報告。如果網絡驅動器連接失敗，例如幾個（最可能是全部！），則在引發異常之前，線程可能會阻塞很長時間。然後他們都立即除外。 catch消息被加載到folderSearch中的'errorMess'字段中，結果事件被觸發。人類可檢測的證據 - 嘎嘎聲停止。一分鐘沒有任何事情發生，然後[無線程]錯誤一次出現。

請注意其他海報的警告和我的經驗。只有嘗試這樣的事情，如果你真的需要它來進行一些特殊的搜索目的和你對多線程應用程序100％滿意。如果您可以通過單線程搜索或shell調用文件資源管理器或幾乎任何其他方法逃避責任，那就這樣做！

我已經使用了相同的方法，因爲使用FTP服務器來生成樹。這是更快的爲好，雖然服務器管理員很可能對多個連接不開心

RGDS， 馬丁