0%

【Go语言设计与实现】Context

在Go语言中,控制并发有两种经典的方式,一种是WaitGroup, 另外一种就是Context。

什么是WaitGroup

WaitGroup是一种控制并发的方式,通过控制多个Go Routine同时完成

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
func main() {
var wg sync.WaitGroup

wg.Add(2)
go func() {
time.Sleep(time.Second * 2)
fmt.Println("routine 1 done")
wg.Done()
}()
go func() {
time.Sleep(time.Second * 2)
fmt.Println("routine 2 done")
wg.Done()
wg.Wait()
fmt.Println("all routine done")
}

使用WaitGroup的情景在于:多个goroutine协同做同一件事情,只有当所有的goroutine都完成时,这件事情才算完成。

但是实际的业务里面,可能还会碰到这么一种场景:需要我们主动的通知某一个goroutine结束

举个例子,我们开启一个后台goroutine一直做一件事情,比如监控,现在不需要了,就需要通知这个监控goroutine结束,不然它会一直跑,产生泄露

chan通知

一个goroutine启动之后,我们是无法控制它的,大部分情况下是等待自己结束。为了在通知这个goroutine结束,经常采用的方式是chan+select。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
func main() {
stop := make(chan bool)

go func() {
for {
select {
case <- stop:
fmt.Println("monitor exited...")
return
default:
fmt.Println("monitoring...")
time.Sleep(time.Second * 2)
}
}
}()

time.Sleep(time.Second * 10)
fmt.Println("It's time to stop monitoring")
stop <- true
time.Sleep(time.Second * 5)
}

在这个例子中,我们定义了一个stop的channel,在后台的goroutine中,我们使用select判断stop是否可以接收到值,如果可以接收到,就表示可以退出停止了;如果没有接收到,就会执行default里面的逻辑,继续监控。

这样一来,我们可以在其他的goroutine中给stop发送值了,比如这里是在main goroutine中发送的控制这个监控的goroutine结束。

这种chan+select的方式,是一种比较优雅地结束goroutine的方式。不过他也有自己的局限性,如果有很多个goroutine都需要控制结束怎么办?如果这些goroutine中又衍生了更多的goroutine怎么办呢?如果一层一层的无穷尽的goroutine呢?

这种场景下仅仅用channel是不够的,所以我们引入了context。

初识Context

上面的场景其实也很常见,比如一个网络请求Request,每个Request都需要开启一个goroutine做一些事情,这些goroutine又可能会开启其他的goroutine。所以我们需要一种可以跟踪goroutine的方案,才能达到控制他们的目的,这就是Go语言的Context做的事情,称之为goroutine的上下文

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
func main() {
ctx, cancel := context.WithCancel(context.Background())
go func(ctx context.Context) {
for {
select {
case <- ctx.Done():
fmt.Println("monitor exited...")
return
default:
fmt.Println("monitoring...")
time.Sleep(time.Second * 2)
}
}
}(ctx)

time.Sleep(time.Second * 10)
fmt.Println("It's time to stop monitor")
cancel()
time.Sleep(time.Second * 2)
}

Context控制多个goroutine

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
func main() {
ctx, cancel := context.WithCancel(context.Background())
go watch(ctx, "monitor1")
go watch(ctx, "monitor2")
go watch(ctx, "monitor3")

time.Sleep(time.Second * 10)
fmt.Println("It's time to stop monitor")
cancel()
time.Sleep(time.Second * 5)
}

func watch() {
for {
select {
case <- ctx.Done():
fmt.Println(name, "monitor exited")
return
default:
fmt.Println(name, "goroutine monitoring")
time.Sleep(time.Second * 2)
}
}
}

Context接口

标准库中Context定义如下:

1
2
3
4
5
6
type Context interface {
Deadline() (deadline time.Time, ok bool)
Done() <- struct{}
Err() error
Value(key interface{}) interface{}
}

可以看到Context是一个interface,在Go语言里面,interface是一个使用非常广泛的结构,它可以接纳任何类型。Context定义很简单,一共有4个方法

  • Deadline方法是获取设置的截止时间的意思,第一个返回值是截止时间,到了这个时间点,Context会自动发起取消请求。第二个返回值ok == false表示没有设置截止时间,如果需要取消的话,需要调用取消函数取消
  • Done方法返回一个只读的channel,类型是struct{}。在goroutine中,如果该方法返回的chan可以读取,则意味着parent context已经发起了取消请求,我们通过Done方法收到这个信号后,就应该做清理操作,然后退出goroutine,释放资源。之后Err方法会返回一个错误,告知为什么Context被取消
  • Err方法返回取消的原因
  • Value方法获取该Context上绑定的值,是一个键值对,所以要通过一个Key才可以获取对应的值,这个值一般是线程安全的。

Context的实现方法

Context虽然是一个接口,但是并不需要使用方实现。golang内置的context包,已经帮我们实现了2个方法,一般在代码中都是以这两个(Background和TODO)作为最顶层的parent context,然后在衍生出子context。这些Context对象形成一棵树:当一个Context对象被取消时,继承自它所有的Context都会被取消。

下面是golang的标准库中的实现

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
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
// An emptyCtx is never canceled, has no values, and has no deadline. It is not
// struct{}, since vars of this type must have distinct addresses.
type emptyCtx int

func (*emptyCtx) Deadline() (deadline time.Time, ok bool) {
return
}

func (*emptyCtx) Done() <-chan struct{} {
return nil
}

func (*emptyCtx) Err() error {
return nil
}

func (*emptyCtx) Value(key interface{}) interface{} {
return nil
}

func (e *emptyCtx) String() string {
switch e {
case background:
return "context.Background"
case todo:
return "context.TODO"
}
return "unknown empty Context"
}

var (
background = new(emptyCtx)
todo = new(emptyCtx)
)

// Background returns a non-nil, empty Context. It is never canceled, has no
// values, and has no deadline. It is typically used by the main function,
// initialization, and tests, and as the top-level Context for incoming
// requests.
func Background() Context {
return background
}

// TODO returns a non-nil, empty Context. Code should use context.TODO when
// it's unclear which Context to use or it is not yet available (because the
// surrounding function has not yet been extended to accept a Context
// parameter). TODO is recognized by static analysis tools that determine
// whether Contexts are propagated correctly in a program.
func TODO() Context {
return todo
}

Context的继承

有了以上的根Context,那么如何衍生更多的子Context呢?这就要靠context包为我们提供的With系列函数了

1
2
3
4
func WithCancel(parent Context) (ctx Context, cancel CancelFunc)
func WithDeadline(parent Context, deadline time.Time) (Context, CancelFunc)
func WithTimeout(parent Context, timeout time.Duration) (Context, CancelFunc)
func WithValue(parent Context, key, val interface{}) Context

通过这些函数,就创建了一棵Context,树的每个节点都可以有更多的子节点,节点层级可以有任意多个

  • WithCancel函数,传递一个父Context作为参数,返回子Context,以及一个取消函数用来取消Context
  • WithDeadline函数,和WithCancel差不多,他会传递一个截至时间参数,意味着到了这个时间点,会自动取消Context。当然我们也可以不等到这个时候,可以提前通过取消函数进行取消
  • WithTimeoutWithDeadline差不多,只是表示的是多长时间后取消Context
  • WithValue函数和取消Context无关,它是为了生成一个绑定了一个键值对数据的Context,这个绑定的数据可以通过Context.Value方法访问到。这是我们实际中经常要用到的技巧,一般我们想要通过上下文传递数据时,可以通过这个方法,比如我们需要trace追踪系统调用栈的时候。

Context使用原则和技巧

  • 不要把Context放在结构体中,要以参数的方式传递,parent Context一般是Background
  • 应该要把Context作为第一个参数传递给入口请求和出口请求链路上的每一个函数,放在第一位,变量名都统一,如ctx
  • 给一个函数方法传递Context的时候,不要传递nil,否则在trace追踪的时候,就会断了连接
  • Context的Value相关方法应该传递必须的数据,不要什么数据都是用这个传递
  • Context是线程安全的,可以放心的在多个goroutine中传递
  • 可以把一个Context对象传递给任意个数的goroutine,对他执行取消操作时,所有的goroutine都会接收到取消信号

Context常用方法实例

调用Context Done方法取消

1
2
3
4
5
6
7
8
9
10
11
12
13
func Stream(ctx context.Context, out chan<- Value) error {
for {
v, err := DoSomething(ctx)
if err != nil {
return err
}
select {
case <- ctx.Done():
return ctx.Err()
case out <- v:
}
}
}

通过context.WithValue来传值

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
func main() {
ctx, cancel := context.WithCancel(context.Background)
valueCtx := context.WithValue(ctx, key, "add value")

go watch(valueCtx)
time.Sleep(time.Second * 10)
cancel()

time.Sleep(time.Second * 5)
}

func watch(ctx context.Context) {
for {
select {
case <- ctx.Done():
fmt.Println(ctx.Value(key), "is canceled")
return
default:
fmt.Println(ctx.Value(key), "int goroutine")
time.Sleep(time.Second * 2)
}
}
}

超时取消context.WithTimeout

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
37
38
39
40
package main

import (
"fmt"
"sync"
"time"
"context"
)

var (
wg sync.WaitGroup
)

func work(ctx context.Context) error {
defer wg.Done()

for i := 0; i < 1000; i++ {
select {
case <- time.After(time.Second * 2):
fmt.Println("Doing some work", i)
case <- ctx.Done():
fmt.Println("Cancel the context", i)
return ctx.Err()
}
}
return nil
}

func main() {
ctx, cancel := context.WithTimeout(context.Background, time.Second * 4)
defer cancel()

fmt.Println("Hey, I'm going to do some work")

wg.Add(1)
go work(ctx)
wg.Wait()

fmt.Println("Finished, I'm going home")
}

截至时间取消context.WithDeadline

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
package main

import (
"context"
"fmt"
"time"
)

func main() {
d := time.Now().Add(time.Second * 1)
ctx, cancel := context.WithDeadline(context.Backend(), d)

// Even though ctx will be expired, it is good practice to call its
// cancelation function in any case. Failure to do so may keep the
// context and its parent alive longer than necessary.
defer cancel()

select {
case <- time.After(time.Second * 2):
fmt.Println("OverSleep")
case <- ctx.Done():
fmt.Println(ctx.Err())
}
}

Reference

上下文 context.Context 是用来设置截止日期、同步信号,传递请求相关值的结构体。上下文与 Goroutine 有比较密切的关系。context.Context 是 Go 语言中独特的设计,在其他编程语言中我们很少见到类似的概念。

context.Context 是 Go 语言在 1.7 版本中引入标准库的接口1,该接口定义了四个需要实现的方法,其中包括:

  1. Deadline — 返回 context.Context 被取消的时间,也就是完成工作的截止日期;

  2. Done — 返回一个 Channel,这个 Channel 会在当前工作完成或者上下文被取消之后关闭,多次调用 Done 方法会返回同一个 Channel;

  3. ```
    Err

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12



    — 返回



    `context.Context`



    结束的原因,它只会在

    Done

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17



    返回的 Channel 被关闭时才会返回非空的值;

    1. 如果 [`context.Context`](https://github.com/golang/go/blob/df2999ef43ea49ce1578137017949c0ee660608a/src/context/context.go#L62-L154) 被取消,会返回 `Canceled` 错误;
    2. 如果 [`context.Context`](https://github.com/golang/go/blob/df2999ef43ea49ce1578137017949c0ee660608a/src/context/context.go#L62-L154) 超时,会返回 `DeadlineExceeded` 错误;

    4. `Value` — 从 [`context.Context`](https://github.com/golang/go/blob/df2999ef43ea49ce1578137017949c0ee660608a/src/context/context.go#L62-L154) 中获取键对应的值,对于同一个上下文来说,多次调用 `Value` 并传入相同的 `Key` 会返回相同的结果,该方法可以用来传递请求特定的数据;

    ```go
    type Context interface {
    Deadline() (deadline time.Time, ok bool)
    Done() <-chan struct{}
    Err() error
    Value(key interface{}) interface{}
    }

context 包中提供的 context.Backgroundcontext.TODOcontext.WithDeadlinecontext.WithValue 函数会返回实现该接口的私有结构体,我们会在后面详细介绍它们的工作原理。

设计原理

在 Goroutine 构成的树形结构中对信号进行同步以减少计算资源的浪费是 context.Context 的最大作用。Go 服务的每一个请求的都是通过单独的 Goroutine 处理的2,HTTP/RPC 请求的处理器会启动新的 Goroutine 访问数据库和其他服务。

如下图所示,我们可能会创建多个 Goroutine 来处理一次请求,而 context.Context 的作用就是在不同 Goroutine 之间同步请求特定数据、取消信号以及处理请求的截止日期。

golang-context-usage

图 6-1 Context 与 Goroutine 树

每一个 context.Context 都会从最顶层的 Goroutine 一层一层传递到最下层。context.Context 可以在上层 Goroutine 执行出现错误时,将信号及时同步给下层。

golang-without-context

图 6-2 不使用 Context 同步信号

如上图所示,当最上层的 Goroutine 因为某些原因执行失败时,下层的 Goroutine 由于没有接收到这个信号所以会继续工作;但是当我们正确地使用 context.Context 时,就可以在下层及时停掉无用的工作以减少额外资源的消耗:

golang-with-context

图 6-3 使用 Context 同步信号

我们可以通过一个代码片段了解 context.Context 是如何对信号进行同步的。在这段代码中,我们创建了一个过期时间为 1s 的上下文,并向上下文传入 handle 函数,该方法会使用 500ms 的时间处理传入的『请求』:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
func main() {
ctx, cancel := context.WithTimeout(context.Background(), 1*time.Second)
defer cancel()

go handle(ctx, 500*time.Millisecond)
select {
case <-ctx.Done():
fmt.Println("main", ctx.Err())
}
}

func handle(ctx context.Context, duration time.Duration) {
select {
case <-ctx.Done():
fmt.Println("handle", ctx.Err())
case <-time.After(duration):
fmt.Println("process request with", duration)
}
}

因为过期时间大于处理时间,所以我们有足够的时间处理该『请求』,运行上述代码会打印出如下所示的内容:

1
2
3
$ go run context.go
process request with 500ms
main context deadline exceeded

handle 函数没有进入超时的 select 分支,但是 main 函数的 select 却会等待 context.Context 的超时并打印出 main context deadline exceeded

如果我们将处理『请求』时间增加至 1500ms,整个程序都会因为上下文的过期而被中止,:

1
2
3
$ go run context.go
main context deadline exceeded
handle context deadline exceeded

相信这两个例子能够帮助各位读者理解 context.Context 的使用方法和设计原理 — 多个 Goroutine 同时订阅 ctx.Done() 管道中的消息,一旦接收到取消信号就立刻停止当前正在执行的工作。

默认上下文

context 包中最常用的方法还是 context.Backgroundcontext.TODO,这两个方法都会返回预先初始化好的私有变量 backgroundtodo,它们会在同一个 Go 程序中被复用:

1
2
3
4
5
6
7
func Background() Context {
return background
}

func TODO() Context {
return todo
}

这两个私有变量都是通过 new(emptyCtx) 语句初始化的,它们是指向私有结构体 context.emptyCtx 的指针,这是最简单、最常用的上下文类型:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
type emptyCtx int

func (*emptyCtx) Deadline() (deadline time.Time, ok bool) {
return
}

func (*emptyCtx) Done() <-chan struct{} {
return nil
}

func (*emptyCtx) Err() error {
return nil
}

func (*emptyCtx) Value(key interface{}) interface{} {
return nil
}

从上述代码,我们不难发现 context.emptyCtx 通过返回 nil 实现了 context.Context 接口,它没有任何特殊的功能。

golang-context-hierarchy

图 6-4 Context 层级关系

从源代码来看,context.Backgroundcontext.TODO 函数其实也只是互为别名,没有太大的差别。它们只是在使用和语义上稍有不同:

  • context.Background 是上下文的默认值,所有其他的上下文都应该从它衍生(Derived)出来;
  • context.TODO 应该只在不确定应该使用哪种上下文时使用;

在多数情况下,如果当前函数没有上下文作为入参,我们都会使用 context.Background 作为起始的上下文向下传递。

取消信号

context.WithCancel 函数能够从 context.Context 中衍生出一个新的子上下文并返回用于取消该上下文的函数(CancelFunc)。一旦我们执行返回的取消函数,当前上下文以及它的子上下文都会被取消,所有的 Goroutine 都会同步收到这一取消信号。

golang-parent-cancel-context

图 6-5 Context 子树的取消

我们直接从 context.WithCancel 函数的实现来看它到底做了什么:

1
2
3
4
5
func WithCancel(parent Context) (ctx Context, cancel CancelFunc) {
c := newCancelCtx(parent)
propagateCancel(parent, &c)
return &c, func() { c.cancel(true, Canceled) }
}
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
func propagateCancel(parent Context, child canceler) {
done := parent.Done()
if done == nil {
return // 父上下文不会触发取消信号
}
select {
case <-done:
child.cancel(false, parent.Err()) // 父上下文已经被取消
return
default:
}

if p, ok := parentCancelCtx(parent); ok {
p.mu.Lock()
if p.err != nil {
child.cancel(false, p.err)
} else {
p.children[child] = struct{}{}
}
p.mu.Unlock()
} else {
go func() {
select {
case <-parent.Done():
child.cancel(false, parent.Err())
case <-child.Done():
}
}()
}
}

上述函数总共与父上下文相关的三种不同的情况:

  1. parent.Done() == nil,也就是 parent 不会触发取消事件时,当前函数会直接返回;

1
child

的继承链包含可以取消的上下文时,会判断

1
parent

是否已经触发了取消信号;

  • 如果已经被取消,child 会立刻被取消;
  • 如果没有被取消,child 会被加入 parentchildren 列表中,等待 parent 释放取消信号;
  1. 在默认情况下

    1. 运行一个新的 Goroutine 同时监听 parent.Done()child.Done() 两个 Channel
    2. parent.Done() 关闭时调用 child.cancel 取消子上下文;

context.propagateCancel 的作用是在 parentchild 之间同步取消和结束的信号,保证在 parent 被取消时,child 也会收到对应的信号,不会发生状态不一致的问题。

context.cancelCtx 实现的几个接口方法也没有太多值得分析的地方,该结构体最重要的方法是 cancel,这个方法会关闭上下文中的 Channel 并向所有的子上下文同步取消信号:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
func (c *cancelCtx) cancel(removeFromParent bool, err error) {
c.mu.Lock()
if c.err != nil {
c.mu.Unlock()
return
}
c.err = err
if c.done == nil {
c.done = closedchan
} else {
close(c.done)
}
for child := range c.children {
child.cancel(false, err)
}
c.children = nil
c.mu.Unlock()

if removeFromParent {
removeChild(c.Context, c)
}
}

除了 context.WithCancel 之外,context 包中的另外两个函数 context.WithDeadlinecontext.WithTimeout 也都能创建可以被取消的计时器上下文 context.timerCtx

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
func WithTimeout(parent Context, timeout time.Duration) (Context, CancelFunc) {
return WithDeadline(parent, time.Now().Add(timeout))
}

func WithDeadline(parent Context, d time.Time) (Context, CancelFunc) {
if cur, ok := parent.Deadline(); ok && cur.Before(d) {
return WithCancel(parent)
}
c := &timerCtx{
cancelCtx: newCancelCtx(parent),
deadline: d,
}
propagateCancel(parent, c)
dur := time.Until(d)
if dur <= 0 {
c.cancel(true, DeadlineExceeded) // 已经过了截止日期
return c, func() { c.cancel(false, Canceled) }
}
c.mu.Lock()
defer c.mu.Unlock()
if c.err == nil {
c.timer = time.AfterFunc(dur, func() {
c.cancel(true, DeadlineExceeded)
})
}
return c, func() { c.cancel(true, Canceled) }
}

context.WithDeadline 方法在创建 context.timerCtx 的过程中,判断了父上下文的截止日期与当前日期,并通过 time.AfterFunc 创建定时器,当时间超过了截止日期后会调用 context.timerCtx.cancel 方法同步取消信号。

context.timerCtx 结构体内部不仅通过嵌入了context.cancelCtx 结构体继承了相关的变量和方法,还通过持有的定时器 timer 和截止时间 deadline 实现了定时取消这一功能:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
type timerCtx struct {
cancelCtx
timer *time.Timer // Under cancelCtx.mu.

deadline time.Time
}

func (c *timerCtx) Deadline() (deadline time.Time, ok bool) {
return c.deadline, true
}

func (c *timerCtx) cancel(removeFromParent bool, err error) {
c.cancelCtx.cancel(false, err)
if removeFromParent {
removeChild(c.cancelCtx.Context, c)
}
c.mu.Lock()
if c.timer != nil {
c.timer.Stop()
c.timer = nil
}
c.mu.Unlock()
}

context.timerCtx.cancel 方法不仅调用了 context.cancelCtx.cancel,还会停止持有的定时器减少不必要的资源浪费。

传值方法

在最后我们需要了解如何使用上下文传值,context 包中的 context.WithValue 函数能从父上下文中创建一个子上下文,传值的子上下文使用 context.valueCtx 类型:

1
2
3
4
5
6
7
8
9
func WithValue(parent Context, key, val interface{}) Context {
if key == nil {
panic("nil key")
}
if !reflectlite.TypeOf(key).Comparable() {
panic("key is not comparable")
}
return &valueCtx{parent, key, val}
}

context.valueCtx 结构体会将除了 Value 之外的 ErrDeadline 等方法代理到父上下文中,它只会响应 context.valueCtx.Value 方法,这个方法的实现也很简单:

1
2
3
4
5
6
7
8
9
10
11
type valueCtx struct {
Context
key, val interface{}
}

func (c *valueCtx) Value(key interface{}) interface{} {
if c.key == key {
return c.val
}
return c.Context.Value(key)
}

如果 context.valueCtx 中存储的键值对与 context.valueCtx.Value 方法中传入的参数不匹配,就会从父上下文中查找该键对应的值直到在某个父上下文中返回 nil 或者查找到对应的值。

小结

Go 语言中的 context.Context 的主要作用还是在多个 Goroutine 组成的树中同步取消信号以减少对资源的消耗和占用,虽然它也有传值的功能,但是这个功能我们还是很少用到。

在真正使用传值的功能时我们也应该非常谨慎,使用 context.Context 进行传递参数请求的所有参数一种非常差的设计,比较常见的使用场景是传递请求对应用户的认证令牌以及用于进行分布式追踪的请求 ID。

延伸阅读

最后的彩蛋

其实在看这个的时候,想到这是Context的With系列函数的设计是一个特别有意思的算法题,题目描述如下:

  1. 我们有一个Context树,根Context可以是Backgroud的Context或者是TODO的Context
  2. 可以从根Context出发,每个parent Context可以有自己的child Context
  3. 我们想实现这个一个函数WithCancel(parent Context) (ctx Context, cancel CancelFunc),输入参数是parent,输出是子context和cancel函数
  4. 当调用cancel函数时,继承自它的所有Context都会被取消
  5. 补充的一个背景是,所有的context都有上面说的4个函数

那么要实现这么一个功能,我们就需要考虑其对应的数据结构和算法了。

具体的做法是什么呢?晚上回去好好想想