用于映射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或本地路径的数据结构

回答

相关问题