ARTS 第7周 | LeetCode 最低公共祖先 | Golang Worker Pool 原型 | 编程之禅

ARTS

ARTS 是陈浩（网名左耳朵耗子）在极客时间专栏里发起的一个活动，目的是通过分享的方式来坚持学习。

每人每周写一个 ARTS：Algorithm 是一道算法题，Review 是读一篇英文文章，Technique/Tips 是分享一个小技术，Share 是分享一个观点。

本周内容

本周的 ARTS 你将看到：

1. 经典题「树中节点的最低公共祖先」
2. 一个 Golang 多队列的 worker-dispatcher 原型
3. 关于编程的方法论

Algorithm

这周的算法题是「树中节点的最低公共祖先」。

[235. Lowest Common Ancestor of a Binary Search Tree

]( https://leetcode.com/problems...

[236. Lowest Common Ancestor of a Binary Tree

]( https://leetcode.com/problems...

这两道题相同之处都是需要求公共祖先，但不同的是「二叉树」还是「二叉查找树」的最低公共祖先。对于二叉树，只能通过后序遍历来求。但是如果给出的两个节点如果互为父子的话，就无法通过简单的后序遍历来判断了，需要单独判断。这种方法对于任何的二叉树都是适用的，当然也包含二叉查找树 BST. 如果对 BST 的公共祖先也是用这种方式的话，因为没有利用 BST 本身的排序特性，必然时间复杂度上会吃亏。话不多说，直接上代码吧，欢迎拍砖。

先是普通二叉树节点的最低公共祖先代码。

func lowestCommonAncestor(root, p, q *TreeNode) *TreeNode {    // dfs 函数里的逻辑没办法包含 p q 互为父子的情况    // 这里只能单独判断    if isAcst(p, q) {        return p    }    if isAcst(q, p) {        return q    }    var ans *TreeNode    var dfs func(node, p, q *TreeNode) (bool, bool)    dfs = func(node, p, q *TreeNode) (bool, bool) {        if node == nil {            return false, false        }        leftFoundP, leftFoundQ := dfs(node.Left, p, q)        rightFoundP, rightFoundQ := dfs(node.Right, p, q)        foundP, foundQ := leftFoundP || rightFoundP, leftFoundQ || rightFoundQ        // 因为是后序遍历，暂时想不到很好的剪枝办法        if ans == nil && (foundP && foundQ) {            ans = node            return true, true        }        if node == p {            foundP = true        }        if node == q {            foundQ = true        }        return foundP, foundQ    }    fp, fq := dfs(root, p, q)    if ans == nil && (fp && fq) {        ans = root    }    return ans}// return p if p is ancestor of qfunc isAcst(p, q *TreeNode) bool {    var found bool    var find func(node *TreeNode)    find = func(node *TreeNode) {        if node == nil {            return        }        if found {            return        }        if node == q {            found = true            return        }        find(node.Left)        find(node.Right)    }    find(p)    return found}

然后是 BST 中节点的最低公共祖先。

// 首先这是一棵 BST 祖先节点的值// 利用 BST 的性质，祖先节点的 Val 介于 p.Val q.Val 之间// 反之，如果不介于二者之间的值是 p q 的祖先节点， 那么一定存在更底层的祖先节点 func lowestCommonAncestor(root, p, q *TreeNode) *TreeNode {    var ans *TreeNode    node := root    for !in(node, p, q) {        if node == nil {            break        }        if node.Val > max(p, q).Val {            node = node.Left        }        if node.Val < min(p, q).Val {            node = node.Right        }    }    if node != nil {        ans = node    }    return ans}func in(node, p, q *TreeNode) bool {    return node.Val >= min(p, q).Val && node.Val <= max(p, q).Val }func min(p, q *TreeNode) *TreeNode {    if p.Val < q.Val {        return p    }    return q}func max(p, q *TreeNode) *TreeNode {    if p.Val > q.Val {        return p    }    return q}

Review 文章推荐

本周的文章推荐是 Handling 1 Million Requests per Minute with Golang . 文中介绍了一个高并发场景下的 Golang 多队列的 worker-dispatcher 模式原型，虽然是很久之前的文章，但目前来看类似的 w-d 模型依然大同小异。

但是跳出条框的舒服，上面文中的多队列方式的 workerpool 和各种 channel 入门中提到的单队列方式（一个协程写 chan 多个协程并发读 chan）的根本区别是什么呢？

我目前的直观感受就是，高并发的情况都各队列的 chan 就能多缓存一些 job（这里指使用 chan 的 buffer），相比单队列 chan 在高并发量的情况下更不容易出现 chan 满导致拒绝 job 请求。但我想这应该是在 cpu 处理能力足够的前提下，如果 cpu 处理能力本身就不足那就谈不上多队列更高效这种可能。

其实类似的问题有很多，这种问题无法用公式和算法之类的东西确切描述，像极了常说的「经验」。但是开发人员一般都是更愿意想相信专家而不是经验，这就很有意思了。

Tip 编程技巧

本周依然没有技巧。嚎啕大哭。

Share 灵光一闪

这一周的灵光一闪是关于上面文章中提到的关于编程中那些「经验」的一些看法。这些经验经常可以在分布式系统以及操作系统中找到，多数时候乍一看感觉非常正确，但有无法给出公式般准确的推导过程。给人一种既神秘又强大的感觉，以我目前的 conding 能力还很难掌握这些经验。甚至在未来的某个阶段这些经验会是我最需要学习的东西，这都很难说。

我暂时把这些「经验」叫做编程之禅。

本周阅读列表

Go语言设计与实现

官方对 defer panic 和 recover 的介绍

官方 Go Concurrency Patterns: Timing out, moving on

文中的观点，select case 的方式等待 chan 的可读或者可写时，如果使用了 default 分支的话，就相当于非阻塞？

Handling 1 Million Requests per Minute with Golang