Структура данных для сопоставления 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\wwwroot 
F:\foo\bar\baz => 
D:\ =>

Answer 2

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

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

Answer 3

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

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

и так далее

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

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

Answer 4

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

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

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