嵌入式系统开发中该如何选择数据结构？

最近研读一些代码发现了跳表这个好玩的数据结构感觉在很多地方都用到了类似的思想所以今天跟大家拿出来分享一波都知道在嵌入式系统开发中该选择怎样的数据结构是非常谨慎的一件事直接决定的嵌入式平台的实时性、内存占用、代码稳定性千万不要拿来就用~以前我们可能就是拿着一些普通的链表和数组进行有序的数据管理那么其实普通的链表这样的查询效率是比较低下O(n)同时数组大家都知道插入删除需大量搬移数据所以你说要实现高性能实我个人觉得还是比较难的。当然像一些其他的数据结构什么红黑树、AVL树等平衡二叉树虽性能优异但是逻辑是真的复杂理解起来都有一些困难代码量大、如果是自己受挫还要调试也是比较困难的一件事我觉得在嵌入式中特别是要求资源受限、代码精简中还是没那个必要的~那么今天的主角就出来了介绍一个相对平衡一点的数据结构: 跳表Skip List,可以说跳表式是一种链表多级索引的轻量化有序数据结构凭借“空间换时间”的极简设计、易实现、低复杂度、高效增删查的特性非常适合嵌入式系统其实就像MMU中的多级页表~1单链表瓶颈大家用得比较多的还是普通链表。它无需连续内存、节点动态增删、实现极简但核心缺陷是查找效率极低而且由于链表节点是离散存储的所以只能从头节点开始逐一遍历我的天查找、插入、删除的时间复杂度均为O(n)。如果说你的应用需要管理的有序数据量增大比如多个定时器、多任务队列线性遍历非常的耗时吃力导致代码跑不过来、系统响应延迟实时性肯定也受到了影响。2跳表带多级索引的高效链表跳表由William Pugh在1989年提出核心设计思路是在原始有序链表的基础上建立多层级索引层通过索引快速跳过无效节点实现类二分查找的检索效率本质是用可控的额外内存开销换取指数级提升的查找效率。跳表的结构分为两层核心部分原始数据层最底层的完整有序链表存储所有实际业务数据和普通单链表一致多级索引层在原始链表之上逐层提取部分节点作为索引上层索引是下层索引的子集层数越高节点越少索引越稀疏。举个通俗例子原始链表按从小到大存储1-10的数字第一层索引每隔2个节点提取一个1、3、5...第二层索引再从第一层索引中每隔2个节点提取1、5、9查找节点8时先从顶层索引快速定位到5-9区间再向下层索引缩小范围最后落到原始链表精准查找全程跳过大量无效节点无需逐一遍历。3跳表核心操作与复杂度分析跳表主要的操作查找、插入、删除。其操作步骤就是“顶层索引遍历-逐层向下缩小范围-原始链表定位”无需像平衡树那样做复杂的旋转、变色调整等等实现逻辑极简。下面再描述下它基本的操作吧:查找操作从最高层索引开始向后遍历大于当前目标值的节点逐层向下最终在原始链表找到目标节点平均时间复杂度O(logn)插入/删除操作先查找目标位置再完成节点增删同步更新对应索引层平均时间复杂度同样为O(logn)空间复杂度属于可控的空间换时间索引层数一般控制在3-5层即可满足嵌入式场景整体空间复杂度O(n)远低于哈希表的内存开销。4跳表在嵌入式中的应用下面介绍两个跳表在嵌入式软件方面的应用场景应用场景1比如说我们在嵌入式中常常设计的软件定时器模块用于实现延时任务、周期任务、超时判断如串口超时、传感器采样超时。传统方案多采用普通单链表按超时时间排序管理定时器每次系统Tick中断时都需要从头遍历链表查找最早到期的定时器当定时器数量超过10个时遍历耗时会明显增加挤占中断时间影响系统实时性。跳表优化方案将软件定时器按超时时间戳构建有序跳表原始链表存储所有定时器节点上层建立2-3层超时时间索引相比传统链表定时器跳表管理的定时器模块在多定时器场景下中断内查询耗时至少降低一半以上这样就可以大大降低因定时器遍历导致的中断阻塞尤其在一些工业控制板等多延时任务的嵌入式设备。应用场景2:在一些轻量RTOS中任务调度核心是任务就绪队列系统需按任务优先级快速选取最高优先级任务执行。以前很多RTOS采用位图链表的方式管理就绪队列虽能快速定位优先级但同一优先级下的任务仍依赖链表遍历在多任务、多优先级场景下调度效率存在瓶颈而采用红黑树优化代码复杂度太高不利于MCU移植和调试。跳表优化方案将RTOS任务就绪队列改用跳表实现按任务优先级构建有序跳表优先级高的任务排在链表前端同时建立多级优先级索引适配资源受限的MCU级RTOS代码量远低于红黑树调度器调度响应速度远超普通链表同时支持动态调整任务优先级兼顾了实时性与代码精简性。‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧ END ‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧关注我的微信公众号回复“星球”加入知识星球有问必答。点击“阅读原文”查看知识星球详情欢迎点分享、收藏、点赞、在看。