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次child尝试，无论它们是否被使用。你可以懒洋洋地创建它们（也就是说，只有当你遇到一个特定的字母时）

您的代码只适用于普通ASCII字母，不处理外来字符、连字符、撇号或混合大小写。懒惰的分配也有助于实现这一点

您的实现在每个char中使用一个Trie对象，再加上一些空的备件，因此可能会占用大量内存

以正确的顺序在getString()中收集结果可能比追加然后反转更好，但您需要对其进行基准测试。如果跟踪Trie的深度，则可以分配正确长度的数组，而不是StringBuilder，但跟踪深度有其自身的内存开销