使用 Go 实现快速排序

快速排序(quick sort)号称是二十世纪最伟大的十大算法之一(The Best of the 20th Century: Editors Name Top 10 Algorithms), 但是快速排序也是最不容易实现的排序算法之一 ()。虽然它的原理非常的简单,但实现起来很容易出错。 也曾因为快排导致腥风血雨甚至网站攻击事件。

快速排序由C. A. R. Hoare在1962年提出。它的基本思想是:通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列。

分治法:将问题分解为若干个规模更小但结构与原问题相似的子问题。递归地解这些子问题,然后将这些子问题的解组合为原问题的解。

利用分治法可将快速排序的分为三步:

  • 在数据集之中,选择一个元素作为”基准”(pivot)。
  • 所有小于”基准”的元素,都移到”基准”的左边;所有大于”基准”的元素,都移到”基准”的右边。这个操作称为分区 (partition) 操作,分区操作结束后,基准元素所处的位置就是最终排序后它的位置。
  • 对”基准”左边和右边的两个子集,不断重复第一步和第二步,直到所有子集只剩下一个元素为止。

快速排序平均时间复杂度为O(n log n),最坏情况为O(n2),不稳定排序。

阅读全文

Go Channel 应用模式

Channel是Go中的一种类型,和goroutine一起为Go提供了并发技术, 它在开发中得到了广泛的应用。Go鼓励人们通过Channel在goroutine之间传递数据的引用(就像把数据的owner从一个goroutine传递给另外一个goroutine), Effective Go总结了这么一句话:

Do not communicate by sharing memory; instead, share memory by communicating.

Go内存模型指出了channel作为并发控制的一个特性:

A send on a channel happens before the corresponding receive from that channel completes. (Golang Spec)

除了正常的在goroutine之间安全地传递共享数据, Channel还可以玩出很多的花样(模式), 本文列举了一些channel的应用模式。

促成本文诞生的因素主要包括:

  1. eapache的channels库
  2. concurrency in go 这本书
  3. Francesc Campoy的 justforfun系列中关于merge channel的实现
  4. 我在出版Scala集合手册这本书中对Scala集合的启发

下面就让我们以实例的方式看看这么模式吧。

阅读全文

[译]使用 LLDB 调试 Go 程序

我一般调试Go程序都是通过log日志,性能调试的话通过 pprof 、trace、flamegraph等,主要是Go没有一个很好的集成的debugger,前两年虽然关注了delve,但是在IDE中集成比较粗糙,调试也很慢,所以基本不使用debugger进行调试, 最近看到滴滴的工程师分享的使用debugger在调试Go程序,我觉得有必要在尝试一下这方面的技术了。

本文翻译自 Debugging Go Code with LLDB, 更好的调试Go程序的工具是delve, 因为它是专门为Go开发, 使用起来也很简单,并且还可以远程调试。delve的命令还可参考: dlv cli,但是流行的通用的基础的debugger也是常用的手段之一。我在译文后面也列出了几篇其它关于go debug的相关文章,有兴趣的话也可以扩展阅读一下。

阅读全文

go addressable 详解

Go语言规范中规定了可寻址(addressable)对象的定义,

For an operand x of type T, the address operation &x generates a pointer of type *T to x. The operand must be addressable, that is, either a variable, pointer indirection, or slice indexing operation; or a field selector of an addressable struct operand; or an array indexing operation of an addressable array. As an exception to the addressability requirement, x may also be a (possibly parenthesized) composite literal. If the evaluation of x would cause a run-time panic, then the evaluation of &x does too.

对于一个对象x, 如果它的类型为T, 那么&x则会产生一个类型为*T的指针,这个指针指向x, 这是这一段的第一句话,也是我们在开发过程中经常使用的一种获取对象指针的一种方式。

阅读全文

10秒钟,让你的方法变为RPC服务

GitHub stars

rpcx一个服务治理的Go RPC框架, 拥有非常多的特性,支持跨语言的服务调用。 众多的特性可以参考doc.rpcx.site。它的服务治理的特性深受阿里巴巴的Dubbo框架的启发。

在实际的产品应用中,用户使用两台服务器+8台日志搜集服务(Client),轻松处理每天几十亿的服务调用, 除了中间一个路由器硬件闪断, 整个系统平稳运行多半年。 相比较之前Java的实现, 服务器节省了一半。 用户使用rpcx框架重构后的系统每月为公司节省了几十万元的成本。

rpcx框架的一个设计哲学就是简单。不希望用户需要花费大量的时间在框架的学习上,并且不需要proto文件或者重复且冗余的服务配置。最少只需要10行代码就可以创建一个服务, 如果需要额外的配置,也只需要几十行的代码。

虽然rpcx开发简单,但是作为开发人员来说,如果可以更加的偷懒, 那更是极好的一件事情了,这就是xgen开发的目的。

这个工具可以搜寻指定的package下可以配置成rpcx服务的类型, 并且生成一个服务器程序,将这些服务注册到服务器程序中。你可以指定是否需要zookeeperetcdconsul作为注册中心。

这个工具的开发参考了Go的tools的实现以及DigitalOcean公司的Fatih Arslan
开发的gomodifytags的实现。

阅读全文

使用二进制形式发布go package

我们在使用Go进行开发的时候, 经常会使用到第三方的库, 这时候我们一般都会通过go get到github.com、bitbucket或者自己私有库中去拉取第三库的源代码。 今天正好群里有网友问能不能将自己开发的库以二进制形式提供给用户,我就顺便整理了一下。

以二进制方式提供库的动机可能是为了保护自己公司的知识产权,也有可能是从安全的角度考虑,避免一些关键信息的泄漏等等,这不是本文讨论的范围。

阅读全文

[转]编写高性能的Go代码的最佳实践

原文: go-perfbook/performance

This document outlines best practices for writing high-performance Go code.

At the moment, it's a collection of links to videos, slides, and blog posts
("awesome-go-performance"), but I would like this to evolve into a longer book
format where the content is here instead of external. The links should be sorted into categories.

All the content will be licensed under CC-BY-SA.

阅读全文