`
nianien
  • 浏览: 17523 次
  • 性别: Icon_minigender_1
  • 来自: 北京
社区版块
存档分类
最新评论

自己实现的TrieTree,对比一下效率

阅读更多
运行环境:Win7,Java SDK6,默认配置

测试数据:
         初始数据:20W

        搜索数据:2W

从20W初始数据中查找2w待搜索数据,运行结果:

map used :19 ms, find: 19474

list used: 24303 ms, find: 19474

trie tree used: 163 ms, find: 19474

optimized tree used: 95 ms, find: 19474

optimized again used: 33 ms, find: 19474

理论上map是0(1)的时间复杂度,就以它为参照物吧

但是Map不能进行前缀匹配,前缀匹配可用于搜索推荐,

下面是从20w数据进行前缀匹配的运行结果:

list used: 19 ms, suggest: 1091

trie tree used: 2 ms, suggest: 1091

optimized tree used: 2 ms, suggest: 1091
分享到:
评论

相关推荐

    多模式匹配AC算法实现.zip

    AC算法首先需要构建一个“失败指针”(Failure Link)的字典树(Trie Tree)。字典树结构能够快速地在字符串集合中进行查找,而失败指针则使得在匹配过程中,当某字符不匹配时,能快速跳转到其他可能的匹配路径,...

    一个下拉自动匹配的控件

    4. **性能优化**:如果下拉列表中的选项非常多,匹配过程可能会消耗大量计算资源,因此需要对算法进行优化,如使用前缀树(Trie Tree)或者缓存最近使用的查询结果,以减少计算量。 5. **UI反馈**:匹配成功后,...

    内容分析工具数据结构161209

    此外,字典树(Trie)或后缀树(Suffix Tree)对于字符串搜索和匹配非常有用,尤其是对于关键词过滤和自动补全功能。它们减少了搜索时间,提高了处理大量文本数据的效率。 最后,队列(Queue)和栈(Stack)作为...

    久其分析机器人:AI激活最强大脑.pdf

    分词技术在处理中文等语境中尤为关键,久其分析机器人利用DoubleArray TrieTree的数据结构来存储字典,这样能够提高查找效率,同时避免过多占用内存资源。 最后,久其分析机器人能够通过用户查询来自动进行语音识别...

    数据结构和Java集合框架 英文版 第三版

    - 对比不同实现方式的优劣之处。 3. **实践应用**: - 在实际项目中复现集合类的功能。 - 自定义集合类解决特定场景下的问题。 - 通过调试工具深入理解集合类的工作原理。 #### 四、总结 通过本篇内容的学习...

    lab10_实验报告1

    基础前缀树,也称为Trie树,是一种数据结构,用于存储IP路由表,以实现高效的查找。在Trie树中,每个节点包含网络号(net)、掩码长度(prefix_len)、端口号(port_id)以及节点类型(INTERNAL或MATCH)。节点间...

    数据结构字母字符串操作

    通过构建Trie树,实现高效的字符串查找和建议功能。 总之,数据结构字母字符串操作这一主题涵盖了广泛的知识点,不仅涉及到数据结构的选择和应用,还涉及了字符串处理的常见算法。深入学习这部分内容,将有助于你更...

    NOSQL数据库的查询处理

    **示例**:对于一个文档存储系统,可以通过构建分布式Trie来实现关键词搜索功能,快速定位包含特定关键词的文档。 ### 结论 尽管NoSQL数据库在查询处理方面存在一定的局限性,但通过上述几种解决方案和技术的应用...

    《数据结构与算法分析》答案

    此书不仅包含了理论上的深度分析,还提供了丰富的实践案例,并使用C++作为实现语言,帮助读者更好地理解和掌握数据结构与算法的实际应用。 #### 二、数学基础(Mathematical Preliminaries) 在《数据结构与算法...

    Nanomsg 代码分析

    4. **内存和CPU使用效率**:Nanomsg采用了基数树(radix tree)结构来存储订阅信息,这种数据结构相比于zeromq中的Trie结构在处理大量订阅时更加高效。此外,nanomsg还提供了一种零复制的API,使得数据可以在不同机器...

Global site tag (gtag.js) - Google Analytics