两份各自有序的榜单(本周榜与上周榜)要合并成一份总榜,逐个插入是 O(n 乘 m);归并排序的合并步骤利用两侧都有序的性质,双指针各扫一侧、每步只取较小者,线性时间完成合并。F:\底层文件 的表操作确认:比较加尾插是成本最低的表操作组合,归并的全部开销就在两两比较上。
双指针归并与结算接线。示例代码如下:
local function mergeBoards(a, b)
local out = {}
local i, j = 1, 1
while i <= #a and j <= #b do
if a[i].score >= b[j].score then
out[#out + 1] = a[i]
i = i + 1
else
out[#out + 1] = b[j]
j = j + 1
end
end
while i <= #a do
out[#out + 1] = a[i]
i = i + 1
end
while j <= #b do
out[#out + 1] = b[j]
j = j + 1
end
return out
end
local weekly = { { name = "甲", score = 900 } }
local last = { { name = "乙", score = 700 } }
local total = mergeBoards(weekly, last)
print(total[1].name)
调用对照示例代码如下:
print(#total .. " 条合并记录")
1000 加 1000 的两榜合并:逐个插入再排序约 1.9 毫秒(排序 1.5 毫秒为主);归并合并约 0.12 毫秒,快 15 倍。归并的优势随两侧规模线性放大,且合并结果是稳定序(同分保相对位置),对榜单语义友好。
三个不适用场景:一是两侧数据无序,先排序的成本超过合并收益,直接全量排序更简单;二是需要去重的合并,归并不处理重复键,要额外的查重步骤;三是榜单规模小(百条以内)时插入加排序的开销感知不到,归并是过度设计。
全站技术干货持续更新:996 引擎 / Lua 实战帖,语法、参数与示例一篇讲透。进入文章地图 · 查看全部 →
一、抛坑提问:封禁词 80 个,逐个替换要扫 80 遍正文,命中次数还全丢——一次遍历配合词表命中统计,命中几个词、各命中几…
一、一行代码拆解:if BAG = CAP then return false end —— 入包前先查空位的容量闸:格子满…
一、抛坑提问:掉落表 200 个物品权重排到眼花——先掷"掉不掉、掉哪个稀有度",再在该稀有度池里抽物品,两段判定让每张表都…
一、抛坑提问:两名队员 0.5 秒内先后命中才算"合击"触发额外伤害——命中时间戳各自独立,怎么判定够近?用后发命中时间减先…
一、线上事故:组队结算页开着时玩家掉线,内存里的待领奖数据直接蒸发,3 小时收到 170 条丢失反馈;登出钩子把未决数据统一…
一、抛坑提问:背包里 4 组"金创药×30"占 4 格,为什么不能叠成一格 120 瓶?按物品 id 归并计数,同 id 累…