c# - 映射 URL 或本地路径的数据结构

Question

我一直在尝试找到一种快速完成此操作的好方法，但我不确定什么是最佳方法，我希望你们中一些更有经验的开发人员可以通过您的数据结构知识提供帮助:-)

基本上我有一个路径列表(例如 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 编写，这只是项目的一小部分(但很关键)。

我想到了二叉搜索树，分解路径，然后做一个 TreeMap 并遍历每条路径。但我不确定它是否正确，因为我们可能有很多节点。

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

但它看起来有点不稳定。

Answer 1

使用预先配置的路径初始化一个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\wwwrootF:\foo\bar\baz =>D:\ =>