Как оптимизировать алгоритма префиксного дерева?

Question

Мне прилетает большое кол-во строк, которые выглядят вот так:

"reply/command/name",
"reply/command/namef",
"reply1/command1/name1"

Мне необходимо их разделять по / и группировать. Хочется видеть такой результат:

reply
   command
     name
     namef
 reply1
   command1
   name1

Я написал такой алгоритм, который достаточно делает нужное, но не так быстро и оптимально, как хотелось бы. Вот решение:

public class Trie
{
    public Trie(
        string part,
        int level,
        Trie? root = null,
        Trie? parent = null )
    {
        Part = part;
        Level = level;
        Parent = parent;
        Root = root;
    }
    
    public string Part { get; }
    public int Level { get; }
    public Trie? Parent { get; }
    private Trie? Root { get; }
    
    private readonly Dictionary<string, Trie> _children = new();
    public bool Add(string[] topic, int level)
    {
        var changedTopicCount = false;

        if ( topic.Length <= 0 )
            return false;
        
        if (!_children.ContainsKey(topic[0]))
        {
            var node = new Trie(topic[0], level, Root, this);
            _children.TryAdd(topic[ 0 ], node);
            changedTopicCount = true;
        }
        
        if(!_children[topic[0]]
               .Add(topic.Skip(1).ToArray(), 
                   level + 1)
           && !changedTopicCount)
            return changedTopicCount;
        
        changedTopicCount = true;
        return changedTopicCount;
    }
}

использовать вот так:

public class UseTree
{
    public UseTree()
    {
        var root = new Trie( "host", 0 );
        
        TreeRoot = root;
    }
    
    private Trie TreeRoot { get; }

    public void Add()
    {
        var array = new[]
        {
            "reply/command/name",
            "reply/command/namef",
            "reply1/command1/name1"
        };

        foreach (var element in array)
        {
            TreeRoot.Add(
                element.Split('/'),
                1);
        }

    }
}

Подскажите, пожалуйста, что тут можно улучшить?

Стоит ли искать пакеты с производительной реализацией Dictionary?

Answer 1

Чет как то сложно, да и пересоздавать массив topic.Skip(1).ToArray() чутка расточительно.

Ну вот я бы как написал

public class TrieNode
{
    private Dictionary<string, TrieNode> _children = new Dictionary<string, TrieNode>();

    public void Add(string[] data, int index = 0)
    {
        if (index >= data.Length) return;

        var word = data[index];
        if (!_children.ContainsKey(word)) _children.Add(word, new TrieNode());
        _children[word].Add(data, index + 1);
    }

    public void Print(string prefix)
    {
        foreach (var kv in _children)
        {
            Console.WriteLine($"{prefix}{kv.Key}");
            kv.Value.Print(prefix + prefix);
        }
    }
}

Проверка

    var data = new[] 
    {
        "reply/command/name",
        "reply/command/namef",
        "reply1/command1/name1"
    };

    var root = new TrieNode();
    foreach (var dataItem in data)
    {
        root.Add(dataItem.Split('/'));
    }

    root.Print("\t");

Вывод

  reply
    command
        name
        namef
  reply1
    command1
        name1

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

БЛОГ НА HUSL

Как оптимизировать алгоритма префиксного дерева?

Ответы (1 шт):