计算平均值，复杂度O(1)

公会对象按以下形式缓存了所有成员的最新等级iLevel，要求实时刷新公会成员的【平均等级】，成员最多200人。

tMemberMap = 
{
    [角色ID1} = {iLevel=1, sPlayerName="xxx", ... }
    [角色ID2} = {iLevel=2, sPlayerName="xxx2", ... }
    ...
}

当成员加入或离开公会或角色升级，触发重刷平均等级，简单的做法是遍历tMemberMap计算出【等级总和】，后除以【成员人数】。公会成员最多只有200人，这样的做法绝对不会有性能问题。但这里我想发散一下，如果是海量数据呢？或者没有缓存信息tMemberMap呢？我分析了一下，还是依据公式【平均等级】=【等级总和】/【成员人数】，仅且只需4个数据就可以重新计算平均值，复杂度O(1)，

修改前的平均值avg，持续化在公会对象
修改前的成员人数size，持续化在公会对象
某成员等级旧值old，不需要持续化，等级变化前临时记录一下
某成员等级新值new，持续化在公会对象以上4个数据在大多数项目中，都能轻易获取到

当加入新成员时add(avg, size, new) 【修改前等级总和】 = avg * size 【修改后等级总和】=【修改前等级总和】 + new = avg * size + new 【修改后的成员人数】= size + 1 【平均等级】= 【修改后等级总和】/【修改后的成员人数】 = (avg * size + new) / (size + 1)
当移除成员时del(avg, size, old) 【修改前等级总和】 = avg * size 【修改后等级总和】=【修改前等级总和】 - old = avg * size - old 【修改后的成员人数】= size - 1 【平均等级】= 【修改后等级总和】/【修改后的成员人数】 = ((avg * size) - old) / (size - 1)
当成员升级时modify(avg, size, new, old) 先移除成员del(avg, size, old) 得出新的平均值avg2，和人数减1即size2 = size - 1 重新加入成员add(avg2, size2, new)

以下是lua版本实现

function add(avg, size, new)
    if size + 1 <= 0 then
        return 0
    end
    return ((avg * size) + new) / (size + 1)
end

function del(avg, size, old)
    if size - 1 <= 0 then
        return 0
    end
    return ((avg * size) - old) / (size - 1)
end

function modify(avg, size, new, old)
    local avg2 = del(avg, size, old)
    local size2 = size - 1
    return add(avg2, size2, new)
end)

原文:
https://lizijie.github.io/2021/11/14/%E8%AE%A1%E7%AE%97%E5%B9%B3%E5%9D%87%E5%80%BC-%E5%A4%8D%E6%9D%82%E5%BA%A6O(1).html
作者github:
https://github.com/lizijie