CODEWITHSUNDEEP
javaoptimizationtrie
ntin
ntin

Reputation: 177

Java Trie Optimization

I have been toying with a trie data structure for practice (there is not course work related). This class is used to store substrings of a string. For a string of length n there are n(n+1)/2 total substrings. In particular this implementation of a trie preserves natural ordering and is more efficient than a TreeMap or TreeSet on random strings. As well storing a single character rather than the entire string saves on memory.

I think for storing substrings a suffix array may be the better way to go but I wanted to make sure this trie class is reasonably optimized for speed before starting a new project.

class Trie
{
    final Trie my_parent;
    final Trie[] my_children;
    final char my_value;

    public Trie(final Trie the_parent, final char the_value)
    {
        my_parent = the_parent;
        my_value = the_value;
        my_children = new Trie[26];
    }

    public int insertIterative(final char[] the_text)
    {
        int number = 0;
        Trie parent = this;

        for(int ator = 0; ator < the_text.length; ator++)
        {
            final int key = the_text[ator] - 97;
            Trie child = parent.my_children[key];

            if(child == null)
            {
                child =  new Trie(parent, the_text[ator]);
                parent.my_children[key] = child;
                number++;
            }

            parent = child;
        }   

        return number;
    }

    public String getString()
    {
        final StringBuilder builder = new StringBuilder();
        Trie parent = this;

        while(parent.my_parent != null)
        {
            builder.append(parent.my_value);
            parent = parent.my_parent;
        }

        return builder.reverse().toString();
    }
}

Upvotes: 1

Views: 1450

Answers (1)

DNA
DNA

Reputation: 42586

See my comment above, but a few observations anyway:

You allocate 26 child Tries immediately, regardless of whether they are used. You could create these lazily (i.e. only when you encounter a particular letter).

Your code will only work for plain ASCII letters, and doesn't handle foreign characters, hyphens, apostrophes or mixed case. Lazy allocation would also help with this.

Your implementation uses a Trie object per char, plus some empty spares, so is likely to be quite heavy on memory usage.

It might be better to collect the result in getString() in the correct order rather than appending and then reversing, but you'd need to benchmark this. If you kept track of the depth of the Trie, then you could allocate an array of the correct length, rather than a StringBuilder - but tracking the depth has its own memory cost.

Upvotes: 5

Related Questions