(19)国家知识产权局 (12)发明 专利 (10)授权公告 号 (45)授权公告日 (21)申请 号 202211091770.2 (22)申请日 2022.09.07 (65)同一申请的已公布的文献号 申请公布号 CN 115185985 A (43)申请公布日 2022.10.14 (73)专利权人 北京镜舟 科技有限公司 地址 100096 北京市海淀区西三 旗建材城 内4幢一层1 17号 (72)发明人 方祝和　 (74)专利代理 机构 北京华夏泰和知识产权代理 有限公司 1 1662 专利代理师 卢万腾 (51)Int.Cl. G06F 16/2453(2019.01) G06F 16/2457(2019.01)G06F 16/2455(2019.01) G06F 9/38(2006.01) G06F 12/0842(2016.01) G06F 9/50(2006.01) 审查员 曹俊杰 (54)发明名称 数据排序方法、 装置、 电子设备及存 储介质 (57)摘要 本申请实施例涉及一种数据排序方法、 装 置、 电子设备及存储介质， 方法包括： 由待排序标 识集得到T个子标识集并启动与其对应的T个线 程； 根据子标识集中标识分布特征将各个子标识 集划分为N个区间， 将待排序标识集对应的待排 序数据集存储到本地非一致内存访问节点； 将各 个子标识集中标识分布特征相同的区间进行组 合， 得到N个目标子标识集， 针对任一线程启动C 个协程交错执行； 针对任一协程， 确定协程对应 的目标子标识集， 采用单指令多数据流向量化方 式对目标子标识集循环筛选出最小或最大标识， 并从本地非一致内存访问节点中获取其对应的 数据， 以组成N个有序目标子 数据集， 合并得到有 序数据集。 可同时解决待排序数据排序过程中遇 到的多个瓶颈 。 权利要求书3页 说明书17页 附图6页 CN 115185985 B 2022.12.20 CN 115185985 B 1.一种数据排序方法， 其特 征在于， 所述方法包括： 对待排序 标识集进行切分， 得到T个子标识集， 并启动T个线程， 所述线程与所述子标识 集一一对应； 针对任一所述子标识集， 根据所述子标识集中标识分布特征对所述子标识集进行划 分， 得到N个区间， 将所述待排序标识 集对应的待排序数据集存储到本地 非一致内存访问节 点； 针对任一所述线程， 对所述线程对应的所述子标识集进行排序， 以得到T个有序子标识 集； 统计T个所述有序子标识集的标识分布特征， 根据T个所述有序子标识集的标识分布特 征， 确定N个区间范围； 针对任一所述有序子标识集， 根据N个所述区间范围对所述有序子标识集进行划分， 得 到N个区间； 对所述N个区间进行切分， 得到 M个区间集； 将各个有序子标识集中区间范围相同的区间集进行组合， 得到M个所述区间范围相同 的区间集的第一集合， 将任一所述第一集合对应的数据存储到一个本地 非一致内存访问节 点； 将各个所述子标识集中标识分布特征相同的区间进行组合， 得到N个目标子标识集， 针 对任一所述线程启动C个协程， 其中， 所述C个协程交错执 行； 针对任一协程， 确定所述协程对应的目标子标识集， 采用单指令多数据流向量化方式 对目标子标识集循环筛选出最小或最大标识， 以获取本地非一致内存访问节点中所述最小 或最大标识对应的数据， 组成有序目标子数据集， 以得到N个有序目标子数据集； 将所述N个有序目标子数据集进行合并， 得到所述待排序标识集对应的待排序数据的 有序数据集。 2.根据权利要求1所述的方法， 其特征在于， 所述对所述N个区间进行切分， 得到M个区 间集， 包括： 确定一个本地非一致内存访 问节点的存储空间， 根据所述存储空间对所述N个区间进 行切分， 得到 M个区间集。 3.根据权利要求1所述的方法， 其特征在于， 所述N个目标子标识集包括： N个标识数量 分布均匀的目标子标识集。 4.根据权利要求1所述的方法， 其特征在于， 所述针对任一协程， 确定所述协程对应的 目标子标识 集， 采用单指 令多数据流向量化方式对目标子标识 集循环筛选出最小或最大标 识， 以获取本地非一致内存访问节点中所述最小或最大标识对应的数据， 组成有序目标子 数据集， 包括： 针对任一协程， 确定所述协程对应的目标子标识集， 采用单指令多数据流向量化方式 对目标子标识集循环筛 选出最小或最大 标识； 根据所述 最小或最大 标识执行数据预取指令， 并暂停所述协程； 当所述数据预取指令将所述最小或最大标识对应的数据 预取成功时， 重新执行所述协 程； 从所述本地非一致内存访问节点中获取所述数据预取指令预取到的所述最小或最大权　利　要　求　书 1/3 页 2 CN 115185985 B 2标识对应的数据， 组成有序目标子数据集。 5.根据权利要求4所述的方法， 其特征在于， 所述根据所述最小或最大标识执行数据 预 取指令， 并暂停所述协程之后， 还 包括： 按照预设的优先级通知所述协程对应的线程中启动的第 一协程， 以使所述第 一协程执 行所述确定所述协 程对应的目标子标识 集， 采用单指 令多数据流向量化方式对目标子标识 集循环筛选出最小或最大标识， 以获取本地 非一致内存访问节点中所述最小或最大标识对 应的数据， 组成有序目标子数据集的步骤。 6.根据权利要求1所述的方法， 其特征在于， 所述确定所述协程对应的目标子标识集， 采用单指 令多数据流向量化方式对目标子标识 集循环筛选出最小或最大标识， 以获取本地 非一致内存访问节点中所述 最小或最大 标识对应的数据， 组成有序目标子数据集， 包括： 确定所述协程对应的目标子标识集， 确定所述目标子标识集中的T个区间， 确定所述单 指令多数据流向量 化方式对应的一个指令能够同时处 理的数据的第一数量； 生成一棵叶子结点数量为T的二叉树， 其中， 所述目标子标识集中的T个区间与T个叶子 结点一一对应， 所述 二叉树的各个节点中可存放的标识数量 为所述第一数量； 迭代执行以下步骤， 直至得到所述目标子标识集对应的有序目标子数据集： 确定当前迭代过程中参与归 并的叶子结点， 从所述参与归 并的叶子结点对应的区间中 获取第二数量的最小或最大 标识； 从所述参与归并的叶子结点开始， 按照从左到右或从右到左的顺序两两归并， 直至得 到当前迭代过程中的第一数量的最小或最大的有序标识； 根据所述第一数量的最小或最大的有序标识执 行数据预取指令， 并暂停所述协程； 当所述数据预取指令将所述第一数量的最小或最大的有序标识对应的数据预取成功 时， 重新执 行所述协程； 从所述本地非一致内存访问节点中获取所述数据预取指令预取到的第一数量的最小 或最大的有序标识对应的数据， 以组成有序目标子数据集； 根据所述第一数量的最小或最大的有序标识确定下一次迭代过程中参与归并的叶子 结点以及所述下一次迭代过程中参与归并的叶子结点所要获取的标识的第二数量。 7.根据权利要求6所述的方法， 其特征在于， 所述确定当前迭代过程中参与归 并的叶子 结点， 从所述 参与归并的叶子结点对应的区间中获取第二数量的最小或最大 标识， 包括： 判断当前迭代过程是否为首次迭代过程； 若当前迭代过程为首次迭代过程， 确定参与归并的叶子结点为T个所述叶子结点， 从T 个所述叶子结点对应的区间中获取 所述第一数量的最小或最大 标识； 若当前迭代过程非首次迭代过程， 确定当前迭代过程中参与归并的叶子结点， 从所述 参与归并的叶子结点对应的区间中获取第二数量的最小或最大 标识。 8.根据权利要求6所述的方法， 其特征在于， 所述根据所述第 一数量的最小或最大的有 序标识确定下一次迭代过程中参与归并的叶子结点以及所述下一次迭代过程中参与归并 的叶子结点所要获取的标识的第二数量， 包括： 确定所述第一数量的最小或最大的有序标识对应的叶子结点为下一次迭代过程中参 与归并的叶子结点； 针对任一下一 次迭代过程中参与归 并的叶子结点， 从所述第 一数量的最小或最大的有权　利　要　求　书 2/3 页 3 CN 115185985 B 3