在 Golang 中使用 go 关键字可以很方便地创建轻量级线程，也就是 Goroutine，从而实现并发。本文是《Go 语言之旅》中“并发（Concurrency）”章节中的练习题，并附上了我自己在学习这部教程时写出的解答代码，供大家参考。

教程其他章节的练习题解答可以点击链接查看：

  1. 基础
  2. 方法和接口
  3. 并发（本文）

本文地址：https://www.jeddd.com/article/a-tour-of-go-exercises-concurrency.html

练习：等价二叉查找树

题目

题目链接：中文 | English

不同二叉树的叶节点上可以保存相同的值序列。例如，以下两个二叉树都保存了序列 1，1，2，3，5，8，13。

在大多数语言中，检查两个二叉树是否保存了相同序列的函数都相当复杂。 我们将使用 Go 的并发和信道来编写一个简单的解法。

本例使用了 tree 包，它定义了类型：

type Tree struct {
 Left  *Tree
 Value int
 Right *Tree
}

1.实现 Walk 函数。

2.测试 Walk 函数。

函数 tree.New(k) 用于构造一个随机结构的已排序二叉查找树，它保存了值 k, 2k, 3k, ..., 10k。

创建一个新的信道 ch 并且对其进行步进：

go Walk(tree.New(1), ch)

然后从信道中读取并打印 10 个值。应当是数字 1, 2, 3, ..., 10。

3.用 Walk 实现 Same 函数来检测 t1 和 t2 是否存储了相同的值。

4.测试 Same 函数。

Same(tree.New(1), tree.New(1)) 应当返回 true，而 Same(tree.New(1), tree.New(2)) 应当返回 false。

Tree 的文档可在这里找到。

解答

我另外实现了一个 inorder 函数来完成实际的中序遍历操作；而 Walk 函数仅负责调用 inorder。

package main

import (
    "fmt"
    "golang.org/x/tour/tree"
)

/* 中序遍历二叉树 */
func inorder(t *tree.Tree, ch chan int) {
    if t != nil {
        inorder(t.Left, ch)
        ch <- t.Value
        inorder(t.Right, ch)
    }
}

// Walk 步进 tree t 将所有的值从 tree 发送到 channel ch。
func Walk(t *tree.Tree, ch chan int) {
    inorder(t, ch) // 从根节点开始中序遍历
    close(ch)      // 关闭信道表示遍历结束
}

// Same 检测树 t1 和 t2 是否含有相同的值。
func Same(t1, t2 *tree.Tree) bool {
    // 创建两个goroutine分别对两棵树进行中序遍历
    ch1, ch2 := make(chan int), make(chan int)
    go Walk(t1, ch1)
    go Walk(t2, ch2)

    // 循环直到信道ch1关闭
    for x := range ch1 {
        y := <-ch2
        if x != y {
            return false
        }
    }
    return true
}

func main() {
    // 随机生成两个由节点1~10组成的二叉查找树
    t1, t2 := tree.New(1), tree.New(1)
    fmt.Println("t1:", t1)
    fmt.Println("t2:", t2)

    // 测试它们是否等价
    fmt.Println(Same(t1, t2))
}

运行结果如下。

t1: ((((1 (2)) 3 (4)) 5 ((6) 7 ((8) 9))) 10)
t2: ((((1) 2 (3)) 4 (5 (6))) 7 ((8) 9 (10)))
true

练习：Web 爬虫

题目

题目链接：中文 | English

在这个练习中，我们将会使用 Go 的并发特性来并行化一个 Web 爬虫。

修改 Crawl 函数来并行地抓取 URL，并且保证不重复。

提示：你可以用一个 map 来缓存已经获取的 URL，但是要注意 map 本身并不是并发安全的！

解答

这题只是一个模拟的爬虫，它并没有真正去访问网页，而是用 fakeFetcher 和 fakeResult 来模拟被爬取的网站。本题有多种做法。我的解答中用 map[string]bool 和互斥锁实现了一个并发安全的集合类型 SafeSet，然后为该类型实现了两个方法 add 和 has，详见代码注释。

package main

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

type Fetcher interface {
    // Fetch 返回 URL 的 body 内容，并且将在这个页面上找到的 URL 放到一个 slice 中。
    Fetch(url string) (body string, urls []string, err error)
}

/* 用map实现的并发安全的集合 */
type SafeSet struct {
    v   map[string]bool // 在集合中的字符串被映射为true
    mux sync.Mutex
}

/* 向集合中添加元素 */
func (set *SafeSet) add(str string) {
    set.mux.Lock()
    set.v[str] = true // 把字符串加入集合中
    set.mux.Unlock()
}

/* 检查元素是否在集合中 */
func (set *SafeSet) has(str string) bool {
    set.mux.Lock()
    defer set.mux.Unlock()
    return set.v[str] // 返回true或false
}

// 全局变量，用于记录访问过的URL
var visited = &SafeSet{v: make(map[string]bool)}

// Crawl 使用 fetcher 从某个 URL 开始递归的爬取页面，直到达到最大深度。
func Crawl(url string, depth int, fetcher Fetcher) {
    // TODO: 并行的抓取 URL。
    // TODO: 不重复抓取页面。
    // 下面并没有实现上面两种情况：
    if depth <= 0 {
        return
    }
    body, urls, err := fetcher.Fetch(url)
    visited.add(url) // 标记当前URL已访问过

    //error的原因是不存在该URL对应的网页
    if err != nil {
        fmt.Println(err) // 输出错误日志
        return
    }

    fmt.Printf("found: %s %q\n", url, body) // 输出正常访问日志
    for _, u := range urls {
        if !visited.has(u) { // 不重复访问
            go Crawl(u, depth-1, fetcher)
        }
    }
    return
}

func main() {
    Crawl("https://golang.org/", 4, fetcher)
    time.Sleep(time.Second)
}

// fakeFetcher 是返回若干结果的 Fetcher。
type fakeFetcher map[string]*fakeResult

type fakeResult struct {
    body string
    urls []string
}

func (f fakeFetcher) Fetch(url string) (string, []string, error) {
    if res, ok := f[url]; ok {
        return res.body, res.urls, nil
    }
    return "", nil, fmt.Errorf("not found: %s", url)
}

// fetcher 是填充后的 fakeFetcher。
var fetcher = fakeFetcher{
    "https://golang.org/": &fakeResult{
        "The Go Programming Language",
        []string{
            "https://golang.org/pkg/",
            "https://golang.org/cmd/",
        },
    },
    "https://golang.org/pkg/": &fakeResult{
        "Packages",
        []string{
            "https://golang.org/",
            "https://golang.org/cmd/",
            "https://golang.org/pkg/fmt/",
            "https://golang.org/pkg/os/",
        },
    },
    "https://golang.org/pkg/fmt/": &fakeResult{
        "Package fmt",
        []string{
            "https://golang.org/",
            "https://golang.org/pkg/",
        },
    },
    "https://golang.org/pkg/os/": &fakeResult{
        "Package os",
        []string{
            "https://golang.org/",
            "https://golang.org/pkg/",
        },
    },
}

由于并发运行的结果可能不唯一，所以下面的结果仅供参考。

found: https://golang.org/ "The Go Programming Language"
found: https://golang.org/pkg/ "Packages"
found: https://golang.org/pkg/os/ "Package os"
not found: https://golang.org/cmd/
found: https://golang.org/pkg/fmt/ "Package fmt"

References

  1. Go 语言之旅
  2. A Tour of Go

本文地址：https://www.jeddd.com/article/a-tour-of-go-exercises-concurrency.html