從文件路徑列表構建目錄樹

我正在尋找一種時間有效的方法來將文件列表解析到樹中。可能有數以百萬計的文件路徑。從文件路徑列表構建目錄樹

蠻力的解決方案是將目錄分隔符出現時的每個路徑分開，並通過字符串比較遍歷目錄和文件條目中添加的樹，但這會非常慢。

輸入數據通常是按字母順序排列，因此列表會是這樣的：

C：\用戶\亞倫\ AppData的\ Amarok的\å文件

C：\用戶\亞倫\ AppData的\ Amarok的\ Afile2

C：\用戶\亞倫\應用程序數據\ Amarok的\ Afile3

C：\用戶\亞倫\應用程序數據\攪拌機\ alibrary.dll

C：\用戶\亞倫\ AppData的\攪拌機\ and_so_on.txt

從這個排序我的自然反應就是做緩慢的字符串比較之前的目錄列表劃分爲組... ...不知何故。我真的不確定。我會很感激任何想法。

編輯：如果可能的話，這個樹從上到下被延遲加載會更好。

來源

2010-03-15 Abignale

爲什麼你認爲這將是非常緩慢？如果有N行，每行是直至m個字符（所以有<=米目錄組件），這將只需要時間O（納米）。對於每一行，將其插入深度至多爲m的樹狀結構中。 nm是輸入數據的大小，所以它是線性的。 – p00ya 2010-03-15 05:27:32

如果可能的話，你可以生成你的樹結構，將tree命令，here

來源

2010-03-15 05:14:51 ghostdog74

爲了把你的輸入數據的「通常分類」屬性的優勢，在這裏你的最後一個文件是目錄開始你的穿越插入：將當前路徑名的目錄名稱與前一個名稱進行比較。如果他們匹配，你可以插入這裏，否則彈出一個級別，然後再試一次。

來源

2010-03-15 05:31:41

由於無法保證字符串可能存在差異，您別無選擇，只能進行完整的字符串比較。有可能加快速度幾個技巧一點：

正如大衛說，形成一棵樹，但與前一個搜索新的插入點（可能帶有某種matchingPrefix例行的幫助是會告訴你新的不同）。
使用哈希表，樹的每個級別有沒有可能中非常多的文件，你需要計算重複。（否則，附加到一個堆棧的罰款。）

來源

2010-03-15 13:34:40

從文件路徑列表構建目錄樹

回答

相關問題