几路回放或输入日志各自按时间排列,合并时可以只比较每一路当前最早的一项。取出一项后再补入同一路的下一项,就不必把所有事件重新打乱排序。
本例四路事件的时间可以相同,每个事件身份由来源编号和路内序号共同确定。比较键依次是时间、来源编号、路内序号;维护每一路尚未取出的队首,每次输出其中最小者,再推进对应来源。
四路输入编号零至三,记录顺序为时间、来源、路内序号。
来源0:[[5, 0, 0], [5, 0, 1], [9, 0, 2], [10, 0, 3], [14, 0, 4], [16, 0, 5]] 来源1:[[4, 1, 0], [8, 1, 1], [11, 1, 2], [12, 1, 3]] 来源2:[[3, 2, 0], [5, 2, 1], [7, 2, 2], [11, 2, 3], [12, 2, 4]] 来源3:[[3, 3, 0], [7, 3, 1], [8, 3, 2], [9, 3, 3], [13, 3, 4]] 每次输出及补入后的候选队首: [3, 2, 0] → [[3, 3, 0], [4, 1, 0], [5, 0, 0], [5, 2, 1]] [3, 3, 0] → [[4, 1, 0], [5, 0, 0], [5, 2, 1], [7, 3, 1]] [4, 1, 0] → [[5, 0, 0], [5, 2, 1], [7, 3, 1], [8, 1, 1]] [5, 0, 0] → [[5, 0, 1], [5, 2, 1], [7, 3, 1], [8, 1, 1]] [5, 0, 1] → [[5, 2, 1], [7, 3, 1], [8, 1, 1], [9, 0, 2]] [5, 2, 1] → [[7, 2, 2], [7, 3, 1], [8, 1, 1], [9, 0, 2]] [7, 2, 2] → [[7, 3, 1], [8, 1, 1], [9, 0, 2], [11, 2, 3]] [7, 3, 1] → [[8, 1, 1], [8, 3, 2], [9, 0, 2], [11, 2, 3]] [8, 1, 1] → [[8, 3, 2], [9, 0, 2], [11, 1, 2], [11, 2, 3]] [8, 3, 2] → [[9, 0, 2], [9, 3, 3], [11, 1, 2], [11, 2, 3]] [9, 0, 2] → [[9, 3, 3], [10, 0, 3], [11, 1, 2], [11, 2, 3]] [9, 3, 3] → [[10, 0, 3], [11, 1, 2], [11, 2, 3], [13, 3, 4]] [10, 0, 3] → [[11, 1, 2], [11, 2, 3], [13, 3, 4], [14, 0, 4]] [11, 1, 2] → [[11, 2, 3], [12, 1, 3], [13, 3, 4], [14, 0, 4]] [11, 2, 3] → [[12, 1, 3], [12, 2, 4], [13, 3, 4], [14, 0, 4]] [12, 1, 3] → [[12, 2, 4], [13, 3, 4], [14, 0, 4]] [12, 2, 4] → [[13, 3, 4], [14, 0, 4]] [13, 3, 4] → [[14, 0, 4]] [14, 0, 4] → [[16, 0, 5]] [16, 0, 5] → []
表中的编号只区分本例对象,请先确认输入顺序和单位。零值、空列表与尚未定义是不同状态,不能合并解释。分数保留准确含义,近似小数只用于展示;复算时应从完整输入出发,不能把已经四舍五入的显示值当成新的原始数据。
相同时间不代表重复事件,本例保留全部记录。表格列出各路输入和每次输出后的候选队首,可以检查是否错误跳过一项。最终输出应按约定的三个字段有序,并且每个输入身份恰好出现一次。
用把全部事件放到一起按同一比较键排序的方式,可以独立核对这个小例子。来源编号仅用于同时间的稳定排序,不意味着它更重要。实际系统若需要不同优先级,必须把优先级明确加入比较键,而不是依靠偶然的插入顺序。
每路输入已经排序是前提。如果某一路后来才提供更早的时间,单靠当前队首就不能保证全局顺序,需要另加缓冲或延迟约定。本例没有实时等待、丢包或不同设备时钟换算,不能把合并规则当成完整网络同步方案。
如果想比较另一套设置,可以先只修改一个条件,观察第一个发生变化的中间结果。出现分歧时先查规则、边界和同值处理,再查计算过程。把输入与过程一起保存,才方便判断差异来自真正的机制变化,还是某一步记录或实现错误。