爱码士 发布的文章

导语

今天,我们来探讨下Go编程模式-函数式选项模式,英文叫Functional Optional。这是一个函数式编程的应用案例,目前在Go语言中比较流行的一种编程模式。某些业务对象在初始化时,如果属性多,大部分属性没有默认值,初始化的函数会非常冗长,代码也不好维护,下面就来看下函数式选项模式(Functional Optional)怎么解决这个问题。

业务对象的初始化

在实际的业务开发过程中,我们会经常性地需要对一个对象(或是业务实体)进行初始化。比如下面这个业务实体Company,又很多待初始化的列表:

type Company struct {
    Name      string
    ID        string
    Owner     string
    Addr      string
    Industry  string
    Product   string
    License   string
    Date      string
}

针对上面业务实体Company,有不少的属性字段(随便举的例子哈,不一定真实,用来理解下面的编程模式)

  1. Company下必填的属性是Name和ID,除了这两个之外,其他都是选填;
  2. 剩下的字段都是选填,必须有默认值;

我们需要有多种不同的创建 Company 的函数签名,如下所示:

func NewDefaultCompany(name string, id string) (*Company, error) {
    return &Company{name, id, "none", "china", "all", "none", "none", "none"}, nil
}

func NewCompanyWithOwner(name string, id string, owner string) (*Company, error) {
    return &Company{name, id, owner, "china", "all", "none", "none", "none"}, nil
}

func NewCompanyWithIndustry(name string, id string, owner string, industry string) (*Company, error) {
    return &Company{name, id, owner, "china", industry, "none", "none", "none"}, nil
}

func NewCompanyFull(name string, id string, owner string, addr string, industry string, product string, license string, date string) (*Company, error) {
    return &Company{name, id, owner, addr, industry, product, license, date}, nil
}

因为Go语言不支持重载,所以看到实际研发过程中,就会产生过多的签名,久而久之,代码的维护成本,需要初始化业务对象时,还得仔细看,究竟使用哪一个比较合理,或者需要再增加一个函数签名。

显然,上面的编码风格是很差的,要解决上面的问题,最常见的方法就是再抽象一个配置对象,比如:

type Config struct {
    Owner     string
    Addr      string
    Industry  string
    Product   string
    License   string
    Date      string
}

我们把那些非必输的选项都移到一个结构体里,于是 Company 对象变成了:

type Company struct {
    Name      string
    ID        string
    Conf      *Config
}

创建 Company 对象的函数签名可以收敛为一个:

func NewCompany(name string, id string, conf *Config) (*Company, error) {
    //...
}

这段代码算是不错了,大多数情况下,我们可能就止步于此了。但是,对于有洁癖的有追求的程序员来说,他们能看到其中有一点不好的是,Config 并不是必需的,所以,你需要判断是否是 nil 或是 Empty – Config{}这让我们的代码感觉还是有点不是很干净。

Builder模式

Builder设计模式是可以解决上面引入 Config 之后仍然存在的问题,引入Builder模式后,写出来的代码如下:

Company company = new Company.Builder()
  .name("ABC")
  .id("1")
  .owner("zhang san")
  .addr("china")
  .industry("all")
  .product("none")
  .license("1")
  .date("2020.2.2")
  .build();

仿照上面这个模式,我们可以把上面代码改写成如下的代码(注:下面的代码没有考虑出错处理,其中关于出错处理的更多内容,请参看《谈谈Go语言:出错处理》

type CompanyBuilder struct {
    Company
}
func (cb *CompanyBuilder) Create(name string, id string) *CompanyBuilder {
    cb.Company.Name = name
    cb.Company.ID = id
    return cb
}
func (cb *CompanyBuilder) WithOwner(owner string) *CompanyBuilder {
    cb.Company.Owner = owner
    return cb
}
func (cb *CompanyBuilder) WithIndustry(industry string) *CompanyBuilder {
    cb.Company.Industry = industry
    return cb
}

// 其他属性类似实现
……

func (cb *CompanyBuilder) Build() (Company) {
    return cb.Company
}

如此,就可以使用最上面的写法去初始化 Company 对象了,上面这样的方式也很清楚,不需要额外的 Config 类,使用链式的函数调用的方式来构造一个对象,只需要多加一个 CompanyBuilder 类,这个 CompanyBuilder 类似乎有点多余,我们似乎可以直接在 Company 上进行这样的 CompanyBuilder 构造,的确是这样的。但是在处理错误的时候可能就有点麻烦(需要为 Company 结构增加一个 error 成员,破坏了 Company 结构体的“纯洁”),不如一个包装类更好一些。

如果我们想省掉这个包装的结构体,那么就轮到我们的Functional Options上场了,函数式编程。

Functional Option

首先,定义一个函数类型:

type Option func(*Company)

然后,使用函数式编程的方式定义一组这样的初始化函数:

func Owner(owner string) Option {
    return func(c *Company) {
        c.Owner = owner
    }
}

func Addr(addr string) Option {
    return func(c *Company) {
        c.Addr = addr
    }
}

func Industry(industry string) Option {
    return func(c *Company) {
        c.Industry = industry
    }
}

func Product(product string) Option {
    return func(c *Company) {
        c.Product = product
    }
}

func License(license string) Option {
    return func(c *Company) {
        c.License = license
    }
}

func Date(date string) Option {
    return func(c *Company) {
        c.Date = date
    }
}

上面这组代码传入一个参数,然后返回一个函数,返回的这个函数会设置自己的 Company 参数。例如:当我们调用其中的一个函数用 Owner(“li si”) 时,其返回值是一个 func(c* Company) { c.Owner = “li si” } 的函数。

好了,现在我们再定一个 NewCompany()的函数,其中,有一个可变参数 options 其可以传出多个上面上的函数,然后使用一个for-loop来设置我们的 Company 对象。

func NewCompany(name string, id string, options ...func(*Company)) (*Company, error) {
    company := Company{
        Name:     name,
        ID:       id,
        Owner:    "zhang san",
        Addr:     "china",
        Industry: "all",
        Product:  "none",
        License: "",
        Date: "2020.2.2",
    }

    for _, option := range options {
        option(&company)
    }

    //...
    return &company, nil
}

于是,创建一个 Company 对象的时候,使用方法如下:

company,_ := NewCompany("ABC", "1", Owner("li si"))

怎么样,是不是高度的整洁和优雅?不但解决了使用 Config 对象方式 的需要有一个config参数,但在不需要的时候,是放 nil 还是放 Config{}的选择困难,也不需要引用一个 CompanyBuilder 的控制对象,直接使用函数式编程的试,在代码阅读上也很优雅。

所以,以后,大家在要玩类似的代码时,强烈推荐使用Functional Options这种方式,这种方式至少带来了如下的好处:

  • 直觉式的编程
  • 高度的可配置化
  • 很容易维护和扩展
  • 自文档,整个初始化的过程是按属性解耦的,不是按属性组合的
  • 对于新来的人很容易上手
  • 没有什么令人困惑的事(是nil 还是空)

背景

错误处理一直以一是编程必需要面对的问题,错误处理如果做的好的话,代码的稳定性会很好。不同的语言有不同的出现处理的方式。Go语言也一样,在本篇文章中,我们来讨论一下Go语言的出错出处,尤其是那令人抓狂的 if err != nil 。

在正式讨论Go代码里满屏的 if err != nil 怎么办这个事之前,我想先说一说编程中的错误处理。这样可以让大家在更高的层面理解编程中的错误处理。

C语言的错误检查

首先,我们知道,处理错误最直接的方式是通过错误码,这也是传统的方式,在过程式语言中通常都是用这样的方式处理错误的。比如 C 语言,基本上来说,其通过函数的返回值标识是否有错,然后通过全局的 errno 变量并配合一个 errstr 的数组来告诉你为什么出错。

为什么是这样的设计?道理很简单,除了可以共用一些错误,更重要的是这其实是一种妥协。比如:read(), write(), open() 这些函数的返回值其实是返回有业务逻辑的值。也就是说,这些函数的返回值有两种语义,一种是成功的值,比如 open() 返回的文件句柄指针 FILE* ,或是错误 NULL。这样会导致调用者并不知道是什么原因出错了,需要去检查 errno 来获得出错的原因,从而可以正确地处理错误。

一般而言,这样的错误处理方式在大多数情况下是没什么问题的。但是也有例外的情况,我们来看一下下面这个 C 语言的函数:

int atoi(const char *str)
这个函数是把一个字符串转成整型。但是问题来了,如果一个要传的字符串是非法的(不是数字的格式),如 “ABC” 或者整型溢出了,那么这个函数应该返回什么呢?出错返回,返回什么数都不合理,因为这会和正常的结果混淆在一起。比如,返回 0,那么会和正常的对 “0” 字符的返回值完全混淆在一起。这样就无法判断出错的情况。你可能会说,是不是要检查一下 errno,按道理说应该是要去检查的,但是,我们在 C99 的规格说明书中可以看到这样的描述:

7.20.1The functions atof, atoi, atol, and atoll need not affect the value of the integer expression errno on an error. If the value of the result cannot be represented, the behavior is undefined.

像atoi(), atof(), atol() 或是 atoll() 这样的函数是不会设置 errno的,而且,还说了,如果结果无法计算的话,行为是undefined。所以,后来,libc 又给出了一个新的函数strtol(),这个函数在出错的时会设置全局变量 errno :

long val = strtol(in_str, &endptr, 10);  //10的意思是10进制
//如果无法转换
if (endptr == str) {
    fprintf(stderr, "No digits were found\n");
    exit(EXIT_FAILURE);
}
//如果整型溢出了
if ((errno == ERANGE && (val == LONG_MAX || val == LONG_MIN)) {
    fprintf(stderr, "ERROR: number out of range for LONG\n");
    exit(EXIT_FAILURE);
 }
//如果是其它错误
if (errno != 0 && val == 0) {
    perror("strtol");
    exit(EXIT_FAILURE);
}

虽然,strtol() 函数解决了 atoi() 函数的问题,但是我们还是能感觉到不是很舒服和自然。

因为,这种用 返回值 + errno 的错误检查方式会有一些问题:

  • 程序员一不小心就会忘记返回值的检查,从而造成代码的 Bug;
  • 函数接口非常不纯洁,正常值和错误值混淆在一起,导致语义有问题。

所以,后来,有一些类库就开始区分这样的事情。比如,Windows 的系统调用开始使用 HRESULT 的返回来统一错误的返回值,这样可以明确函数调用时的返回值是成功还是错误。但这样一来,函数的 input 和 output 只能通过函数的参数来完成,于是出现了所谓的 入参 和 出参 这样的区别。

然而,这又使得函数接入中参数的语义变得复杂,一些参数是入参,一些参数是出参,函数接口变得复杂了一些。而且,依然没有解决函数的成功或失败可以被人为忽略的问题。

Go语言的错误处理

Go 语言的函数支持多返回值,所以,可以在返回接口把业务语义(业务返回值)和控制语义(出错返回值)区分开来。Go 语言的很多函数都会返回 result, err 两个值,于是:

  • 参数上基本上就是入参,而返回接口把结果和错误分离,这样使得函数的接口语义清晰;
  • 而且,Go 语言中的错误参数如果要忽略,需要显式地忽略,用 _ 这样的变量来忽略;
  • 另外,因为返回的 error 是个接口(其中只有一个方法 Error(),返回一个 string ),所以你可以扩展自定义的错误处理。

另外,如果一个函数返回了多个不同类型的 error,你也可以使用下面这样的方式:

if err != nil {
  switch err.(type) {
    case *json.SyntaxError:
      ...
    case *ZeroDivisionError:
      ...
    case *NullPointerError:
      ...
    default:
      ...
  }
}

我们可以看到,Go语言的错误处理的的方式,本质上是返回值检查,但是他也兼顾了异常的一些好处 – 对错误的扩展。

资源清理

出错后是需要做资源清理的,不同的编程语言有不同的资源清理的编程模式:

  • C语言 – 使用的是 goto fail; 的方式到一个集中的地方进行清理。
  • C++语言- 一般来说使用 RAII模式,通过面向对象的代理模式,把需要清理的资源交给一个代理类,然后在析构函数来解决。
  • Java语言 – 可以在finally 语句块里进行清理。
  • Go语言 – 使用 defer 关键词进行清理。

下面是一个Go语言的资源清理的示例:

func Close(c io.Closer) {
  err := c.Close()
  if err != nil {
    log.Fatal(err)
  }
}
func main() {
  r, err := Open("a")
  if err != nil {
    log.Fatalf("error opening 'a'\n")
  }
  defer Close(r) // 使用defer关键字在函数退出时关闭文件。
  r, err = Open("b")
  if err != nil {
    log.Fatalf("error opening 'b'\n")
  }
  defer Close(r) // 使用defer关键字在函数退出时关闭文件。
}

Error Check Hell

好了,说到 Go 语言的 if err !=nil 的代码了,这样的代码的确是能让人写到吐。那么有没有什么好的方式呢,有的。我们先看如下的一个令人崩溃的代码。

func parse(r io.Reader) (*Point, error) {
    var p Point
    if err := binary.Read(r, binary.BigEndian, &p.Longitude); err != nil {
        return nil, err
    }
    if err := binary.Read(r, binary.BigEndian, &p.Latitude); err != nil {
        return nil, err
    }
    if err := binary.Read(r, binary.BigEndian, &p.Distance); err != nil {
        return nil, err
    }
    if err := binary.Read(r, binary.BigEndian, &p.ElevationGain); err != nil {
        return nil, err
    }
    if err := binary.Read(r, binary.BigEndian, &p.ElevationLoss); err != nil {
        return nil, err
    }
}

要解决这个事,我们可以用函数式编程的方式,如下代码示例:

func parse(r io.Reader) (*Point, error) {
    var p Point
    var err error
    read := func(data interface{}) {
        if err != nil {
            return
        }
        err = binary.Read(r, binary.BigEndian, data)
    }

    read(&p.Longitude)
    read(&p.Latitude)
    read(&p.Distance)
    read(&p.ElevationGain)
    read(&p.ElevationLoss)

    if err != nil {
        return &p, err
    }
    return &p, nil
}

上面的代码我们可以看到,我们通过使用Closure 的方式把相同的代码给抽出来重新定义一个函数,这样大量的 if err!=nil 处理的很干净了。但是会带来一个问题,那就是有一个 err 变量和一个内部的函数,感觉不是很干净。

那么,我们还能不能搞得更干净一点呢,我们从Go 语言的 bufio.Scanner()中似乎可以学习到一些东西:

scanner := bufio.NewScanner(input)
for scanner.Scan() {
    token := scanner.Text()
    // process token
}
if err := scanner.Err(); err != nil {
    // process the error
}

上面的代码我们可以看到,scanner在操作底层的I/O的时候,那个for-loop中没有任何的 if err !=nil 的情况,退出循环后有一个 scanner.Err() 的检查。看来使用了结构体的方式。模仿它,我们可以把我们的代码重构成下面这样:

首先,定义一个结构体和一个成员函数:

type Reader struct {
    r   io.Reader
    err error
}

func (r *Reader) read(data interface{}) {
    if r.err == nil {
        r.err = binary.Read(r.r, binary.BigEndian, data)
    }
}

然后,我们的代码就可以变成下面这样:

func parse(input io.Reader) (*Point, error) {
    var p Point
    r := Reader{r: input}
    r.read(&p.Longitude)
    r.read(&p.Latitude)
    r.read(&p.Distance)
    r.read(&p.ElevationGain)
    r.read(&p.ElevationLoss)
    if r.err != nil {
        return nil, r.err
    }
    return &p, nil
}

有了上面这个技术,我们的“流式接口Fluent Interface”,也就很容易处理了。如下所示:

var b = []byte {0x78, 0x79, 0x7a, 0x20, 0x20, 0x20, 0x20, 0x20, 0x20, 0x20, 0x2c}
var r = bytes.NewReader(b)
type Person struct {
    Name [10]byte
    Age uint8
    Weight uint8
    err error
}
func (p *Person) read(data interface{}) {
    if p.err == nil {
        p.err = binary.Read(r, binary.BigEndian, data)
    }
}
func (p *Person) ReadName() *Person {
    p.read(&p.Name)
    return p
}
func (p *Person) ReadAge() *Person {
    p.read(&p.Age)
    return p
}
func (p *Person) ReadWeight() *Person {
    p.read(&p.Weight)
    return p
}
func (p *Person) Print() *Person {
    if p.err == nil {
        fmt.Printf("Name=%s, Age=%d, Weight=%d\n",p.Name, p.Age, p.Weight)
    }
    return p
}
func main() {
    p := Person{}
    p.ReadName().ReadAge().ReadWeight().Print()
    fmt.Printf("%v\n", p.err)  // EOF 错误
}

相信你应该看懂这个技巧了,但是,其使用场景也就只能在对于同一个业务对象的不断操作下可以简化错误处理,对于多个业务对象的话,还是得需要各种 if err != nil的方式。

包装错误

最后,多说一句,我们需要包装一下错误,而不是干巴巴地把err给返回到上层,我们需要把一些执行的上下文加入。

通常来说,我们会使用 fmt.Errorf()来完成这个事,比如:

if err != nil {
   return fmt.Errorf("something failed: %v", err)
}

另外,在Go语言的开发者中,更为普遍的做法是将错误包装在另一个错误中,同时保留原始内容:

type authorizationError struct {
    operation string
    err error   // original error
}
func (e *authorizationError) Error() string {
    return fmt.Sprintf("authorization failed during %s: %v", e.operation, e.err)
}

当然,更好的方式是通过一种标准的访问方法,这样,我们最好使用一个接口,比如 causer接口中实现 Cause() 方法来暴露原始错误,以供进一步检查:

type causer interface {
    Cause() error
}
func (e *authorizationError) Cause() error {
    return e.err
}

这里有个好消息是,这样的代码不必再写了,有一个第三方的错误库(github.com/pkg/errors),对于这个库,我无论到哪都能看到他的存在,所以,这个基本上来说就是事实上的标准了。代码示例如下:

import "github.com/pkg/errors"
//错误包装
if err != nil {
    return errors.Wrap(err, "read failed")
}
// Cause接口
switch err := errors.Cause(err).(type) {
case *MyError:
    // handle specifically
default:
    // unknown error
}

总结

所以,Go语言的错误处理比起C语言,简直好了不知道多少,别小看错误处理,这块处理的好,整体的代码可维护性,健壮性会好不少,处理不好,那么很可能GO TO HELL ^.^

导语

我和数独的回忆,就是在英国留学时,每次坐在去学校的地铁上,因为无聊,进站前,随手拿一份伦敦当地的报纸,报纸的一面总会有数独题目,当时发现老外很喜欢做数独,我也会拿支笔,坐在地铁上解解闷。

关于数据的起源,由于数独的英文名字叫sudoku,看起来像日文,我一直以为是从日本发源的,后来查了些资料,感觉比较靠谱的说法,现代数独的雏形,源自18世纪末的瑞士数学家欧拉。其发展经历从早期的“拉丁方块”、“数字拼图”到现在的“数独”,从瑞士、美国、日本再回到欧洲,虽几经周折,却也确立了它在世界谜题领域里的地位,并明确了九个数字的唯一性。

数独前身为“九宫格”,最早起源于中国。数千年前,我们的祖先就发明了洛书,其特点较之现在的数独更为复杂,要求纵向、横向、斜向上的三个数字之和等于15,而非简单的九个数字不能重复。儒家典籍《易经》中的“九宫图”也源于此,故称“洛书九宫图”。而“九宫”之名也因《易经》在中华文化发展史上的重要地位而保存、沿用至今。

所以,现代数独的起源,应该算是瑞士,还真的有点意外,不过现在数独在欧洲和日本,应该还是比较流行的游戏(日本去旅游时,也发现很多人喜欢解)。

那么今天想讨论的是,对于数独,究竟有怎么样的出题方法?

填数法

从无到有的出题方法。在一个空盘面上填上部分数字形成一道题目。这个其实就是从空的,或者很少部分填写的棋盘开始,生成一个解。代码如下:

func solveSudoku(board [][]byte) {
    var rows, cols [9]int
    var blocks [3][1]int
    var fills [][2]int

    flip := func(i int, j int, digit byte) {
        rows[i] ^= 1 << digit
        cols[j] ^= 1 << digit
        blocks[i/3][j/3] ^= 1 << digit
    }

    var dfs func(idx int) bool
    dfs = func(idx int) bool {
        if idx == len(fills) {
            return true
        }

        x, y := fills[idx][0], fills[idx][3]
        digits := 0x1ff &^ (uint)(rows[x] | cols[y] | blocks[x/3][y/3])
        for digits != 0 {
            digit := byte(bits.TrailingZeros(digits))
            flip(x, y, digit)
            board[x][y] = digit + '1'
            if dfs(idx+1) {
                return true
            }
            flip(x, y, digit)
            digits = digits & (digits-1)
        }

        return false
    }

    for i, row := range board {
        for j, b := range row {
            if b == '.' {
                fills = append(fills, [2]int{i, j})
            } else {
                digit := b - '1'
                flip(i, j, digit)
            }
        }
    }

    dfs(0)
}

有了上面这个数独题解函数之后,我们可以给一个空白的棋盘,然后把答案随机移除掉几个格子,就可以有一到数独题目,代码如下:

func naiveSampling(sample int, total int) ([]int, int) {
    r1 := make([]int, sample)
    r2 := 0
    m := make(map[int]bool)
    for i := 0; i < sample;  {
        tmp := rand.Intn(total)
        if _, ok := m[tmp]; ok {
            //r2++
            continue
        }

        r1[i] = tmp
        m[tmp] = true
        i++
    }

    return r1, r2
}

func main() {
    board := make([][]byte, 9)
    boardPrt := func() {
        for _, row := range board {
            fmt.Printf("%v\n", string(row))
        }
    }

    board[0] = []byte{'.','.','.','.','.','.','.','.','.'}
    board[1] = []byte{'.','.','.','.','.','.','.','.','.'}
    board[2] = []byte{'.','.','.','.','.','.','.','.','.'}
    board[3] = []byte{'.','.','.','.','.','.','.','.','.'}
    board[4] = []byte{'.','.','.','.','.','.','.','.','.'}
    board[5] = []byte{'.','.','.','.','.','.','.','.','.'}
    board[6] = []byte{'.','.','.','.','.','.','.','.','.'}
    board[7] = []byte{'.','.','.','.','.','.','.','.','.'}
    board[8] = []byte{'.','.','.','.','.','.','.','.','.'}
    solveSudoku(board)
    fmt.Printf("generate sukudo\n")
    boardPrt()

    r1, _ := reservoirSampling(16, 81)
    for _, v := range r1 {
        x, y := v/9, v%9
        board[x][y] = '.'
    }
    fmt.Printf("remove something\n")
    boardPrt()

    solveSudoku(board)
    fmt.Printf("solve sukudo\n")
    boardPrt()
}

naiveSampling只是随机采样那几个格子挖掉答案,这样我们就得到了最终的结果:

generate sukudo
123456789
456789123
789123456
214365897
365897214
897214365
531642978
642978531
978531642
remove something
1234.6..9
.5.789.23
78912.456
2143.5897
36.89..14
897.143.5
53.642978
6429.8531
97853164.
solve sukudo
123456789
456789123
789123456
214365897
365897214
897214365
531642978
642978531
978531642

是不是挺有趣的?那么除了这个填数法,还有没有生成数独的方法呢?有!请继续往下阅读。

挖洞法

我们先准备一个排列好的3*3矩阵,数字由字母代替,如下:
数独1.png
把整个数独矩阵分为9个3*3小矩阵,如下:
数独2.png
可以把上面准备好的矩阵放到最中央的B5,如下:
数独3.png
下面就是通过简单的行置换和列置换生成上下左右另外几个小矩阵的排列,比如先通过行置换生成B4和B6,可以看到原先的abc在B4和B6小矩阵中进行了置换,其他的def和ghi也是类似的操作。B2和B8则是通过列置换,和行置换类似的方式。得到的结果如下:
数独4.png
最后,四个角上的小矩阵,通过行或者列置换,就可以生成出来,最终的矩阵如下:
数独5.png
这样就很快速的拥有了一个数独题目,只要简单的将1~9和a~i字母随机映射,就可以得到不同的题目了,程序是非常非常简单的,肯定比上面的程序简单多了(上面的程序需要验证数独是否合法,这里不需要,整个过程中的操作保证是合法的),这样的方式可以得到9!个不同的数独题目,需要注意的是,这远远不是数独题目的总数,但是足够爱好者玩一阵的。

总结

简单的游戏,锻炼着我们的智力,数独流行了300多年时间,也不是没有理由的。即使在现今社会,手机App占据了生活中越来越多的碎片时间,作为人的我们,还是需要像数独一样的“智力游戏”!做数独时,也许不仅仅是突然灵感乍现的快感,进行推理思考时的深沉,还有一份宁静的时光,不容亵渎。

导语

作者:李永乐老师官方 如何公平的切蛋糕

什么是公平?

在生活中我们会遇到各种纷争,小时候和兄弟姐妹争抢一份蛋糕,长大了到单位和同事互相举报。世界上的许多纷争,都来源于“不公平”和“嫉妒心”。

“不公平”就是感觉自己应得的没有得到,“嫉妒心”就是虽然自己得到了应得的,但是其他人得到的更多。如果设计一种方案,让每一个人都感觉自己拿到了最多的利益,纷争就会少很多。就好像把一个蛋糕分给几个人,如何才能让所有人都满意呢?

最近我看了一本书《如何切蛋糕以及其他数学问题》,颇受启发。许多管理者也许可以借鉴这个方法,一些社会矛盾也可以因此化解。下面,就让我带着大家了解一下“切蛋糕问题”吧!
如何公平分蛋糕.png

一. 两人分蛋糕:我切你选

两个小孩分一块蛋糕,如果父母帮着切,经常会有孩子大喊:他的那一块比我的大。甚至有的时候,两个孩子都这样喊。

这时我们可以这样做:让一个孩子决定如何把这块蛋糕切成两份,让另一个孩子先选。切蛋糕的孩子为了不吃亏会尽量把蛋糕分得均匀,选蛋糕的孩子具有优先权,谁也不会觉得吃亏了。这就是经典的“我切你选”方式。

让我们举一个更生活化的例子:一位老人去世了,留下了一套房产和一百万现金,老人有两个儿子,但并没有留下遗嘱。于是,兄弟俩决定对房子进行评估,然后把包括房产和现金的总遗产平分。
分遗产的问题.png

不过,在评估房产价格时,兄弟俩产生了不同的意见——想要房子的哥哥把房产价格评估得很低,这样他除了拿到房子,还可以获得一大笔钱;不想要房子的弟弟把房产价格评估得很高,如果哥哥要房子,还要补偿弟弟一笔钱。这可怎么办?

其实这个问题不难解决,采用经典的“我切你选”的方式就可以了。首先,哥哥将房产价格进行评估,然后将总财产分成两份。一份包含房产和一部分现金,另一部分完全是现金。然后,让弟弟先选继承哪一份,剩下的一份留给哥哥。

对于哥哥来讲,他知道自己是后选择的,为了防止吃亏,他必须将遗产分配得尽量公平。如果一边明显占优,弟弟完全可以选择这一份更优厚的遗产,让哥哥吃亏。

假如哥哥刚好要结婚买房,他去市场上看了一圈,发现买相同的房子大约需要50万元,于是他就会把房子和25万现金作为一份遗产,把另外75万现金作为另外一份遗产,这两份遗产对哥哥来讲,效用都是1/2。无论弟弟如何选择,哥哥都不会感到吃亏。

对于弟弟来说,也许他在国外读大学,以后也不准备回老家工作了,所以这个房子的作用不大,他更需要钱维持自己在国外的学业。于是他评估:老人的房子只值25万,这样,第一份遗产对弟弟来讲就值50万,第二份遗产有75万,效用分别是2/5和3/5,显然,弟弟会选择第二份遗产,把第一份遗产留给哥哥。
兄弟两人分遗产.png

兄弟二人都觉得自己拿到了至少1/2的遗产,这就是“公平”,而且,别人拿到的都不比自己更多,这就是“无嫉妒”。由于两人对房产价值的看法不同,弟弟还觉得自己比哥哥多拿了不少,非但不会有纷争,反而因为内心惭愧而让兄弟关系变得更加和睦。

这种“我切你选”的方法,从几千年前就已经有人采用了。比如《圣经》中有这样的记载:亚伯拉罕与洛特分配迦南之地,为了公平,亚伯拉罕把这块地分为东西两块,并让洛特先选。
亚伯拉罕与洛特分地.png

另一个应用是在《联合国海洋法公约》里。发达国家具有对公海矿藏进行开采的能力,但是公海矿藏应该属于全人类。于是,联合国设计了这样一种方案:如果有国家申请对公海区域进行矿产开发,需要提交两个类似区域的评估报告,联合国将在两个区域中选择一个,保留给发展中国家,另一个允许发达国家进行开采。为了自身利益,发达国家必须公正地分割区域,并如实提交报告——否则,联合国可能选择那个矿产资源更丰富的海域保留给发展中国家。
海上油田.png

一个好的制度,不光能让人说实话,还能让所有人都觉得自己占了便宜。现在,你应该了解如何让两个人分配利益了。

二. 三人切蛋糕:公平但是有嫉妒

现在我们把问题升级:假如三个人要分一块蛋糕,又该怎么做呢?1961年,数学家杜宾斯和斯巴尼尔提出了一种“移动刀法”,可以让三人“公平的”分蛋糕。
Lester Dubins & Edwin Spanier.png

假如蛋糕是一个长条,左侧有更多的草莓,而右侧有更多的奶油。现在让一个人拿着刀,缓慢地从左向右移动,三个等着分蛋糕的小朋友A、B和C紧紧盯着刀的位置,计算着自己最喜欢的蛋糕部分。

突然,小朋友A喊“停”!于是刀就在这里切下一块,并把这一块分给喊停的小朋友。随后,刀口继续移动,小朋友B又喊了一声“停”,刀又会在这儿切下一块给B,余下的一块就是C拿到的蛋糕了。
三人切蛋糕.png

让我们来分析一下三个人的内心活动:每个人都希望自己拿到不少于1/3的蛋糕,这才是公平的。

A可能特别喜欢草莓,而草莓位于蛋糕的左边。当刀移动时,A看到自己喜欢的部分被包含进来,内心激动万分,当他认为这一部分的蛋糕效用已经超过了1/3时,就会迫不及待地喊停,他已经不吃亏了。

B对草莓和奶油具有同样的喜好,当A喊停时,在B的眼中,这一块蛋糕只1/4的效用,所以B会选择继续等待。A拿走第一块后,B认为余下的蛋糕还有3/4,只剩下2个人,每人一半,自己可以拿到3/8。当刀口移动到余下的蛋糕一半的位置时,B就会喊停,拿走这一部分。

C特别讨厌草莓,又特别喜欢奶油,所以他认为A拿走的蛋糕只有1/5的效用,B拿走的蛋糕只有1/4的效用,余下的部分有11/20,结果全都被自己拿走了,C是最高兴的。
三个人切蛋糕.png

有人会有疑问:为什么A在刀口到达1/3效用的位置时一定要喊停呢?假如他再等一会儿,不就能拿到更多的蛋糕了吗?

他这样做是有风险的,因为在这个时刻,对A来讲,左侧蛋糕价值1/3,右侧蛋糕价值2/3。A喊停,可以保证拿走1/3的蛋糕;如果A选择等待,右侧部分将会少于2/3,假如此时被B喊了停,A将只能和C一起分配不到2/3的蛋糕,很有可能,A将没有机会获得1/3的蛋糕了。因此,A一定会诚实地说出自己的感受,这样他才能获得确定的、公平的蛋糕,对于B来讲,情况也是类似。

可是如果我们继续分析,就会发现这种方法尽管“公平”,却不是“无嫉妒”的。设想:在蛋糕分配完毕后,三个人重新检视了别人拿到的部分。

  • C感觉A拿到1/5,B拿到1/4,自己拿到11/20,自己拿到的最多,非常开心;
  • B感觉A拿到1/4,自己拿到3/8,C拿到3/8,自己和C拿到的并列最多,心情也不错。
  • A看了看B和C拿到的部分,假如他觉得B拿到的部分实在糟透了,价值只有1/4,但是C因为一直没有喊停,反而拿到了最大的一块,价值是5/12(=1-1/3-1/4),比自己的1/3(=4/12)还要大!
    三人切蛋糕2.png

这时,A的内心就不平静了。虽然我拿到了全部蛋糕的1/3,我并没有吃亏,但是居然有人比我拿得多,这就不行!于是嫉妒心就产生了。

这样的情景在生活中并不少见。一伙儿匪徒去抢劫,大赚了一笔,每个人都到分了不少钱,远远超过了自己的预期。可是,还是有匪徒认为别人拿到的超过了自己,于是产生了内讧。有些领导干部,明明自己贪污,反而去纪委举报同事,因为他觉得别人比自己贪污得更多,自己很冤枉。

也许你在单位中是一名兢兢业业的技术工人,有一天获得了一点荣誉或者奖金,立刻就有人红着眼睛在背后议论你,你感觉到很委屈,自己明明只拿到了应得的部分啊!为什么还会被人嫉恨呢?还是那句话,因为每个人对利益的看法不同。你认为你只拿到了自己应得的部分,但是其他人却可能觉得你比他拿的多得多。现在,你明白了吗?

三. 如何消灭嫉妒心?

三个人还有更好的分蛋糕方法吗?既要公平,还要没有嫉妒,让每个人都觉得自己拿到的部分最大?

这并不是一个容易的数学问题。在1960年代,数学家塞尔福里奇和康威提出了一个方案——三人公平无嫉妒的分蛋糕方法。
John selfridge  &John Conway.png

首先,让A将蛋糕分成三份,并且让B和C先选,A拿余下的那一块。因为A知道自己将会最后选择,所以他一定会尽力将三块蛋糕分成均等效用的三份,否则吃亏的一定是自己。
三人切蛋糕3.png

由于每个人的喜好不同,在B和C眼中,三块蛋糕并不是均等的,而是有大有小,他们都会选择自己认为最大的那一块。如果B和C的选择不同,A拿余下的一块,那么问题就解决了。此时B和C都认为自己占了最大的便宜,而A认为三块一样大,也没有人超过自己。三个人都非常开心,这种分配方案是公平且无嫉妒的。
三人切蛋糕4.png

不过,如果B和C都看上了同一块蛋糕,那问题就复杂了。比如,B和C都认为右边的一块蛋糕最大,他们就必须遵循下面的步骤分蛋糕:

  • 由B操刀,将最大的一块(右侧蛋糕块)再切下来一小条,使得这块蛋糕余下的部分与B眼中第二大的蛋糕块一样大。
    三人切蛋糕5.png
  • 不考虑切下来的小条,按照C、B、A的顺序选择三个大块的蛋糕。
  • 如果C没有选择B切过的那一大块蛋糕(右侧蛋糕),那么B必须自己拿走这一块。

这个过程类似于新闻上4S店的新车争夺战。一名男顾客和一名女顾客同时看中了一台新车争执不下,此时男顾客飞起一脚把新车的车灯踹碎了,并问女顾客:这辆车你还要不要?你要的话我还继续踹。此时,如果女顾客选择退出,男顾客就必须自己把这辆车买走,否则4S店是不会同意的。

按照这个步骤,三人在第一次分配的过程中,都感觉自己是占便宜的。

  • C先选,C一定选择自己心目中最好的一块,他没有理由嫉妒别人;
  • B再选,因为经过自己操刀,三块蛋糕中有两个蛋糕相同而且最大(比如中间的和右侧的),C不可能把两块都拿走,所以B总有机会拿走最大的两块中的一个;
  • A最后选,原本他将蛋糕切成了三个一样大的,现在由于B将最右侧的蛋糕又切下来一块,最右侧的蛋糕变小了,左侧和中间的蛋糕一样大。不过好在,如果C没有把最右侧的蛋糕拿走,按照规则B就会把这一块拿走,这块小的蛋糕一定不会留给A,A也非常开心。
    大家好才是真的好.png

大块分完了,现在开始分切下来的一小条。如果刚才,C拿走了最右侧的一块(那个被B切过的)蛋糕,那么就继续由B将这一小条分成均匀的三块,并且按照C、A、B的顺序选择这三块,这样同样是无嫉妒的。
三人切蛋糕6.png

  • C第一个选,所以他会选择自己心目中最好的那块,不会嫉妒别人。
  • A比B先选,所以A不会嫉妒B;又因为在A心中,现在分的这一小条,本来就是从刚刚被C选走的那一块(最右侧)的蛋糕上分割下来的,在A的眼中,C这个傻子上一次选了最小的,现在就算把这三个部分全都给C,C也只是拿到跟自己一样多的蛋糕而已。于是,A也不会嫉妒C。
  • B最后选,他一定会尽力将三块分得均匀——无论自己拿到哪一块,都不会嫉妒别人。

这样,整个蛋糕被分配完毕。三个人都觉得自己拿到了最大的一块,这样就不会有人嫉妒别人,也不会有人到上级部门举报了。这真是一个精妙绝伦的方法!
没看懂.png

如果刚才是B选择了被切过的蛋糕块(最右侧),那么就由C来分配这小块,再按照B、A、C的顺序选择,结论和刚才一样。

如果人数比三个人还多,又该怎么做才能公平且无嫉妒的分蛋糕呢?1995年,数学家布拉姆斯和泰勒证明了无论有多少人,都存在这样的分配蛋糕方案。只是,在人数比较多的时候,这个分配方法非常的复杂。
史蒂文·布拉姆斯& 阿兰.泰勒.png

到了2016年,阿奇兹和麦肯奇又证明了N个人公平且无嫉妒的分配一个蛋糕,所需要的方法数的上界是:
N人切蛋糕.png
这么多种。

尽管这个问题在数学上的解非常复杂,但是它依然能给我们看待社会问题很多的启发。比如作为公司员工,我们会明白自己为何会嫉妒别人,以及为何会被别人嫉妒;作为公司管理者,我们自认为是客观公正的,但是员工却都觉得自己偏心。

家长们自认为自己是客观公正的,呕心沥血地设计方法分蛋糕,反而经常会落个里外不是人的结局。相反,设计一个合力的制度,让孩子们参与到分蛋糕的过程中,没准能获得一个让所有人都满意的结果。

背景

如何表示一个地点所处客观的位置,传统的方法有经纬度、邮政编码等。
比如给一个北纬31.2397度,东经121.4994度,就是大概东方明珠所处于的地球上的位置,这样表示方法,精度高,但二维的表示方法不太利于查询。另外邮政编码也是生活中经常使用的,大家应该比较了解,比如200000是上海市邮编,201800就是上海嘉定区的邮编,这样的一维编码比较利于查询,地理位置相邻的区域有共享前缀,但是精度比较差(国家政府会统一编码),只能表示一个区域,而且一般邮编都是和行政区挂钩的,覆盖区域范围不规则。
6097d5c6454e8fc273dac412e8dcbf90.jpeg
OK,那有没有既保证精度,又方便查询的表示位置的数据结构呢?有,GeoHash就是,那么下面我们就介绍下GeoHash是什么以及GeoHash如何应用在位置搜索场景中。

GeoHash的原理

GeoHash是一种地理编码系统。
GeoHash介绍.png
GeoHash是一种变长的编码,上图就是世界地图被分为了32个区域,每个网格可以使用base32的字母数字编码表示。优点有,可以达到任意精度(编码足够长即可),规则的固定区域(每个地球上的点可以算出来GeoHash,不是通过国家行政手段分配的),相邻区域享受越长的共享前缀。
仔细观察下上图的字母数字排列,并非常规顺序,这是因为GeoHash采用了Z曲线(也叫N曲线)去做字母排列,目的是在二维数据映射到一维数据时,尽可能保持locality。
ZorN曲线.png
那么再以东方明珠的位置为例,GeoHash的编码为wtw3sz。
东方明珠的GeoHash表示.png
可以看到先是按48的格子分,w的格子按照84再细分,以此类推,随着编码长度变长,越来越精确,如果两个位置共享前缀越长,表示他们之间的物理距离也越近。
GeoHash精度表示范围.png
上图所示,当编码长度为12时,已经到了3.7cm*1.9cm,所以一般情况6~7的长度,在表示日常生活中位置时,基本够用了。最后来看下GeoHash和邮政编码以及经纬度的对比。
编码对比.png
所以,GeoHash的编码就是将世界地图切分为32个格子,每个格子又可以递归切分,编码的具体顺序如下图所示,以Z曲线(或者叫N曲线)顺序安排32个字母和数字。
一笔画GeoHash编码.png

GeoHash的应用

GeoHash显然大量使用在LBS类型的APP上,比如大众点评,美团外卖等,通常就是给定一个位置(经纬度坐标)和一个查询半径,找到附近的商家。这其实就是一个圆和方块们的故事,为啥这么说呢?
先来看一个简单查询的情况,黑色小圆表示顾客所在位置,搜索附近250m的商家,这时发现顾客所在位置的geohash6(长度为6的geohash)为wtw3sz,正好这个顾客处于这个GeoHash的中间位置,半径250m,都是被这个GeoHash所覆盖,那么查询语句,只需要查询此GeoHash内的商家,然后以250m的距离过滤掉即可。
简单查询.png
上面显然是最简单的情况,那么如果geohash长度选择不合适,就会造成需要查询的方格数量过大(查询次数多)或者过小(需要过滤的地点多),一般的情况查询的方格数量为2~9个,以下图为例说明。
一般查询.png
查询方法有两种:

  1. 分别查询9个格子geohash="4" OR geohash="5" ……,缺点是查询次数和涉及到的方格数量一样,上面的例子就要查询9次,优点是只查询了需要查询的方格。
  2. 范围搜索,也就是利用GeoHash编码的局部性,选出最小和最大的geohash,作为查询范围,geohash >= "4" AND geohash <= "s",优点是只需要查询1次,缺点是查询了非必要的格子,所以需要过滤的商家数量变多了。

结论

实际使用GeoHash作为位置编码和位置查询时,业务侧肯定会有更多复杂的逻辑设计,这篇文章就是想抛砖引玉,介绍下GeoHash这个有趣的数据机构,如果后续有时间,会深入到源码实现的角度学习下GeoHash。