背景
最近想优化下敏感词过滤算法, 了解到trie tree,既然学习trie tree ,顺便就温习下常见的一些数据结构
说明
C++ 常见容器的实现代码
- 数组 (stl)
- 链表 (stl)
- 栈 (stl)
- 队列 (stl)
- 优先队列(stl)
- 散列表(stl)
- 二叉树之红黑树(stl)
- 堆(stl)
- 跳表(github https://github.com/greensky00/skiplist)
- 图
- trie 数 (github https://github.com/s-yata/darts-clone)
- lrucache : (boost)
数据结构说明
数组
- 增加: O(n)
- 删除: O(n)
- 查找: O(n)
- 随机访问: O(1)
地址空间连续;随机增加、删除不方便;随机访问;查找效率低
链表
- 增加: O(1)
- 删除: O(1)
- 查找: O(n)
- 随机访问: O(n)
地址空间不连续;随机增加、删除方便;不能随机访问;查找效率低
散列表
- 增加: O(1) 装载因子过高,启动扩容O(n)
- 删除: O(1)
- 查找: O(1)
随机增加、删除方便,可能触发动态扩容;查找效率高;排序不方便;hash冲突
平衡二叉树-红黑树
- 增加: O(logn)
- 删除: O(logn)
- 查找: O(logn)
avl树高度差最大为1,红黑树最大高度差为logn,但是插入时动态更新(旋转次数不频繁)性能得到提升,综合性能比较折中,所以大部分平衡二叉树都选择使用红黑树。
堆
快排比堆排序更好,虽然时间复杂度都是O(nlogn)
- 快排局部数据是连续访问,但是堆排序是跳着访问;cpu缓存不友好
- 排序过程中,堆排序交换数据的次数要多余快速排序
跳表
- 增加: O(logn)
- 删除: O(logn)
- 查找: O(logn)
优点:代码实现简单;支持区间搜索
缺点:最大层级固定(一般够用了),内存损失较大(key 会多一些,实际可以接受)
字典树
- 构建: O(m*len) m :敏感词数量,len:敏感词平均长度
- 字符串匹配 : O(k)
敏感词库比较;前缀搜索匹配字符串
luacache 最近最少使用数据结构
最近最少使用数据淘汰算法
list+hashmap 实现。
项目说明
敏感词过滤
这个在之前的敏感词过滤中有说明, 效果很不错
luacache
在项目中主要用于内存数据留存,配合上redis,可以达到高效的缓存访问