用於映射URL或本地路徑的數據結構

我一直在試圖制定一個快速實現這一目標的好方法，但我不確定哪種方法最優化，我希望你們中有些更有經驗的開發人員可以提供幫助通過您的數據結構知識:-)用於映射URL或本地路徑的數據結構

本質上我有一個路徑列表（例如C：\ inetpub \ wwwroot \，C：\ www \ websites \ vhosts \ somesite.com \，D：\ www-mirror \ websites \ vhosts \ somesite.co.uk），我必須檢查當前正在處理的文件（比如C：\ inetpub \ wwwroot \ styles \ style.css）是否存在於預先配置的路徑列表中。

所以我最初的想法是將項目列表進行整理並執行CurrentFilename.StartsWith（PreconfigureListOfPathsPathName）。但是我經常在列表中遍歷整個列表，並且列表可能會減慢，因爲列表有時可能包含10個，其他1000個（客戶端在服務器上）路徑。

作爲這個問題的快速解決方案，您會有什麼建議？我在C＃3.5中編寫，這只是該項目的一小部分（但非常關鍵）。

我想過二叉搜索樹，分解路徑，然後做一個樹形圖並遍歷每個路徑。但我不確定它是否正確，因爲我們可以有很多節點。

D:\www-mirror\websites\vhosts\somesite.co.uk\ 
D:\www-mirror\websites\vhosts\somesite.com\ 
D:\www-mirror\websites\vhosts\somesite.org\ 
D:\www-mirror\websites\vhosts\somesite.pl\

樹形圖：

www-mirror->websites->vhosts->somesite* (has 4 nodes) 
www-mirror->blah->woah->okay

但它看起來有點靠不住。

來源

2010-01-26 Nicole Lee

用預先配置的路徑初始化HashSet。然後，對於每個文件來測試，減少從端部的路徑和探測HashSet在每次迭代：

class PreconfiguredPaths { 
    private readonly HashSet<string> known = new HashSet<string>(); 

    public PreconfiguredPaths(params string[] paths) { 
    foreach (var p in paths) 
     known.Add(Normalize(p)); 
    } 

    public string Parent(string path) { 
    path = Normalize(path); 

    while (path.Length > 0) { 
     if (known.Contains(path)) 
     return path; 
     else if (!path.Contains("\\")) 
     break; 

     path = Regex.Replace(path, @"\\[^\\]+$", ""); 
    } 

    return null; 
    } 

    private string Normalize(string path) { 
    return Regex.Replace(path, "\\\\+", "\\").TrimEnd('\\').ToLower(); 
    } 
}

例如：

var paths = new PreconfiguredPaths(
    @"C:\inetpub\wwwroot\", 
    @"C:\www\websites\vhosts\somesite.com\", 
    @"D:\www-mirror\websites\vhosts\somesite.co.uk" 
); 

string[] files = { 
    @"C:\inetpub\wwwroot\styles\style.css", 
    @"F:\foo\bar\baz", 
    @"D:\", 
}; 

foreach (var f in files) 
    Console.WriteLine("{0} => {1}", f, paths.Parent(f));

輸出：

C:\inetpub\wwwroot\styles\style.css => c:\inetpub\wwwroot 
F:\foo\bar\baz => 
D:\ =>

來源

2010-01-26 13:14:52

謝謝，這似乎是可行的！ – 2010-01-29 12:26:16

不客氣！我很高興它有幫助。 – 2010-01-29 14:11:01

我懷疑迭代1000個項目的列表實際上是你的性能瓶頸。我懷疑實際上擊中磁盤或網絡共享是什麼時候吃東西。如果你在做磁盤或網絡I \ O，你需要在工作線程上完成。你不需要一個複雜的結構，只需走1000件物品。你應該做一些時間來看看你的性能問題實際上在哪裏......

如果你要發佈你正在用來做迭代的代碼，那也可能有助於獲得更好的答案。

來源

2010-01-26 02:48:47

同意原則上，但是如果將I/O放在工作線程上，那麼在迭代項目之前，是否還需要等待讀取完成？ – 2010-01-26 05:24:39

最好的辦法是用樹建模允許路徑，並將檢查的路徑作爲樹遍歷。所以你建立如下的結構：

root 
+- C: 
| +- inetpub 
|  +- wwwroot 
| +- www 
|  +- websites 
+- D: 
    +- www-mirror

等

或者你可以簡單地有路徑的排序列表，並做他們平分搜索，找到最接近的匹配（即等於或小於以字符串比較術語）。如果您的字符串以最接近的匹配開頭，則它位於允許的目錄中。

你將不得不在這種情況下正常化輸入（例如全部小寫，確保所有的路徑分隔符是一致的，等等）。

來源

2010-01-26 02:52:48 cletus

我會說特里是最好的數據結構，可能這個scenario.I認爲，你可以在網上找到線索的實現。如果沒有，可以通過關注維基百科編寫它。

對於特里，/將是默認節點斷路器。因此，每個節點都包含一些路徑名，並根據數據傳輸樹。該解決方案可能涉及比較來自特定路徑的最大節點數量。最糟糕的情況將出現在下面的場景中，您有n長度路徑和最後一個節點包含m個文件。在這種情況下，你有效地進行n次遍歷+ m比較，所以它的O（N + M）。如果目錄包含均勻分佈的文件，則時間將爲O（要搜索的路徑的長度）。

另一個改進是緩存最近的答案，然後在繼續執行trie之前檢查它們。

來源

2010-01-26 05:17:33 Boolean

用於映射URL或本地路徑的數據結構

回答

相關問題