引子: filter_word

目前项目中很多文本识别能力, 是基于关键词匹配来做, 需要做去重处理以提高质量. 例如:

文本=贝多芬音乐会, 关键词={贝多芬, 多芬, …}, 只出{贝多芬}
文本=木林森马丁靴, 关键词={木林森, 森马, 马丁靴, …}, 只出 {木林森, 马丁靴}

等于是另外一种方式去做分词逻辑

看到项目里的一种实现

def filter_words_1(ac: set) -> set:
    # ac: [(词结束位置, 词), ...]
    return ac.difference(
        {
            (i, a)
            for i, a in ac
            for j, b in ac
            if (
                (a in b and a != b)
                or (i - len(a) + 1) <= (j - len(b) + 1) <= i < j
                or (j - len(b) + 1) < (i - len(a) + 1) <= j <= i
        )
        }
    )

assert filter_words_1({(2, '贝多芬'), (2, '多芬')}) == {(2, '贝多芬')}

好家伙, 先不论O(N**2)的复杂度, 从结果来看, 只要重叠的词全都不留, 香消玉损:

assert filter_words_1({(2, '木林森'), (3, '森马'), (5, '马丁靴')}) == set()

另外类似需求的实现, O(NlogN)的(排序导致的)复杂度, 看上去好像靠谱点.

def filter_words_2(ac) -> set:
    r = []
    ac = sorted(ac, key=lambda t: (t[0], -len(t[1])))  # 按照结束位置排序, 相同结束位置长的排前面
    x = ac[0]
    for y in ac[1:]:
        if x[0] < y[0] - len(y[1]) + 1:  # 当前词和备选词无重叠
            r.append(x)
            x = y
        elif len(y[1]) > len(x[1]):  # 有重叠且当前词更长, 换备选词
            x = y
    r.append(x)
    return set(r)

assert filter_words_2({(2, "木林森"), (3, "森马"), (5, "马丁靴")}) == {(2, "木林森"), (5, "马丁靴")}

注意到这里有个规则, 就是重叠留长词. 猜测是因为相较于短词, 长词误提取的概率更低. 不过进一步想想, 这个函数返回的结果特性是什么, 或者说计算目标是什么?

目标1: 返回最多的关键词?
目标2: 返回的关键词覆盖的文本长度最长?
目标3: 泛化形式, 不是什么东西越长/越多越好, 每个词有它相应的权重, 或者说基于词优先级规则去重?

好像都不是, 甚至连返回结果的不重叠都没保障. 随便找个反例:

# 期望: 只有 Mario Badescu
assert assert filter_words_2({(4, "rio"), (10, "des"), (12, "Mario Badescu")}) == {(4, "rio"), (12, "Mario Badescu")}
# 期望: 临停, 车位
assert filter_words_2({(1, '临停'), (3, '车位'), (3, '停车位')}) == {(3, '停车位')}

这个问题等价为 ISMP (interval scheduling maximization problem), 即找最大的可行子集.

离日常更近一点的形式表述: 一天超级多会议邀约, 你得选择参加其中不冲突的会议, 从而

目标1: 参加最多的会议?
目标2: 开会时间最长?
目标3: 泛化形式, 每个会议都有个收益, 确保一天会开完会的收益最多?

针对目标1的贪心解

参加最早结束的会议
拒绝所有和该会议冲突的会议
重复直到没有待确认的会议邀约

def filter_words_3(ac) -> set:
    r = []
    ac = sorted(ac, key=lambda t: (t[0], -len(t[1])))
    x = ac[0]
    for y in ac[1:]:
        # 当前词和备选词无重叠
        if x[0] < y[0] - len(y[1]) + 1:
            r.append(x)
            x = y
    r.append(x)
    return set(r)

assert filter_words_3({(2, "贝多芬"), (2, "多芬")}) == {(2, "贝多芬")}
assert filter_words_3({(2, "木林森"), (3, "森马"), (5, "马丁靴")}) == {(2, "木林森"), (5, "马丁靴")}
assert filter_words_3({(1, "临停"), (3, "车位"), (3, "停车位")}) == {(1, "临停"), (3, "车位")}
# 这里返回了最多的词组, 虽然期望是: 无线电法/国别/研究
assert filter_words_3({(2, "无线电"), (3, "无线电法"), (4, "法国"), (5, "国别"), (5, "别"), (7, "研究")}) == {
    (2, "无线电"),
    (4, "法国"),
    (5, "别"),
    (7, "研究"),
}

如何验证这个算法为什么是对的?

暴力穷举出所有的可能性, 断言该算法的结果是最优的. 但是基于计算的方式, 只能针对给定例子/范围断言, 不能证明正确性. 随手算下穷举验证的复杂度:

枚举给定数量N的复杂性: 2**N (所有组合拿出来轮一遍)
定长时间范围T内所有组合验证的复杂性:
1. T*T/2种会议时长安排方式, K=2**(T*T/2)-1种组合
2. 不考虑各种等价约化手段, \sum_{k=1}^K C_K^k 2^k = 3**K - 1 次计算
3. 定会议只能细到15分钟, 一天8小时最多T=32个时间片段, 算上去也就1后面244个0的量级
4. 考虑到约化的话, 环节2.可以去到O(3**K/3)=O(1.44**K), 也是1后面81个0的量级

所以暴力穷举是走不通的

P vs NP, 以及工作执行和验收的联想

上面的会议安排问题, O(NlogN)的解法, 实际计算验证其正确性, 却需要O(2**N)的复杂度, 实在是让人头大.

理想的情况当然是, 验证正确性的计算复杂度低于实际算法的复杂度?

简单的工作类比:

算法: 具体工作实施
验证: 工作结果评估
低端的工作: 随功能点数量指数级增长的代码量, 枚举所有的可能性, 一点也不约化问题, 看山是山, 上来就是干
高端的工作: 多项式时间的解法, 平滑的代码量增长曲线, 带点分治想法, 最好还带点memorization/backtracking, 能够举一反三
低端的评估: 对不对不知道, 全靠线上出故障, 工作具体是花了一天干活摸四天鱼, 还是一周实打实磨出来的, 看不清
高端的评估: 一眼看出来是否有缺陷, 而且能看出来对方真正花了多少时间

P vs NP 的问题, 说的是: 一个能快速验证结果正确性的问题, 是否一定有快速被解决的算法?

从直觉上, 或者从感情上来说, 不应当是的 (P != NP), 否则工厂质检员的能力超过所有的流水线工人之和才能胜任? 如何进行有效的团队管理? 或者换个角度说, 要啥工作分配和验收啊! 分配工作的时候, 如果工作是否完成的检查条件/量化指标都非常充分, 那么只消稍微再多做一点点, 事情就已经做完了!

不过为什么没人问: 有多项式时间的算法, 是否一定有多项式时间验证的方式? 因为算法首先一定是论证其正确性之后才谈复杂度的, “随缘”输出结果, 不保证任何规则的计算过程, 都是垃圾!

逻辑推导”贪心解”的正确性

暴力穷举行不通, 这时候需要发挥逻辑推理的能力了, 且听我”狡辩”:

“贪心解”决定参加了会议A, 并拒绝了与之冲突的所有会议B, C, D;
由于B, C, D和A的结束时间冲突了, 所以B, C, D也一定冲突了, 那么在”最优解”里, 如果没有A, 则B, C, D最多只有其一
因此我们建立了”贪心解”每个选择和最优解集合选择的”至多一”关系, 因此”贪心解”的会议数量一定不会少于”最优解”
QED

那么针对目标2/3的算法呢?

一开始觉得问题差不多, 应该是简单的推广, 但是琢磨半天发现, 没有预想的那么简单.

等价为 MWIS (maximum weight independent set): 即找图上最大的顶点集合, 使得满足:

任意两顶点间无边关系
顶点权重和最大

这里

顶点: 会议
邻边: 两个会议是否冲突

对于任意图, 这个问题是NP-hard的. 但到我们这里, 这个图结构很特殊, 是有多项式求解的, 具体也没深入研究下去 (TODO).

为什么Deadline是第一生产力, 以及柿子专挑软的捏

回到我们”贪心解”, 我们贪心的是最早结束时间, 类似的, 在任务调度策略上, 不论抢占还是非抢占调度场景, EDF (Earliest deadline first) 都是最优策略.

这里最优指的是吞吐, 即单位时间完成任务数量.

同样的道理, 干活时候”柿子专挑软的捏”, 手头任务排优先级的时候, 永远优先去做简单, 耗时最短的任务, 那么一天下来, 完成的任务数一定是最多的.

当然, 前提是对于任务难度/耗时有非常精准的估算, 实际情况常常确是: 做之前以为自己是去捏蚂蚁, 做到最后发现自己是要去捕大象; 原本说本月必须上线, 结果再回首, 发现已是去年的需求.

对于抢占式任务调度来说, 即一个事情没完成的时候可以换去做另外一件事情, 会导致重要而长期的任务永远得不到执行. 如果我们总是做短平快的事情, 长期要做的重要的事情可能毫无进展. 如果我们不允许抢占调度, 长期挂在一个不能解决的事情里面, 会导致任务堆积毫无产出. 这也是为啥所谓”敏捷”里面大任务/史诗, 建议拆成更小的任务单元, 从而方便调度.

还记得被小学奥数题支配的恐惧么?

十几年前的作业题:

烧水沏茶时, 洗水壶要用1分钟, 烧开水要用10分钟, 洗茶壶要用5分钟, 洗茶杯要3分钟, 泡茶要5分钟, 找茶叶要3分钟, 如何安排才能尽早喝上茶?

这个问题暗含了任务并行度的假设 (几个人帮忙?/燃气灶几个头的?/水龙头个数?), 以及依赖关系 (烧水得先洗水壶, 泡茶得烧开水, …)

再难一点, 沏茶讲究的, 要水烧开1分钟内泡上, 这就等于再加上其他约束条件了.

十几年后工作上的问题, 安排数据任务的调度策略: 计算任务DAG依赖关系, 每个任务有需要的内存资源和耗时, 可以执行任务的机器就N台, 如何规划任务, 最快完成? 以及, 这个任务必须得这个小时内跑完才有意义, 咋整?

N=1的时候, 并行任务只有1的时候, 事情最简单, 也最慢, 就是树的线性化表达, 没啥好优化的. N>1, 且有并行的时候, 就没那么直观了. 再复杂一点, 异构的调度机器 (不同机器性能不同, 执行速度不一样, 不可预测的内存占用, 等等).

问题再放大一点, 工作中很多人的事情是需要协调的, 研发等需求, 数据等采集, 后端等前端, 上线卡测试, 一环扣一环, 每个事情都有期望的期限, 每个人做不同类型工作的效率也是不同的, 如何确保最优的工作安排?

这类问题在算法上就很难了, 落到实际工作就更难了, 因为算法的前提完全建立在, 你靠谱, 我靠谱, 他靠谱, 时间估算完全精确的前提下. 现实情况, 当然是大家多多少少不靠谱, 所以没有谁安排工作用算法先跑一轮?

排队论, 为甚么偷工作是好的, 以及如何说服运维加内存

以上的调度, 都是建立在所有任务已知, 且耗时确定的情况下. 实际情况是, 任务用时都是不确定性的, 我们常见的认知就是: 任务还有多久做完, 和已经花了多久时间毫无关系 (所谓无记忆性, 或者说不要纠结于沉没成本).

以及, 任务不是确定的, 完全提前安排好的, 在做的过程中, 不断的有新的任务到来插入.

这是我们常说的离线/实时系统的区别:

离线系统: 一般不要求失效性, 等待队列可以认为无限长
实时系统: 有限的队列空间, 任务有失效性要求

离线系统一般优化的是吞吐, 即单位时间处理完成任务数, 从整个系统的效率考虑; 而实时系统优化目标更侧重于平均任务等待时间, 从单个任务的感知角度考虑.

最简单的例子: 2TB数据 (图片1W张共1TB, 电影10部共1TB) 上传服务器

离线系统: 开车把磁盘运到机房, 用时1天, 吞吐2TB/日, 平均文件上传用时1天
实时系统: 网络上传, 先传图片, 再传视频, 耗时2日, 吞吐1TB/日, 平均文件上传用时0.5天多一点

在不确定的任务到达, 以及不确定的任务耗时情况下, 如何优化系统吞吐? 如何优化任务平均等待时间? 针对这些问题, 演化出了一门单独的学科: 排队论

排队论告诉我们, 在多个人协作的时候, 任务偷取式的调度是效率最高的: 这件事你还没开始做, 其它人做完了没事儿做了, 直接把这件事抢过来做.

这就是为什么Golang的调度器实现, 从一开始的GM改成了GMP模式, 增加了任务偷取流程.

此外排队论还指导我们, 处理速度/到达速度在各种分布的情况下, 在怎样的排队网络拓扑下, 会有怎样的概率等待队列长度会超过何种阈值, 以及我们需要预留多长的排队空间, 从而多大可能性上避免爆炸/拒绝服务.

所以下次遇到线上资源不足的情况, 先写一黑板公式, 数学推导论证一通, 最后得出结论:

加钱升级机器, 赶紧的!

filter_word引发的随想