新闻动态

合并多路已排序事件时怎样保留稳定顺序:机制记录第18例

2026-11-19

几路回放或输入日志各自按时间排列,合并时可以只比较每一路当前最早的一项。取出一项后再补入同一路的下一项,就不必把所有事件重新打乱排序。

输入含义与规则

本例四路事件的时间可以相同,每个事件身份由来源编号和路内序号共同确定。比较键依次是时间、来源编号、路内序号;维护每一路尚未取出的队首,每次输出其中最小者,再推进对应来源。

本次独立演算

四路输入编号零至三,记录顺序为时间、来源、路内序号。

来源0:[[4, 0, 0], [5, 0, 1], [6, 0, 2], [9, 0, 3], [12, 0, 4], [16, 0, 5]] 来源1:[[0, 1, 0], [0, 1, 1], [0, 1, 2], [2, 1, 3], [6, 1, 4], [9, 1, 5]] 来源2:[[4, 2, 0], [7, 2, 1], [10, 2, 2], [13, 2, 3], [17, 2, 4]] 来源3:[[4, 3, 0], [5, 3, 1], [6, 3, 2], [7, 3, 3], [8, 3, 4]] 每次输出及补入后的候选队首: [0, 1, 0] → [[0, 1, 1], [4, 0, 0], [4, 2, 0], [4, 3, 0]] [0, 1, 1] → [[0, 1, 2], [4, 0, 0], [4, 2, 0], [4, 3, 0]] [0, 1, 2] → [[2, 1, 3], [4, 0, 0], [4, 2, 0], [4, 3, 0]] [2, 1, 3] → [[4, 0, 0], [4, 2, 0], [4, 3, 0], [6, 1, 4]] [4, 0, 0] → [[4, 2, 0], [4, 3, 0], [5, 0, 1], [6, 1, 4]] [4, 2, 0] → [[4, 3, 0], [5, 0, 1], [6, 1, 4], [7, 2, 1]] [4, 3, 0] → [[5, 0, 1], [5, 3, 1], [6, 1, 4], [7, 2, 1]] [5, 0, 1] → [[5, 3, 1], [6, 0, 2], [6, 1, 4], [7, 2, 1]] [5, 3, 1] → [[6, 0, 2], [6, 1, 4], [6, 3, 2], [7, 2, 1]] [6, 0, 2] → [[6, 1, 4], [6, 3, 2], [7, 2, 1], [9, 0, 3]] [6, 1, 4] → [[6, 3, 2], [7, 2, 1], [9, 0, 3], [9, 1, 5]] [6, 3, 2] → [[7, 2, 1], [7, 3, 3], [9, 0, 3], [9, 1, 5]] [7, 2, 1] → [[7, 3, 3], [9, 0, 3], [9, 1, 5], [10, 2, 2]] [7, 3, 3] → [[8, 3, 4], [9, 0, 3], [9, 1, 5], [10, 2, 2]] [8, 3, 4] → [[9, 0, 3], [9, 1, 5], [10, 2, 2]] [9, 0, 3] → [[9, 1, 5], [10, 2, 2], [12, 0, 4]] [9, 1, 5] → [[10, 2, 2], [12, 0, 4]] [10, 2, 2] → [[12, 0, 4], [13, 2, 3]] [12, 0, 4] → [[13, 2, 3], [16, 0, 5]] [13, 2, 3] → [[16, 0, 5], [17, 2, 4]] [16, 0, 5] → [[17, 2, 4]] [17, 2, 4] → []

表中的编号只区分本例对象,请先确认输入顺序和单位。零值、空列表与尚未定义是不同状态,不能合并解释。分数保留准确含义,近似小数只用于展示;复算时应从完整输入出发,不能把已经四舍五入的显示值当成新的原始数据。

怎样核对结果

相同时间不代表重复事件,本例保留全部记录。表格列出各路输入和每次输出后的候选队首,可以检查是否错误跳过一项。最终输出应按约定的三个字段有序,并且每个输入身份恰好出现一次。

用把全部事件放到一起按同一比较键排序的方式,可以独立核对这个小例子。来源编号仅用于同时间的稳定排序,不意味着它更重要。实际系统若需要不同优先级,必须把优先级明确加入比较键,而不是依靠偶然的插入顺序。

边界与限制

每路输入已经排序是前提。如果某一路后来才提供更早的时间,单靠当前队首就不能保证全局顺序,需要另加缓冲或延迟约定。本例没有实时等待、丢包或不同设备时钟换算,不能把合并规则当成完整网络同步方案。

如果想比较另一套设置,可以先只修改一个条件,观察第一个发生变化的中间结果。出现分歧时先查规则、边界和同值处理,再查计算过程。把输入与过程一起保存,才方便判断差异来自真正的机制变化,还是某一步记录或实现错误。