数据结构学习(C++)

发表于 | 分类于 | 评论数： | 阅读次数：

背景

最近想优化下敏感词过滤算法， 了解到trie tree，既然学习trie tree ，顺便就温习下常见的一些数据结构

说明

C++ 常见容器的实现代码

数据结构说明

数组

  • 增加: 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，可以达到高效的缓存访问