Java Trie优化
我一直在玩trie
实践的数据结构(没有课程工作相关)。该类用于存储字符串的子字符串。对于长度为n
的字符串,总共有子字符串n(n+1)/2
。特别是,trie
的这种实现保留了自然排序并且比随机字符串上的TreeMap
或TreeSet
更有效。存储单个字符而不是整个字符串会节省内存。Java Trie优化
我认为存储子字符串后缀数组可能是更好的方法,但我想确保这个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();
}
}
见我的评论以上,但也有少数意见反正:
你分配26孩子立即尝试,不管是否使用它们。你可以创造这些懒惰(即只有当你遇到一个特定的字母)。
您的代码只能用于纯ASCII字母,并且不处理外来字符,连字符,撇号或混合大小写。懒惰的分配也会对此有所帮助。
您的实现使用每个char
的Trie对象以及一些空的备用,所以可能会占用很大的内存。
它可能更好地以正确的顺序收集getString()
中的结果,而不是追加然后倒转,但是您需要对此进行基准测试。如果你跟踪了Trie的深度,那么你可以分配一个正确长度的数组,而不是StringBuilder--但是跟踪深度有它自己的内存成本。
我从来没有真正考虑过,但空数组仍然需要为空指针分配内存,这将是4个字节(32位)或8字节(64位)。如果Trie拥有100,000个节点,则会浪费相当数量的存储空间。 – ntin 2012-02-29 09:52:58
您是否注意到您需要帮助的特定性能问题?如何通过分析器运行代码以查看哪些部分花费最多时间?当你说“优化”时,你是指速度还是记忆? – DNA 2012-02-29 09:03:09
由于我没有比较的东西,所以很难说速度。我从来没有听说过一个分析器将不得不看看这个。 – ntin 2012-02-29 09:23:56
您可以与其他Trie实现进行比较 - 请参阅此问题,例如:http://*.com/questions/623892/where-do-i-find-a-standard-trie-based-map-implementation-in- Java或此:http://*.com/questions/3806788/trie-data-structures-java – DNA 2012-02-29 15:25:24