关于Treap数据结构问题的研究

计算机科学中最基本的问题就是如何高效的存储、组织数据,以实现快速的查找、更新等操作。本文对二叉树和堆结构进行了简单的回顾,分析了普通和随机Treap数据结构的特点,指出了它的局限性和不足。

快速动态优先搜索树的实现及其应用

对形如([x1:x2],[-∞:y])的二维查询问题,提出一种快速的、易于实现的动态优先搜索树数据结构及其相关算法,采用只在叶节点存储数据的结构,以及在常数时间内实现旋转操作的算法。设n为数据点的个数,k为满足搜索条件的解的个数,则该动态搜索树空间复杂度为O(n),插入、删除操作的时间复杂度为O(logn),搜索复杂度为O(logn+k)。

ROS2多线程执行器上DAG任务的优先级分配方法

随着机器人操作系统(robot operating system, ROS)的日益普及,系统也变得更加复杂,这类系统的计算平台正逐渐转变为多核心平台.在ROS中,任务执行的顺序取决于底层任务调度策略和分配给任务的优先级,而最大限度地缩短所有任务的执行时间是并行系统任务调度的一个重要目标.受强化学习在解决各种组合优化问题的最新研究成果的启发,在考虑ROS2多线程执行器的调度机制和执行约束的前提下,提出了一种基于强化学习的任务优先级分配方法,该方法提取了基于有向无环图形式表示的任务集的时间和结构特征,通过策略梯度和蒙特卡洛树搜索(Monte Carlo tree search, MCTS)方法有效地学习ROS2调度策略并给出合理的优先级设置方案,最终达到最小化并行任务的最大完工时间的目的.通过模拟平台环境下随机生成的任务图以评估所提方法,结果表明所提方法明显优于基准方法.作为一种离线分析方法,所提方法可以很容易地扩展到复杂的ROS中,在可接受的时间内找到接近最优的解决方案.

基于NAND Flash存储器的磨损均衡DP算法优化

双池DP(Dual Pool)算法对于NANDFlash的磨损均衡控制水平较高,但是磨损均衡过程较长,磨损均衡分布不均,第一个磨穿块容易较早出现。为了解决这些不足之处,在吸收双池算法磨损控制思想的基础上,提出一种基于优先搜索树(PST)的磨损均衡思想,在块搜索策略和垃圾回收策略等方面进行优化。实验结果表明,算法继承了磨损均衡控制水平较高的优点,磨损均衡过程相比双池算法降低70%,系统资源利用率降低40%,NAND Flash使用寿命提高了30%。