固定容量的环形缓冲区会把新记录写回开头,物理数组中编号小的位置不一定更早。读取时间顺序必须同时知道写入位置和已保存数量。
先固定规则与数据
容量固定,写入指针指向下一次要写的位置。每次写入后指针循环前进,数量达到容量后不再增加,覆盖的始终是最旧记录。空位置用空值表示,记录带唯一编号以区分相同数据。
容量5,记录编号一至十八,值列表[9, 2, 4, 2, 7, 6, 1, 5, 2, 5, 3, -5, 4, 9, -1, 8, 6, 2]
逐项记录过程
写入编号1、值9,物理槽[1, None, None, None, None],下一写入位置1,数量1,按时间读出编号[1],被覆盖编号None。
写入编号2、值2,物理槽[1, 2, None, None, None],下一写入位置2,数量2,按时间读出编号[1, 2],被覆盖编号None。
写入编号3、值4,物理槽[1, 2, 3, None, None],下一写入位置3,数量3,按时间读出编号[1, 2, 3],被覆盖编号None。
写入编号4、值2,物理槽[1, 2, 3, 4, None],下一写入位置4,数量4,按时间读出编号[1, 2, 3, 4],被覆盖编号None。
写入编号5、值7,物理槽[1, 2, 3, 4, 5],下一写入位置0,数量5,按时间读出编号[1, 2, 3, 4, 5],被覆盖编号None。
写入编号6、值6,物理槽[6, 2, 3, 4, 5],下一写入位置1,数量5,按时间读出编号[2, 3, 4, 5, 6],被覆盖编号1。
写入编号7、值1,物理槽[6, 7, 3, 4, 5],下一写入位置2,数量5,按时间读出编号[3, 4, 5, 6, 7],被覆盖编号2。
写入编号8、值5,物理槽[6, 7, 8, 4, 5],下一写入位置3,数量5,按时间读出编号[4, 5, 6, 7, 8],被覆盖编号3。
写入编号9、值2,物理槽[6, 7, 8, 9, 5],下一写入位置4,数量5,按时间读出编号[5, 6, 7, 8, 9],被覆盖编号4。
写入编号10、值5,物理槽[6, 7, 8, 9, 10],下一写入位置0,数量5,按时间读出编号[6, 7, 8, 9, 10],被覆盖编号5。
写入编号11、值3,物理槽[11, 7, 8, 9, 10],下一写入位置1,数量5,按时间读出编号[7, 8, 9, 10, 11],被覆盖编号6。
写入编号12、值-5,物理槽[11, 12, 8, 9, 10],下一写入位置2,数量5,按时间读出编号[8, 9, 10, 11, 12],被覆盖编号7。
写入编号13、值4,物理槽[11, 12, 13, 9, 10],下一写入位置3,数量5,按时间读出编号[9, 10, 11, 12, 13],被覆盖编号8。
写入编号14、值9,物理槽[11, 12, 13, 14, 10],下一写入位置4,数量5,按时间读出编号[10, 11, 12, 13, 14],被覆盖编号9。
写入编号15、值-1,物理槽[11, 12, 13, 14, 15],下一写入位置0,数量5,按时间读出编号[11, 12, 13, 14, 15],被覆盖编号10。
写入编号16、值8,物理槽[16, 12, 13, 14, 15],下一写入位置1,数量5,按时间读出编号[12, 13, 14, 15, 16],被覆盖编号11。
写入编号17、值6,物理槽[16, 17, 13, 14, 15],下一写入位置2,数量5,按时间读出编号[13, 14, 15, 16, 17],被覆盖编号12。
写入编号18、值2,物理槽[16, 17, 18, 14, 15],下一写入位置3,数量5,按时间读出编号[14, 15, 16, 17, 18],被覆盖编号13。
最终应保留编号[14, 15, 16, 17, 18]。编号用于区分记录身份,值即使重复也不能合并成一条;物理数组的位置只用于存放,不承担时间先后含义。
独立复核的方法
按最近写入的顺序取最后容量条记录,应与从环形数组推导出的顺序一致。缓冲区恰好写满时,指针回到起点也不能当作空,因为已保存数量仍等于容量。
建议先按原始数据自己算一遍,保留中间状态后再与本例对照。发生分歧时,先寻找最早不同的步骤,检查边界是否包含、编号与坐标方向是否一致,以及状态是在事件之前还是之后更新。最终结果相同并不能替代对过程规则的理解,修改输入后也需要重新核算。
使用范围
这里单线程执行,不涉及同时读写的同步问题。实际日志系统若有多个生产者,还需要额外的并发规则;单靠取余数不能保证记录不会被读到一半。
