如何给磁盘文件排序?

近来,翻出来之前买的《编程珠玑》,买来还没有仔细阅读,随手翻开看看,经典书籍果然是经典书籍,读起来,还是那么深刻。我准备将自己对书上内容的理解记录下来,一是通过整理巩固知识,二是写成文字,可作为输出内容。

上来讲的是“如何给磁盘文件排序”的问题,问题的准确描述如下:
输入:一个最多包含n个正整数的文件,每个数都小于n,其中n=10^7。如果在输入文件中有任何整数重复出现就是致命错误。没有其他数据与该整数相关联。
输出:按升序排列输入整数的列表。
约束:最多有(大约)1MB的内存空间可以使用,有充足的磁盘存储空间可用。运行时间最多为几分钟(感觉到之前时代算力的紧张了),运行时间为10秒就不需要优化了。(现在可以改为运行时间低于100ms就不需要优化了)。

思考过程:
方法一、归并排序读入输入文件一次,然后在中间文件的协作下,完成多路归并排序,并写入输出文件一次。中间文件需要多次读写。

企业微信20220126-114447@2x.png

方法二、40趟算法读入输入文件,前提是要知道整数分布的范围,那么就可以按号段去扫描读入,比如问题中描述的1MB空间,如果用来存0~100万数字表述的号码,那么一个号码可以使用一个32位整型数表示,1MB空间可以存大约250000个号码,100万的号码可以先扫描到内存中0~249999之间的整数,内存做快速排序,结果存到输出文件,以此类推。

企业微信20220126-114503@2x.png

下图所示的方案更可取。我们结合上述两种方法的优点,读输入文件仅一次,且不使用任何中间文件。但前提是1MB内存需要来表示所有的整数。该怎么做呢?

企业微信20220126-114515@2x.png

解决方案:
现在想来,直接的方案就是使用bitmap,举例,可以使用一个20位长的字符串表示一个所有元素都小于20的简单的非负整数集合。例如,可以使用如下字符串(二进制的表示)来表示集合{1,2,3,5,8,13}:
0 1 1 1 0 1 0 0 1 0 0 0 0 1 0 0 0 0 0 0
那么1MB内存有3000万bit,每个bit表示1个整形数,可以表示的整数个数可以达到3000+万。这种表示利用了该问题的三个在排序问题中不常见的属性:输入数据限制在相对较小的范围内;数据没有重复;而且对每条记录而言,除了单一整数外,没有任何其他关联数据。

实现代码:

#include <time.h>
#include <vector>
#include <algorithm>
#include <string>
#include <fstream>

using namespace std;

#define BITSPERWORD 32
#define SHIFT 5
#define MASK 0x1F
#define N 10000000

int a[1+N/BITSPERWORD];

void set(int i) { a[i>>SHIFT] |= (1<<(i & MASK)); }
void clr(int i) { a[i>>SHIFT] &= ~(1<<(i & MASK)); }
int test(int i) { return a[i>>SHIFT] & (1<<(i & MASK)); }

unsigned long GetTickCount()
{
    struct timespec ts;
    clock_gettime(CLOCK_MONOTONIC, &ts);
    return (ts.tv_sec * 1000 + ts.tv_nsec / 1000000);
}

void stl_sort() {
    vector<int> v;
    ifstream ifile;
    ifile.open("./input.txt");
    string line;
    unsigned long begin_time = GetTickCount();
    while(getline(ifile, line)) {
        v.push_back(atoi(line.c_str()));
    }
    unsigned long end_time = GetTickCount();
    printf("finish input, cost time=%d\n", end_time-begin_time);
    ifile.close();

    begin_time = GetTickCount();
    sort(v.begin(), v.end());
    end_time = GetTickCount();
    printf("finish sorting, cost time=%d\n", end_time-begin_time);

    ofstream ofile;
    ofile.open("./output1.txt");
    begin_time = GetTickCount();
    for (int i = 0; i < v.size(); ++i) {
        ofile << v[i] << endl;
    }
    end_time = GetTickCount();
    printf("finish writing, cost time=%d\n", end_time-begin_time);
    ofile.close();
}

void bitmap_sort() {
    vector<int> v;
    ifstream ifile;
    ifile.open("./input.txt");
    string line;
    unsigned long begin_time = GetTickCount();
    while(getline(ifile, line)) {
        v.push_back(atoi(line.c_str()));
    }
    unsigned long end_time = GetTickCount();
    printf("finish input, cost time=%d\n", end_time-begin_time);
    ifile.close();

    begin_time = GetTickCount();
    for (int i = 0; i <= N; ++i) {
        clr(i);
    }
    for (int i = 0; i < v.size(); ++i) {
        //printf("set: i=%d, v[i]=%d\n", i, v[i]);
        set(v[i]);
    }
    end_time = GetTickCount();
    printf("finish sorting, cost time=%d\n", end_time-begin_time);

    ofstream ofile;
    ofile.open("./output2.txt");
    begin_time = GetTickCount();
    for (int i = 0; i <= N; ++i) {
        if (test(i)) {
            ofile << i << endl;
        }
    }
    end_time = GetTickCount();
    printf("finish writing, cost time=%d\n", end_time-begin_time);
    ofile.close();
}

上面代码实现了从文件读入数据,排序(STL实现的排序和bitmap方式),实测在1000万量级上的耗时如下:

finish input, cost time=795
finish sorting, cost time=3873 // 3873ms
finish writing, cost time=13634
finish input, cost time=793
finish sorting, cost time=151 // 151ms
finish writing, cost time=8777

排序的加速效果是非常明显的,同样数据规模,比STL实现的排序算法加速了20x。

另外,这个bitmap表示一个整数集合的思想,也不仅仅用在排序场景中,有些去重的场景也适用(或者检查有无重复项),比如今天遇到的leetcode上一道题目,题目不难,但是如果使用bitmap实现,代码挺整洁的。
检查是否每一行每一列都包含全部整数

导语

函数式编程的中非常重要的Map、Reduce、Filter的三种操作,这三种操作可以让我们非常方便灵活地进行一些数据处理——我们的程序中大多数情况下都是在到倒腾数据,尤其对于一些需要统计的业务场景,Map/Reduce/Filter是非常通用的玩法。

例子

Map示例
下面的程序代码中,我们写了两个Map函数,这两个函数需要两个参数:

  • 一个是字符串数组 []string,说明需要处理的数据一个字符串
  • 另一个是一个函数func(s string) string 或 func(s string) int
func MapStrToStr(arr []string, fn func(s string) string) []string {
    var newArray = []string{}
    for _, it := range arr {
        newArray = append(newArray, fn(it))
    }
    return newArray
}

func MapStrToInt(arr []string, fn func(s string) int) []int {
    var newArray = []int{}
    for _, it := range arr {
        newArray = append(newArray, fn(it))
    }
    return newArray
}

整个Map函数运行逻辑都很相似,函数体都是在遍历第一个参数的数组,然后,调用第二个参数的函数,然后把其值组合成另一个数组返回。
于是我们就可以这样使用这两个函数:

var list = []string{"Hao", "Chen", "MegaEase"}

x := MapStrToStr(list, func(s string) string {
    return strings.ToUpper(s)
})
fmt.Printf("%v\n", x)
//["HAO", "CHEN", "MEGAEASE"]

y := MapStrToInt(list, func(s string) int {
    return len(s)
})
fmt.Printf("%v\n", y)
//[3, 4, 8]

我们可以看到,我们给第一个 MapStrToStr() 传了函数做的是 转大写,于是出来的数组就成了全大写的,给MapStrToInt() 传的是算其长度,所以出来的数组是每个字符串的长度。
我们再来看一下Reduce和Filter的函数是什么样的。

Reduce示例

func Filter(arr []int, fn func(n int) bool) []int {
    var newArray = []int{}
    for _, it := range arr {
        if fn(it) {
            newArray = append(newArray, it)
        }
    }
    return newArray
}

var intset = []int{1, 2, 3, 4, 5, 6, 7, 8, 9, 10}
out := Filter(intset, func(n int) bool {
   return n%2 == 1
})
fmt.Printf("%v\n", out)

out = Filter(intset, func(n int) bool {
    return n > 5
})
fmt.Printf("%v\n", out)

Filter示例

func Filter(arr []int, fn func(n int) bool) []int {
    var newArray = []int{}
    for _, it := range arr {
        if fn(it) {
            newArray = append(newArray, it)
        }
    }
    return newArray
}

var intset = []int{1, 2, 3, 4, 5, 6, 7, 8, 9, 10}
out := Filter(intset, func(n int) bool {
   return n%2 == 1
})
fmt.Printf("%v\n", out)

out = Filter(intset, func(n int) bool {
    return n > 5
})
fmt.Printf("%v\n", out)

下图是一个比喻,其非常形象地说明了Map-Reduce是的业务语义,其在数据处理中非常有用。
map-reduce例子.png

业务示例
通过上面的一些示例,你可能有一些明白,Map/Reduce/Filter只是一种控制逻辑,真正的业务逻辑是在传给他们的数据和那个函数来定义的。是的,这是一个很经典的“业务逻辑”和“控制逻辑”分离解耦的编程模式。下面我们来看一个有业务意义的代码,来让大家强化理解一下什么叫“控制逻辑”与业务逻辑分离。

首先,我们一个员工对象,以及一些数据。

type Employee struct {
    Name     string
    Age      int
    Vacation int
    Salary   int
}

var list = []Employee{
    {"Hao", 44, 0, 8000},
    {"Bob", 34, 10, 5000},
    {"Alice", 23, 5, 9000},
    {"Jack", 26, 0, 4000},
    {"Tom", 48, 9, 7500},
    {"Marry", 29, 0, 6000},
    {"Mike", 32, 8, 4000},
}

相关的Reduce/Fitler函数:

func EmployeeCountIf(list []Employee, fn func(e *Employee) bool) int {
    count := 0
    for i, _ := range list {
        if fn(&list[i]) {
            count += 1
        }
    }
    return count
}

func EmployeeFilterIn(list []Employee, fn func(e *Employee) bool) []Employee {
    var newList []Employee
    for i, _ := range list {
        if fn(&list[i]) {
            newList = append(newList, list[i])
        }
    }
    return newList
}

func EmployeeSumIf(list []Employee, fn func(e *Employee) int) int {
    var sum = 0
    for i, _ := range list {
        sum += fn(&list[i])
    }
    return sum
}

简单说明一下:

  • EmployeeConutIf 和 EmployeeSumIf 分别用于统满足某个条件的个数或总数。它们都是Filter +
    Reduce的语义。
  • EmployeeFilterIn 就是按某种条件过虑。就是Fitler的语义。

于是我们就可以有如下的代码。

统计有多少员工大于40岁

old := EmployeeCountIf(list, func(e *Employee) bool {
    return e.Age > 40
})
fmt.Printf("old people: %d\n", old)

统计有多少员工薪水大于6000

high_pay := EmployeeCountIf(list, func(e *Employee) bool {
    return e.Salary >= 6000
})
fmt.Printf("High Salary people: %d\n", high_pay)
//High Salary people: 4

列出有没有休假的员工

no_vacation := EmployeeFilterIn(list, func(e *Employee) bool {
    return e.Vacation == 0
})
fmt.Printf("People no vacation: %v\n", no_vacation)
//People no vacation: [{Hao 44 0 8000} {Jack 26 0 4000} {Marry 29 0 6000}]

统计所有员工的薪资总和

total_pay := EmployeeSumIf(list, func(e *Employee) int {
    return e.Salary
})

fmt.Printf("Total Salary: %d\n", total_pay)
//Total Salary: 43500

统计30岁以下员工的薪资总和

younger_pay := EmployeeSumIf(list, func(e *Employee) int {
if e.Age < 30 {
    return e.Salary
} 
return 0 })

泛型Map-Reduce

我们可以看到,上面的Map-Reduce都因为要处理数据的类型不同而需要写出不同版本的Map-Reduce,虽然他们的代码看上去是很类似的。所以,这里就要带出来泛型编程了,Go语言在本文写作的时候还不支持泛型(注:Go开发团队技术负责人Russ Cox在2012年11月21golang-dev上的mail确认了Go泛型(type parameter)将在Go 1.18版本落地,即2022.2月份)。

简单版 Generic Map
所以,目前的Go语言的泛型只能用 interface{} + reflect来完成,interface{} 可以理解为C中的 void*,Java中的 Object ,reflect是Go的反射机制包,用于在运行时检查类型。
下面我们来看一下一个非常简单不作任何类型检查的泛型的Map函数怎么写。

func Map(data interface{}, fn interface{}) []interface{} {
    vfn := reflect.ValueOf(fn)
    vdata := reflect.ValueOf(data)
    result := make([]interface{}, vdata.Len())

    for i := 0; i < vdata.Len(); i++ {
        result[i] = vfn.Call([]reflect.Value{vdata.Index(i)})[0].Interface()
    }
    return result
}

上面的代码中

  • 通过 reflect.ValueOf() 来获得 interface{} 的值,其中一个是数据 vdata,另一个是函数 vfn;
  • 然后通过 vfn.Call() 方法来调用函数,通过 []refelct.Value{vdata.Index(i)}来获得数据。

Go语言中的反射的语法还是有点令人费解的,但是简单看一下手册还是能够读懂的。我这篇文章不讲反射,所以相关的基础知识还请大家自行Google相关的教程。
于是,我们就可以有下面的代码——不同类型的数据可以使用相同逻辑的Map()代码。

square := func(x int) int {
  return x * x
}
nums := []int{1, 2, 3, 4}

squared_arr := Map(nums,square)
fmt.Println(squared_arr)
//[1 4 9 16]

upcase := func(s string) string {
  return strings.ToUpper(s)
}
strs := []string{"Hao", "Chen", "MegaEase"}
upstrs := Map(strs, upcase);
fmt.Println(upstrs)
//[HAO CHEN MEGAEASE]

但是因为反射是运行时的事,所以,如果类型什么出问题的话,就会有运行时的错误。比如:

x := Map(5, 5)
fmt.Println(x)

上面的代码可以很轻松的编译通过,但是在运行时就出问题了,还是panic错误……

panic: reflect: call of reflect.Value.Len on int Value

goroutine 1 [running]:
reflect.Value.Len(0x10b5240, 0x10eeb58, 0x82, 0x10716bc)
        /usr/local/Cellar/go/1.15.3/libexec/src/reflect/value.go:1162 +0x185
main.Map(0x10b5240, 0x10eeb58, 0x10b5240, 0x10eeb60, 0x1, 0x14, 0x0)
        /Users/chenhao/.../map.go:12 +0x16b
main.main()
        /Users/chenhao/.../map.go:42 +0x465
exit status 2

健壮版的Generic Map

所以,如果要写一个健壮的程序,对于这种用interface{} 的“过度泛型”,就需要我们自己来做类型检查。下面是一个有类型检查的Map代码:

func Transform(slice, function interface{}) interface{} {
  return transform(slice, function, false)
}

func TransformInPlace(slice, function interface{}) interface{} {
  return transform(slice, function, true)
}

func transform(slice, function interface{}, inPlace bool) interface{} {
 
  //check the <code data-enlighter-language="raw" class="EnlighterJSRAW">slice</code> type is Slice
  sliceInType := reflect.ValueOf(slice)
  if sliceInType.Kind() != reflect.Slice {
    panic("transform: not slice")
  }

  //check the function signature
  fn := reflect.ValueOf(function)
  elemType := sliceInType.Type().Elem()
  if !verifyFuncSignature(fn, elemType, nil) {
    panic("trasform: function must be of type func(" + sliceInType.Type().Elem().String() + ") outputElemType")
  }

  sliceOutType := sliceInType
  if !inPlace {
    sliceOutType = reflect.MakeSlice(reflect.SliceOf(fn.Type().Out(0)), sliceInType.Len(), sliceInType.Len())
  }
  for i := 0; i < sliceInType.Len(); i++ {
    sliceOutType.Index(i).Set(fn.Call([]reflect.Value{sliceInType.Index(i)})[0])
  }
  return sliceOutType.Interface()

}

func verifyFuncSignature(fn reflect.Value, types ...reflect.Type) bool {

  //Check it is a funciton
  if fn.Kind() != reflect.Func {
    return false
  }
  // NumIn() - returns a function type's input parameter count.
  // NumOut() - returns a function type's output parameter count.
  if (fn.Type().NumIn() != len(types)-1) || (fn.Type().NumOut() != 1) {
    return false
  }
  // In() - returns the type of a function type's i'th input parameter.
  for i := 0; i < len(types)-1; i++ {
    if fn.Type().In(i) != types[i] {
      return false
    }
  }
  // Out() - returns the type of a function type's i'th output parameter.
  outType := types[len(types)-1]
  if outType != nil && fn.Type().Out(0) != outType {
    return false
  }
  return true
}

上面的代码一下子就复杂起来了,可见,复杂的代码都是在处理异常的地方。我不打算Walk through 所有的代码,别看代码多,但是还是可以读懂的,下面列几个代码中的要点:

  • 代码中没有使用Map函数,因为和数据结构和关键有含义冲突的问题,所以使用Transform,这个来源于 C++ STL库中的命名。
  • 有两个版本的函数,一个是返回一个全新的数组 – Transform(),一个是“就地完成” – TransformInPlace();
  • 在主函数中,用 Kind() 方法检查了数据类型是不是 Slice,函数类型是不是Func;
  • 检查函数的参数和返回类型是通过 verifyFuncSignature() 来完成的,其中:NumIn() – 用来检查函数的“入参”,NumOut() 用来检查函数的“返回值”;
  • 如果需要新生成一个Slice,会使用 reflect.MakeSlice() 来完成。
    好了,有了上面的这段代码,我们的代码就很可以很开心的使用了:

可以用于字符串数组:

list := []string{"1", "2", "3", "4", "5", "6"}
result := Transform(list, func(a string) string{
    return a +a +a
})
//{"111","222","333","444","555","666"}

可以用于整形数组:

list := []int{1, 2, 3, 4, 5, 6, 7, 8, 9}
TransformInPlace(list, func (a int) int {
  return a*3
})
//{3, 6, 9, 12, 15, 18, 21, 24, 27}

可以用于结构体:

var list = []Employee{
    {"Hao", 44, 0, 8000},
    {"Bob", 34, 10, 5000},
    {"Alice", 23, 5, 9000},
    {"Jack", 26, 0, 4000},
    {"Tom", 48, 9, 7500},
}

result := TransformInPlace(list, func(e Employee) Employee {
    e.Salary += 1000
    e.Age += 1
    return e
})

健壮版的 Generic Reduce
同样,泛型版的 Reduce 代码如下:

func Reduce(slice, pairFunc, zero interface{}) interface{} {
  sliceInType := reflect.ValueOf(slice)
  if sliceInType.Kind() != reflect.Slice {
    panic("reduce: wrong type, not slice")
  }

  len := sliceInType.Len()
  if len == 0 {
    return zero
  } else if len == 1 {
    return sliceInType.Index(0)
  }

  elemType := sliceInType.Type().Elem()
  fn := reflect.ValueOf(pairFunc)
  if !verifyFuncSignature(fn, elemType, elemType, elemType) {
    t := elemType.String()
    panic("reduce: function must be of type func(" + t + ", " + t + ") " + t)
  }

  var ins [2]reflect.Value
  ins[0] = sliceInType.Index(0)
  ins[1] = sliceInType.Index(1)
  out := fn.Call(ins[:])[0]

  for i := 2; i < len; i++ {
    ins[0] = out
    ins[1] = sliceInType.Index(i)
    out = fn.Call(ins[:])[0]
  }
  return out.Interface()
}

健壮版的 Generic Filter

同样,泛型版的 Filter 代码如下(同样分是否“就地计算”的两个版本):
func Filter(slice, function interface{}) interface{} {
  result, _ := filter(slice, function, false)
  return result
}

func FilterInPlace(slicePtr, function interface{}) {
  in := reflect.ValueOf(slicePtr)
  if in.Kind() != reflect.Ptr {
    panic("FilterInPlace: wrong type, " +
      "not a pointer to slice")
  }
  _, n := filter(in.Elem().Interface(), function, true)
  in.Elem().SetLen(n)
}

var boolType = reflect.ValueOf(true).Type()

func filter(slice, function interface{}, inPlace bool) (interface{}, int) {

  sliceInType := reflect.ValueOf(slice)
  if sliceInType.Kind() != reflect.Slice {
    panic("filter: wrong type, not a slice")
  }

  fn := reflect.ValueOf(function)
  elemType := sliceInType.Type().Elem()
  if !verifyFuncSignature(fn, elemType, boolType) {
    panic("filter: function must be of type func(" + elemType.String() + ") bool")
  }

  var which []int
  for i := 0; i < sliceInType.Len(); i++ {
    if fn.Call([]reflect.Value{sliceInType.Index(i)})[0].Bool() {
      which = append(which, i)
    }
  }

  out := sliceInType

  if !inPlace {
    out = reflect.MakeSlice(sliceInType.Type(), len(which), len(which))
  }
  for i := range which {
    out.Index(i).Set(sliceInType.Index(which[i]))
  }

  return out.Interface(), len(which)
}

后记

还有几个未尽事宜:

  1. 使用反射来做这些东西,会有一个问题,那就是代码的性能会很差。所以,上面的代码不能用于你需要高性能的地方。怎么解决这个问题,我们会在本系列文章的下一篇文章中讨论。
  2. 上面的代码大量的参考了 Rob Pike的版本,他的代码在 https://github.com/robpike/filter
  3. 其实,在全世界范围内,有大量的程序员都在问Go语言官方什么时候在标准库中支持 Map/Reduce,Rob Pike说,这种东西难写吗?还要我们官方来帮你们写么?这种代码我多少年前就写过了,但是,我从来一次都没有用过,我还是喜欢用“For循环”,我觉得你最好也跟我一起用“For循环”。

我个人觉得,Map/Reduce在数据处理的时候还是很有用的,Rob Pike可能平时也不怎么写“业务逻辑”的代码,所以,对他来说可能也不太了解业务的变化有多么的频繁……

当然,好还是不好,由你来判断,但多学一些编程模式是对自己的帮助也是很有帮助的。

导语

今天,我们来探讨下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占据了生活中越来越多的碎片时间,作为人的我们,还是需要像数独一样的“智力游戏”!做数独时,也许不仅仅是突然灵感乍现的快感,进行推理思考时的深沉,还有一份宁静的时光,不容亵渎。