Блог

Главная - Вопросы по программированию - Построение URL-дерева из Vec

Построение URL-дерева из Vec

#algorithm #web #struct #rust #tree

#алгоритм #веб #структура #Ржавчина #дерево

Вопрос:

мне нужно создать структуру дерева url, например, карту сайта. Ввод: Vec — список ожидаемых URL-адресов Вывод: структура с вложенной иерархией URL-адресов, от корня до конечных точек.

Это уже существующий ящик или мне нужно сделать его самому?

Ввод:

 {
   "https://exapmle.com",
   "https://exapmle.com/aa",
   "https://exapmle.com/ab",
   "https://exapmle.com/v",
   "https://exapmle.com/zac",
   "https://exapmle.com/zac/acf",
   "https://exapmle.com/zac/acf/adr",
   "https://exapmle.com/zac/axx"
}

Вывод:

 UrlTree {
    root: "https://exapmle.com",
    Nodes: {
        {
            node: "aa",
            Nodes: None,
        },
        {
            node: "ab",
            Nodes: None,
        },
        {
            node: "v",
            Nodes: None,
        },
        {
            node: "zac",
            Nodes: {
                       {
                            node: "acf",
                            Nodes: {
                                       node: "adr",
                                       Nodes: None,
                                   }   
                       },
                       {
                            node: "axx",
                            Nodes: None,
                       }
                   }
        }
    }
}

Комментарии:

1. Добро пожаловать в StackOverflow! Хотя сомнительно, что вы найдете ящик, который точно соответствует вашему конкретному варианту использования, не должно быть сложно создать структуру данных, которая делает то, что вы хотите.

2. В вашем желаемом выводе трудно определить, какой тип Nodes поля — он выглядит как dict , но его ключи, похоже, встроены в значения. Вы могли бы сопоставить подузлы как a HashMap , ключами которых являются строки, а значениями — узлы, соответствующие этим строкам, например, здесь . Точный дизайн также будет зависеть от того, что именно вы хотите сделать с результирующим деревом.

3. Вы можете искать реализации дерева оснований или дерева префиксов на crates.io . Быстрый поиск показал это, что выглядит разумно: docs.rs/radix_trie/0.2.1/radix_trie

Ответ №1:

Я думаю, вам придется что-то кодировать самостоятельно. Хотя вы могли бы использовать базовое дерево, как упоминал Свен Марнах, у вас возникнет проблема, связанная с тем, что оно может быть разделено на имя папки, и не только /. Abc/df и abd/df будут сохранены как (an, c/df, d /df) .

Создавая что-то самостоятельно, вы должны спросить, насколько большим будет ваш размер ввода, длина или ваш vec, насколько производительным должен быть ваш код?

Если производительность не такая уж большая проблема, тогда будет найден vec struts. При каждой вставке просто проверяйте, есть ли текущая папка уже в hashmap и добавьте или перейдите на шаг вниз. После того, как вы построите структуру, сопоставьте ее с желаемым результатом.

Если вам нужно что-то более производительное, вы могли бы реализовать что-то вроде базового дерева, структура не слишком сложна для реализации, поскольку вам нужно только позаботиться о разделении на «/», вы могли бы использовать это как вдохновение https://www.cs.usfca.edu /~galles/visualization/RadixTree.html .

Метки: