自己实现的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
测试数据:
初始数据: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
上一篇: cached过高,导致load高的问题
下一篇: 获取class类字节数组的方法