ARTS 是陈浩（网名左耳朵耗子）在极客时间专栏里发起的一个活动，目的是经过分享的方式来坚持学习。node
每人每周写一个 ARTS：Algorithm 是一道算法题，Review 是读一篇英文文章，Technique/Tips 是分享一个小技术，Share 是分享一个观点。
本周你将看到：golang
本周的算法题是一道链表和归并排序结合的题目：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
}
本周推荐的文章是 Go 官网的一篇性能调优的科普文章：Profiling Go Programs.api
这篇文章实际上是对下面这篇论文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.
怎么样，是否是感受似曾相识？app
因而官方把怎么使用 pprof 工具开始，再到具体优化 Go 代码的 CPU 占用和内存使用效率，全在这篇文章里介绍了一遍。固然，对于具体的优化内容不可能面面俱到。文中主要是对某些数据类型是不用不当（好比将 map 改为 slice）下降 CPU 的使用率，对某些频繁建立和删除的对象作了本地缓存来下降内存申请和垃圾回收对 CPU 的消耗。工具
上面的两项措施从基准结果来看效果显著，而后做者不忘嘲讽一下以前那篇论文。oop
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
本周很想找到一个变成技巧，但我仍是失败了。哭干了眼泪。
周五晚上和一个老同窗聊到了一些在各自不一样的公司项目管理模式的经历。对于我目前的工做来讲，项目的进度彻底不须要我去考虑，由于有项目经历在负责推荐整个项目。我只须要负责我本身的部分，保证能按时完成。若是有对接的其余部门或者团队的开发进度比预期更慢的话，我都会让项目经理去解决。而个人同窗所在的公司在这方面彷佛分工并不严格，致使个人这位同窗默默作了不少催促对接团队项目进度的工做，甚至是为对方的团队进行了一些友情援助式的开发工做。
然而，项目到最后仍是未能定期交付。对方的团队领导反而以为我这位同窗工做内容不够饱和，一直是「嘴强王者」，而事实上他已经提早半个月完成了本身的开发工做。这种事情在我这里是不可能发生了，我首先就不可能跑去别的团队催促他们的工做进度。由于那不是个人职责，再者由于我不了解对方的项目排期和优先级等等等，我更毫不可能去插手其余团队。
说实话听到我这个同窗的经历，我是震惊的。首先我没法理解他为何会插手其余团队的工做，再次我也没法理解对方团队这种乘人之危的行为。这些原本应该由项目经理完成的工做，若是平时的开发顺利的话，是很难注意到的。可一旦发生了某些问题致使项目须要人为推动，那么项目经理的重要性就会凸显出来。
因此在平时的开发中，不要总以为项目经理就是催你我干活的，他们多数时候都是在帮你解决不少你绝对不想本身解决的问题。