ARTS

ARTS 是陈浩（网名左耳朵耗子）在极客工夫专栏里发动的一个流动，目标是通过分享的形式来保持学习。

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

本周内容

本周你将看到：

1. 多路归并排序的 Golang 实现。
2. Go 官网教你如何做性能剖析。
3. 项目经理真的很重要。

Algorithm

本周的算法题是一道链表和归并排序联合的题目：23. Merge k Sorted Lists.

这道题目的解法不生疏，对于用 Go 来解这道题的我来说，这道题的难点反而是在实现上。Go 中的 container/heap 我之前是不理解的，幸好在我决定本人实现一个堆之前尝试搜寻了一下 Go 是否有相似的工具。不过话说回来，container/heap这个工具也着实过于简略。只帮你实现堆化(heapify)，其余的堆内理论数据类型须要你本人定义，同时类型须要反对 Less() 办法，如果不反对的话须要你本人定义。此外你还要实现上述类型的 Pop() 和 Push() 办法对底层数据的具体操作形式。其余须要留神的中央我都有曾经写在正文中了。

func mergeKLists(lists []*ListNode) *ListNode {if len(lists) == 0 {return nil}

    var fhead = &ListNode{}
    h := &IntHeap{}
    heap.Init(h)

    for i := range lists {if lists[i] == nil {continue}
        heap.Push(h, node{Val: lists[i].Val, ListIdx: i})
        lists[i] = lists[i].Next
    }

    curr := fhead
    // container/heap 会主动帮你做 heapify
    // 每次从小顶堆 pop 之后要从原来的 list 中再取出一个 node
    // 如果原来的 list 为空就持续 pop
    // 这也就是为什么不间接存 ListNode.Val 到 heap 里
    // 为了保留以后从堆 pop 进去的值来自哪个 list 专门申明了 node 类型
    // 另外，可能你会对为什么肯定要从 pop 进去的值原来的 list 再取一个 node
    // 起因在于，本地的 merge 逻辑就是随时都在堆里放以后所有 list 的最小值
    // 每次都从原 list 取一个值放进堆里，这个值被 push 进去之后可能不会成为堆顶
    // 然而成为一旦原 list 的下一个值可能成为堆顶或者可能在其被 push 进堆之前成为堆顶
    // 就会造成最终 merge 排序的乱序
    // 所以最持重和简略的做法就是每次都从原 list 找下一个值 push 到堆里
    for h.Len() > 0 {n := heap.Pop(h).(node)
        curr.Next = &ListNode{Val: n.Val}
        if lists[n.ListIdx] != nil {
            heap.Push(h, node{Val:     lists[n.ListIdx].Val,
                ListIdx: n.ListIdx})
            lists[n.ListIdx] = lists[n.ListIdx].Next
        }
        curr = curr.Next
    }
    return fhead.Next
}

type node struct {
    Val     int
    ListIdx int
}

type IntHeap []node

func (h IntHeap) Len() int { return len(h) }

// Less 递增示意形成小顶堆
func (h IntHeap) Less(i, j int) bool {return h[i].Val < h[j].Val }

func (h IntHeap) Swap(i, j int) {h[i], h[j] = h[j], h[i] }

func (h *IntHeap) Push(x interface{}) {*h = append(*h, x.(node))
}

func (h *IntHeap) Pop() interface{} {ret := (*h)[len(*h)-1]
    *h = (*h)[:len(*h)-1]
    return ret
}

Review 文章举荐

本周举荐的文章是 Go 官网的一篇性能调优的科普文章：Profiling Go Programs.

这篇文章其实是对上面这篇论文 Loop Recognition in C++/Java/Go/Scala 的一个官网回应，因为论文里的几种语言性能的测试后果对 Golang 很不「敌对」。总之从后果来看 Go 在上述基准测试中的体现都不太好，Go 官网示意并「不是咱们性能不太好，而是你们不互用！」

The Go program presented in that paper runs quite slowly, making it an excellent opportunity to demonstrate how to use Go’s profiling tools to take a slow program and make it faster.

怎么样，是不是感觉似曾相识？

于是官网把怎么应用 pprof 工具开始，再到具体优化 Go 代码的 CPU 占用和内存应用效率，全在这篇文章里介绍了一遍。当然，对于具体的优化内容不可能八面玲珑。文中次要是对某些数据类型是不必不当（比方将 map 改成 slice）升高 CPU 的使用率，对某些频繁创立和删除的对象做了本地缓存来升高内存申请和垃圾回收对 CPU 的耗费。

下面的两项措施从基准后果来看效果显著，而后作者不忘讥嘲一下之前那篇论文。

Having a garbage-collected language doesn’t mean you can ignore memory allocation issues. In this case, a simple solution is to introduce a cache so that each call to FindLoops reuses the previous call’s storage when possible. (In fact, in Hundt’s paper, he explains that the Java program needed just this change to get anything like reasonable performance, but he did not make the same change in the other garbage-collected implementations.)

最初，一顿操作之后，作者给出了优化的后果：比论文中的论断至多能够快 6 倍到 11 倍。同时，作者强调「还有」能够优化的中央存在。然而，后续的优化操作在应用的工具和办法上，与上述优化过程中应用过的工具和办法没有任何区别。

There’s more we can do to clean up the program and make it faster, but none of it requires profiling techniques that we haven’t already shown.

最初的最初，作者还要补充一句 Go 和 C++ 能够在「某种程度上」并驾齐驱。

Benchmarks are only as good as the programs they measure. We used go tool pprof to study an inefficient Go program and then to improve its performance by an order of magnitude and to reduce its memory usage by a factor of 3.7. A subsequent comparison with an equivalently optimized C++ program shows that Go can be competitive with C++ when programmers are careful about how much garbage is generated by inner loops

Tip 编程技巧

本周很想找到一个变成技巧，但我还是失败了。哭干了眼泪。

Share 灵光一闪

周五早晨和一个老同学聊到了一些在各自不同的公司项目管理模式的经验。对于我目前的工作来说，我的项目的进度齐全不须要我去思考，因为有我的项目经验在负责举荐整个我的项目。我只须要负责我本人的局部，保障能按时实现。如果有对接的其余部门或者团队的开发进度比预期更慢的话，我都会让项目经理去解决。而我的同学所在的公司在这方面仿佛分工并不严格，导致我的这位同学默默做了很多督促对接团队我的项目进度的工作，甚至是为对方的团队进行了一些情谊支援式的开发工作。

然而，我的项目到最初还是未能按期交付。对方的团队领导反而感觉我这位同学工作内容不够饱和，始终是「嘴强王者」，而事实上他曾经提前半个月实现了本人的开发工作。这种事件在我这里是不可能产生了，我首先就不可能跑去别的团队督促他们的工作进度。因为那不是我的职责，再者因为我不理解对方的我的项目排期和优先级等等等，我更绝不可能去插手其余团队。

说实话听到我这个同学的经验，我是震惊的。首先我无奈了解他为什么会插手其余团队的工作，再次我也无奈了解对方团队这种恻隐之心的行为。这些原本应该由项目经理实现的工作，如果平时的开发顺利的话，是很难留神到的。可一旦产生了某些问题导致我的项目须要人为推动，那么项目经理的重要性就会凸显进去。

所以在平时的开发中，不要总感觉项目经理就是催你我干活的，他们少数时候都是在帮你解决很多你相对不想本人解决的问题。

本周浏览列表

• 极客工夫 MySQL 实战 45 讲
  行锁
• 通过动画学习 Raft 协定
  艰深！易懂！也易忘，哈哈哈。