abc

0%

go"泛型编程"

Posted on Edited on In

开始文章之前我们要先弄清楚什么是『泛型编程』。

In the simplest definition, generic programming is a style of computer programming in which algorithm are written in terms of types to-be-specified-later that are then instantiated when needed for specific types provided as parameters. – From Wikipedia.

简单来说就说，我们编写的代码不是针对特定的类型（比如适用于int, 不适用于string）才有效，而是大部分类型的参数都是可以工作的。

我们来看一个C++的例子：

1
2
3
4
5
6
7
8
9
10
#include <algorithm>
#include <vector>

int main() {
    std::vector<int> A{3,1,2,4,5};
    std::vector<string> B{"golang", "I", "am"};
    std::sort(A.begin(), A.end());	//after this, A={1,2,3,4,5}
    std::sort(B.begin(), B.end());	//after this, B={"I", "am", "golang"}
    return 0;
}

这里的sort函数就是一个泛型编程例子。至于为什么{“golang”, “I”, “am”}排序之后变成{“I”, “am”, “golang”}是因为string类型的比较函数是字典序。细心的人可能会注意到这儿直接使用大括号来初始化vector，是的，这是C++11。

Go有泛型编程吗？

没有。

为什么Go没有泛型编程？

这里应用官网的回答

Why does Go not have generic types?
Generics may well be added at some point. We don’t feel an urgency for them.Generics are convenient but they come at a cost in complexity in the type system and run-time…
Meanwhile, Go’s built-in maps and slices, plus the ability to use the empty interface to construct containers mean in many cases it is possible to write code that does what generics would enable, if less smoothly.

翻译一下，就是尽管泛型很好，但是它会让我们的语言设计复杂度提升，所以我们现在暂时不打算支持，以后可能会支持。另外，虽然我们现在很弱，但是使用Interface也是可以实现泛型了（呵呵）。

Go的泛型编程实现

前面说了使用Go的interface可以实现泛型编程，那么我们先理解一下interface。

duck typing

这里引入一个概念，duck typing。

When I see a bird that walks like a duck and swins like a duck and quacks like a duck, I call that bird a duck. – James Whitcomb Riley

结合维基百科的定义，duck typing是面向对象编程语言的一种类型定义方法。我们判断一个对象是神马不是通过它的类型定义来判断，而是判断它是否满足某些特定的方法和属性定义。

interface

那么Go中interface是什么呢？interface是一组方法集合。我们可以把它看成一种定义内部方法的动态数据类型，任意实现了这些方法的数据类型都可以认为是特定的数据类型。

泛型编程

其实Go语言中也提供了sort函数，我们看一下源码，src/sort/sort.go。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
package sort

// A type, typically a collection, that satisfies sort.Interface can be
// sorted by the routines in this package.  The methods require that the
// elements of the collection be enumerated by an integer index.
type Interface interface {
    // Len is the number of elements in the collection.
    Len() int
    // Less reports whether the element with
    // index i should sort before the element with index j.
    Less(i, j int) bool
    // Swap swaps the elements with indexes i and j.
    Swap(i, j int)
}

...

// Sort sorts data.
// It makes one call to data.Len to determine n, and O(n*log(n)) calls to
// data.Less and data.Swap. The sort is not guaranteed to be stable.
func Sort(data Interface) {
    // Switch to heapsort if depth of 2*ceil(lg(n+1)) is reached.
    n := data.Len()
    maxDepth := 0
    for i := n; i > 0; i >>= 1 {
        maxDepth++
    }
    maxDepth *= 2
    quickSort(data, 0, n, maxDepth)
}

其中省略了一些源码，我们看到package中定义了一个Interface，包含三个方法：Len(), Less(), Swap()。Interface作为参数传递给Sort。我们要使用Sort，只需要实现Interface的三个方法就可以使用下面是一个例子。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
package main

import (
    "fmt"
    "sort"
)

type Person struct {
    Name string
    Age  int
}

func (p Person) String() string {
    return fmt.Sprintf("%s: %d", p.Name, p.Age)
}

// ByAge implements sort.Interface for []Person based on
// the Age field.
type ByAge []Person

func (a ByAge) Len() int           { return len(a) }
func (a ByAge) Swap(i, j int)      { a[i], a[j] = a[j], a[i] }
func (a ByAge) Less(i, j int) bool { return a[i].Age < a[j].Age }

func main() {
    people := []Person{
        {"Bob", 31},
        {"John", 42},
        {"Michael", 17},
        {"Jenny", 26},
    }

    fmt.Println(people)
    sort.Sort(ByAge(people))
    fmt.Println(people)
}