Структура данных для сопоставления URL-адресов или локальных путей

Question

Я пытался найти хороший способ сделать это быстро, но я не уверен, что будет наиболее оптимальным, я надеюсь, что некоторые из вас, более опытные разработчики, могут помочь с вашими знаниями Data Structures :-)

По сути, у меня есть список путей (например, C: \ inetpub \ wwwroot \, C: \ www \ sites \ vhosts \ somesite.com \, D: \ www-mirror \ sites \ vhosts \ somesite.co. Великобритания), я должен проверить, что текущий файл, над которым я работаю (скажем, 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

Но это выглядит немного шатко.

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\wwwroot
F:\foo\bar\baz =>
D:\ =>

Answer 2

Лучше всего смоделировать разрешающие пути с деревом и рассматривать рассматриваемый путь как обход дерева. Таким образом, вы строите структуру, как:

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

и т. Д.

В качестве альтернативы вы можете просто иметь отсортированный список путей и выполнить поиск по ним на две части, чтобы найти наиболее близкое совпадение (равное или меньшее в терминах сравнения строк). Если ваша строка начинается с самого близкого совпадения, она находится в разрешенном каталоге.

В этом случае вам придется нормализовать входные данные (например, все строчные буквы, убедиться, что все разделители пути согласованы и т. Д.).

Answer 3

Я бы сказал, что trie - лучшая структура данных, возможная для этого сценария. Я думаю, вы можете найти реализацию trie онлайн. Если нет, его легко написать, следуя википедии.

Для дерева, / будет прерыватель узла по умолчанию. Итак, каждый узел содержит некоторое имя пути, и вы переносите дерево на основе данных. Это решение может включать сравнение максимального количества узлов, происходящих из определенного пути. Наихудший случай произойдет в приведенном ниже сценарии, когда у вас есть путь длины n, а последний узел содержит m файлов. В этом случае вы фактически делаете n обходов + m сравнений, поэтому это O (N + M). Если каталоги содержат файлы, которые распределены равномерно, то время будет равно O (длина пути, по которому будет производиться поиск).

Еще одним улучшением будет кеширование последних ответов, а затем проверка их перед продолжением в дереве.

Answer 4

Я сомневаюсь, что итерация списка из 1000 элементов - это на самом деле ваша производительность. Я подозреваю, что на самом деле попадание на диск или в сетевой ресурс - это то, что пожирает время. Если вы выполняете дисковый или сетевой ввод-вывод, вам нужно сделать это в рабочем потоке. Вам не нужна сложная конструкция, чтобы просто пройти 1000 предметов. Тебе нужно определиться со временем, чтобы увидеть, где на самом деле лежат твои проблемы с перфом ...

Если вы опубликуете код, который вы в настоящее время используете для выполнения итерации, это также может помочь получить лучшие ответы.