欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

自己实现的TrieTree,对比一下效率 数据结构和算法

程序员文章站 2022-07-09 13:24:14
...
运行环境: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
相关标签: 数据结构和算法