4
\$\begingroup\$

This is from the Resin codebase. It is fast at lookup but I could use some help making it faster at buildup. Loaded with 210K words, it looks up pretty much any node and its descendants in zero time. Buildup takes 3000 ms.

using System;
using System.Collections.Generic;
using System.IO;

namespace Resin
{
    public class UseTrie
    {
        public void Main()
        {
            var words = new[]{"pre", "prefix"};
            var trie = new Trie(words);

            // Print "pre" and "prefix"
            foreach(var word in trie.GetTokens("pr"))
            {
                Console.WriteLine(word);
            }
        }
    }
    public class Trie
    {
        public char Value { get; set; }

        public bool Eow { get; set; }

        public IDictionary<char, Trie> Children { get; set; }

        public bool Root { get; set; }

        public Trie(bool isRoot)
        {
            Root = isRoot;
            Children = new Dictionary<char, Trie>();
        }

        public Trie(IList<string> words)
        {
            if (words == null) throw new ArgumentNullException("words");

            Root = true;
            Children = new Dictionary<char, Trie>();

            foreach (var word in words)
            {
                AppendToDescendants(word);
            }
        }

        public Trie(string text)
        {
            if (string.IsNullOrWhiteSpace(text))
            {
                throw new ArgumentException("text");
            }

            Value = text[0];

            Children = new Dictionary<char, Trie>();

            if (text.Length > 1)
            {
                var overflow = text.Substring(1);
                if (overflow.Length > 0)
                {
                    AppendToDescendants(overflow);
                }
            }
            else
            {
                Eow = true;
            }
        }

        public IEnumerable<string> GetTokens(string prefix)
        {
            var words = new List<string>();
            Trie child;
            if (Children.TryGetValue(prefix[0], out child))
            {
                child.Scan(prefix, prefix, ref words);
            }
            return words;
        }

        private void Scan(string originalPrefix, string prefix, ref List<string> words)
        {
            if (string.IsNullOrWhiteSpace(prefix)) throw new ArgumentException("prefix");

            if (prefix.Length == 1 && prefix[0] == Value)
            {
                // The scan has reached its destination. Find words derived from this node.
                if (Eow) words.Add(originalPrefix);
                foreach (var node in Children.Values)
                {
                    node.Scan(originalPrefix+node.Value, new string(new []{node.Value}), ref words);
                }
            }
            else if (prefix[0] == Value)
            {
                Trie child;
                if (Children.TryGetValue(prefix[1], out child))
                {
                    child.Scan(originalPrefix, prefix.Substring(1), ref words);
                }
            }
        }

        public void AppendToDescendants(string text)
        {
            if (string.IsNullOrWhiteSpace(text)) throw new ArgumentException("text");

            Trie child;
            if (!Children.TryGetValue(text[0], out child))
            {
                child = new Trie(text);
                Children.Add(text[0], child);
            }
            else
            {
                child.Append(text);
            }
        }

        public void Append(string text)
        {
            if (string.IsNullOrWhiteSpace(text)) throw new ArgumentException("text");
            if (text[0] != Value) throw new ArgumentOutOfRangeException("text");
            if (Root) throw new InvalidOperationException("When appending from the root, use AppendToDescendants.");

            var overflow = text.Substring(1);
            if (overflow.Length > 0)
            {
                AppendToDescendants(overflow);
            }
        }
    }
}

Edit: Where is a great free profiler? Been using and loving Resharper Ultimate's profiler but it has expired.

\$\endgroup\$
4
\$\begingroup\$

single-expression if statements

I do not know if there is an official stance on formatting, but I find placing the if and the expression it contains side-by-side is difficult to read in most cases. It is also generally non-standard, and invites buggy code like the following:

if(is true) do stuff;
    do other stuff;

This is especially true if the boolean expression is long.

The safest formatting is to put the expression on the next line and enclose it in braces, even if it is a single line:

if(is true)
{
    do stuff;
}

Personally, I err on the side of the above, but I generally find it acceptable to omit the braces when the expression leaves the current block (e.g., return, throw, continue, break):

if(is true)
    throw new SomeSpecificException("badness happened");

encapsulation

Most of the members in Trie are currently public. Many do not need to be. The general interaction with the trie is going to be creating it, adding words to it (currently part of the creation step), and fetching data from it.

With those use cases in mind, none of the properties need to be public, and in fact, none of them need to be properties. Instead, I would change them to private fields. By convention, you should then rename them to _camelCase (e.g., _children).

Also, since a caller is only going to be interested in the root, the third constructor should be private.

Additionally, the Append method is dangerous to call on the root, but the above use cases dictate that callers only care about dealing with the root. Since all the children of Trie happen to also be Trie objects, you can make it private.

This also allows you to remove the root flag altogether, since it was only there to prevent invalid access of Append, and callers can no longer directly access children.

readonly for great justice

None of the properties (now fields) are modified outside a constructor, and given the behavior of Trie, none of them should change. As such, it is best to make them explicitly read-only:

private readonly char _value;
private readonly bool _eow;
private readonly IDictionary<char, Trie> _children;

constructor chaining

The three constructors repeat assigning the children dictionary. A better way to do this is with constructor chaining. Move the dictionary assignment to a single constructor and call it from the other constructors:

public Trie()
{
    _children = new Dictionary<char, Trie>();
}

public Trie(IEnumerable<string> words)
    : this()
{
...
}

public Trie(string text)
    : this()
{
...
}

nameof all the things

With the addition of the nameof operator in C#6, I use it wherever possible when referencing the name of a member. In Trie, this is useful for all your ArgumentExceptions:

if (string.IsNullOrWhiteSpace(text))
    throw new ArgumentException("text");

becomes

if (string.IsNullOrWhiteSpace(text))
    throw new ArgumentException(nameof(text));

The benefit is that if you ever rename text, your refactor tools will update the second example, while commonly, they will miss the string in the first example.

sealed by default

As a general rule, I seal classes unless it has been specifically designed for extension. I could go into explanations why, but smarter people than I already have.

Final code:

public sealed class Trie
{
    private readonly char _value;
    private readonly bool _eow;
    private readonly IDictionary<char, Trie> _children;

    public Trie()
    {
        _children = new Dictionary<char, Trie>();
    }

    public Trie(IEnumerable<string> words)
        : this()
    {
        if (words == null)
            throw new ArgumentNullException(nameof(words));

        foreach (var word in words)
        {
            AppendToDescendants(word);
        }
    }

    private Trie(string text)
        : this()
    {
        if (string.IsNullOrWhiteSpace(text))
            throw new ArgumentException(nameof(text));

        _value = text[0];

        if (text.Length > 1)
        {
            var overflow = text.Substring(1);
            if (overflow.Length > 0)
            {
                AppendToDescendants(overflow);
            }
        }
        else
        {
            _eow = true;
        }
    }

    public IEnumerable<string> GetTokens(string prefix)
    {
        var words = new List<string>();
        Trie child;
        if (_children.TryGetValue(prefix[0], out child))
        {
            child.Scan(prefix, prefix, ref words);
        }
        return words;
    }

    private void Scan(string originalPrefix, string prefix, ref List<string> words)
    {
        if (string.IsNullOrWhiteSpace(prefix))
            throw new ArgumentException(nameof(prefix));

        if (prefix.Length == 1 && prefix[0] == _value)
        {
            // The scan has reached its destination. Find words derived from this node.
            if (_eow)
                words.Add(originalPrefix);
            foreach (var node in _children.Values)
            {
                node.Scan(originalPrefix + node._value, new string(new[] { node._value }), ref words);
            }
        }
        else if (prefix[0] == _value)
        {
            Trie child;
            if (_children.TryGetValue(prefix[1], out child))
            {
                child.Scan(originalPrefix, prefix.Substring(1), ref words);
            }
        }
    }

    public void AppendToDescendants(string text)
    {
        if (string.IsNullOrWhiteSpace(text))
            throw new ArgumentException(nameof(text));

        Trie child;
        if (!_children.TryGetValue(text[0], out child))
        {
            child = new Trie(text);
            _children.Add(text[0], child);
        }
        else
        {
            child.Append(text);
        }
    }

    private void Append(string text)
    {
        if (string.IsNullOrWhiteSpace(text))
            throw new ArgumentException(nameof(text));
        if (text[0] != _value)
            throw new ArgumentOutOfRangeException(nameof(text));

        var overflow = text.Substring(1);
        if (overflow.Length > 0)
        {
            AppendToDescendants(overflow);
        }
    }
}

Additional Notes

Naming is one thing you may want to look at.

The class is called Trie, which only describes the data structure you used, rather than the purpose of the object. You are using it to store words, so my first reaction is to call it a Dictionary, but of course, that name's taken. Naming is hard :(

Also, it seems a little odd that you scan for words with a GetTokens method and you add tokens with an AppendToDescendants method. The latter bleeds implementation details to the caller - why should they know there are descendants at all? I would probably use FindWords and AddWord, but I leave final judgement to you.

There's also the use of ref in your Scan method I would love to replace. However, since I am out of time on my lunch break, I leave that to someone else.

As far as performance goes: use a profiler. I could take a crack at the performance issue you mentioned, but all I would end up doing is profiling it myself.

\$\endgroup\$
  • \$\begingroup\$ Thank you so much first of all for reading my code and then for such an extensive answer. I agree with everything, except sealed. I CANNOT STAND when MS have made fwk classes sealed that I know through looking at the decompiled code is safe for me to use. \$\endgroup\$ – Marcus Mar 23 '16 at 18:14
  • \$\begingroup\$ And also, what's wrong with my use of ref? \$\endgroup\$ – Marcus Mar 23 '16 at 18:15
  • \$\begingroup\$ @Marcus you are passing words by ref. words is already a reference type, so you're not gaining in efficiency by passing it by ref. If you pass in words directly to a method that takes List<string> you will not be copying the list, just copying its reference. Since you are not actually making words point to something else in the method, there is no reason to pass it by ref, and it just makes it confusing. \$\endgroup\$ – 404 Mar 23 '16 at 20:41
  • \$\begingroup\$ Nice answer. If OP was using C# 6.0, besides the nameof feature he could also declare read only properties such as public char Value { get; }. \$\endgroup\$ – Rick Davin Mar 23 '16 at 21:17
  • \$\begingroup\$ @RickDavin Oh, I love writing less code. That's really nice. I should probably install vs2015. Heard it's a crash-bound thing compared to 2013. \$\endgroup\$ – Marcus Mar 24 '16 at 6:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.