Java Trie优化

Question

为了实践，我一直在玩trie数据结构(没有与课程相关的工作)。该类用于存储字符串的子字符串。对于长度为n的字符串，有n(n+1)/2总子字符串。特别是，trie的这种实现保留了自然排序，并且比随机字符串上的TreeMap或TreeSet更有效。同时，存储单个字符而不是整个字符串可以节省内存。

我认为，对于存储子字符串，后缀数组可能是更好的方法，但在启动新项目之前，我希望确保这个trie类在速度上得到了合理的优化。

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();
    }
}

Answer 1

请看我上面的评论，不过还是有几点意见：

无论是否使用，您都会立即分配26次子尝试。你可以懒洋洋地创造这些东西(也就是说，只有当你遇到一个特定的字母时)。

您的代码只适用于普通的ASCII字母，不处理外文字符、连字符、撇号或混合大小写。懒惰的分配也会在这方面有所帮助。

您的实现在每个char中使用一个Trie对象，加上一些空的备件，因此可能会对内存的使用造成很大影响。

最好是以正确的顺序收集getString()中的结果，而不是追加然后倒转，但您需要对此进行基准测试。如果您跟踪Trie的深度，那么您可以分配一个正确长度的数组，而不是一个StringBuilder --但是跟踪深度有它自己的内存开销。