Go
by smallnest

使用 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)，不稳定排序。

阅读全文

by smallnest

搭建IPFS私有网络

IPFS (InterPlanetary File System) 是一个面向全球的、点对点的分布式版本文件系统。它用基于内容的地址替代基于域名的地址，也就是用户寻找的不是某个地址而是储存在某个地方的内容，不需要验证发送者的身份，而只需要验证内容的哈希，通过这样可以让网页的速度更快、更安全、更健壮、更持久。IPFS表示，IPFS未来将替代HTTP（以及其他的许多东西）。

IPFS 和 BitTorrent 的区别: How does it compare to BitTorrent's Project Maelstrom?

IPFS从根本上改变了用户搜索的方式。通过IPFS，用户搜索的是内容。通过HTTP浏览器搜索文件的时候，首先找到服务器的位置（IP地址），然后使用路径名称在服务器上查找文件。按照这个设计，只有文件所有者可以判断这是否是用户要找的文件。此时，必须保证托管者不会通过移除文件或者关闭服务器而对文件做任何更改。

当文件被添加到IPFS节点上，它得到一个新的名字。这个名字实际上是一个加密哈希，它是从文件内容中被计算出来。通过加密保证该哈希始终只表示该文件的内容。哪怕只在文件中修改一个比特的数据，哈希都会完全不同。

当下一步向IPFS分布式网络询问哈希的时候，它通过使用一个分布式哈希表，可以快速（在一个拥有10,000,000个节点的网络中只需要20跳）地找到拥有数据的节点，从而检索该数据，并使用哈希验证这是否是正确的数据。

不幸的是， IPFS 被墙了。如果你有幸能翻墙，你可以通过通过下面的命令下载并安装预编译的ipfs工具。

1
2
3
tar xvfz go-ipfs.tar.gz
cd go-ipfs
./install.sh

然后初始化仓库:

1
2
3
4
5
6
7
8
> ipfs init
initializing ipfs node at /Users/jbenet/.go-ipfs
generating 2048-bit RSA keypair...done
peer identity: Qmcpo2iLBikrdf1d6QU6vXuNb6P7hwrbNPW9kLAH8eG67z
to get started, enter:
  ipfs cat /ipfs/QmYwAPJzv5CZsnA625s3Xf2nemtYgPpHdWEz79ojWnPbdG/readme

它默认会在你的Home下创建一个.ipfs文件夹。

1
ipfs cat /ipfs/QmYwAPJzv5CZsnA625s3Xf2nemtYgPpHdWEz79ojWnPbdG/readme

查看ipfs网络上的一个文件，正常你可以看到这个文件的内容。

你可以使用ipfs add上传文件，ipfs cat查看文件。当然ipfs包含很多的命令，你可以在 commands 页面查看每个命令。

默认IPFS会通过一些种子连接到IPFS全球网络， 如果你想搭建一个私有的IPFS网络，可以使用本文下面介绍的方法。

阅读全文

Go
by smallnest

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集合的启发

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

阅读全文

Java
by Mahmoud Anouti

[译]20个使用 Java CompletableFuture的例子

在Java中异步编程，不一定非要使用rxJava, Java本身的库中的CompletableFuture可以很好的应对大部分的场景。

原文: 20 Examples of Using Java’s CompletableFuture, 作者 Mahmoud Anouti。

这篇文章介绍 Java 8 的 CompletionStage API和它的标准库的实现 CompletableFuture。API通过例子的方式演示了它的行为，每个例子演示一到两个行为。

既然CompletableFuture类实现了CompletionStage接口，首先我们需要理解这个接口的契约。它代表了一个特定的计算的阶段，可以同步或者异步的被完成。你可以把它看成一个计算流水线上的一个单元，最终会产生一个最终结果，这意味着几个CompletionStage可以串联起来，一个完成的阶段可以触发下一阶段的执行，接着触发下一次，接着……

除了实现CompletionStage接口， CompletableFuture也实现了future接口, 代表一个未完成的异步事件。CompletableFuture提供了方法，能够显式地完成这个future,所以它叫CompletableFuture。

阅读全文

Go
by smallnest

[译]使用 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的相关文章，有兴趣的话也可以扩展阅读一下。

阅读全文