练习 Web 爬虫

问题

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

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

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

背景知识

  1. 学习 Go语言的sync.Mutex用法,阅读计数器实现的源代码,这个例子也可以参数计数器来实现。
  2. 在多个协程抓取时可以添加互斥锁,这也是Mutex的应用。
  3. 需要你深刻的理解协程的编程方式,也需要注意信道的数据获取方式。

实现思路

  1. 基本代码算是实现了,但是没有做协程安全,如果多个协程同时处理,就会有变量被覆盖的情况。
  2. 还有一种情况,就是并没有对爬虫进行去重判断,有可能实现的爬虫会一直死循环,并需要对map进行互斥锁判断,避免会有冲突。
  3. URL的抓取实现是一些测试用例,并不是真实世界的抓取,现实中的爬虫会比这个更复杂,简单的来讲,最少要添加一个超时的处理,异常的处理。
  4. 在Crawl中如何实现协程抓取URL?如何同步控制map的URL更新?
  5. 定义SafeCounter类型,类似计数器有两个变量,一个是字符串和整数的映射,另外一个是互斥锁的实现。定义一个全局变量sc,在全部的函数里都可以使用。
  6. 由于map不是协程安全,所有验证函数validUrl和标记函数markUrl函数,都需要加下互斥锁。
  7. 并行的抓取,可以在Crawl实现,对抓取回来的内容里的二级URL进行协程处理,并发抓取URL。
    难点在于下面这两个地方:
//方案1
//开启协程处理二级URL
ch := make(chan int, len(urls))
for _, u := range urls {
    go crawl(u, depth-1, fetcher, ch)
}
for i:=0; i < len(urls); i++ {
    //从信道接受数据
     <- ch
}

func crawl(url string, depth int, fetcher Fetcher, ch chan int) {
    Crawl(url, depth, fetcher)
    ch <- 1
}

第一个是,根据对应urls数量开启配置信道缓冲区大小。
通过for循环urls数量,实现并行协程处理,然后重点来了,从信道缓冲区,接受协程发送过来的数据。
第二个,在私有函数crawl,注意,调用完抓取函数Crawl后,需要关闭信道。

细节

一级URL 标题 内容里的二级URL
https://golang.org/ “The Go Programming Language” "https://golang.org/pkg/","https://golang.org/cmd/"
https://golang.org/pkg/ “Packages” "https://golang.org/","https://golang.org/cmd/","https://golang.org/pkg/fmt/","https://golang.org/pkg/os/",
https://golang.org/pkg/fmt/ “Package fmt” "https://golang.org/","https://golang.org/pkg/",
https://golang.org/pkg/os/ “Package os” "https://golang.org/","https://golang.org/pkg/",

实现代码

GitHub

参考链接

  1. 练习:Web 爬虫
  2. GO指南 练习:Web爬虫
  3. 学习一下golang 练习70 web crawler

练习 等价二叉查找树

问题

不同二叉树的叶节点上可以保存相同的值序列。例如,以下两个二叉树都保存了序列 `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 的文档可在[这里](https://godoc.org/golang.org/x/tour/tree#Tree)找到。

背景知识

  1. 你需要了解什么是等价二叉树?
  2. 阅读Tree类型的Go实现源代码。代码实现了3个函数,New函数新建二叉树,insert函数插入新元素,实现了打印字符串String接口
  3. 了解协程,信道的实现原理。
  4. 判断等价二叉树相等的话,那么左右节点的值都需要相等。

实现思路

  1. 实现 Walk 函数,循环通过信道发送数据,然后接受并输出。Walk的遍历方式为中序遍历,先遍历根节点,然后左节点,最后右节点。
  2. 注意tree的遍历方式,也就是获得值的方式,实现一个私有的walk函数,签名和Walk一致,因为Tree类型较为简单,并不能直接判断循环的结束。故采用这样的方式,循环遍历到最后,t == nil时,关闭信道,不然会报错的。
  3. 实现 Same 函数,循环判断tree每一个值是否相等。难点在于,创建2个信道,去读取Walk返回的Tree的节点值。

实现代码

GitHub

参考链接

  1. 练习:等价二叉查找树
  2. 二叉查找树
  3. Go指南练习之《等价二叉树》(Equivalent Binary Trees)

练习 图像

问题

还记得之前编写的图片生成器吗?我们再来编写另外一个,不过这次它将会返回一个 image.Image 的实现而非一个数据切片。

定义你自己的 Image 类型,实现必要的方法并调用 pic.ShowImage。

Bounds 应当返回一个 image.Rectangle ,例如 image.Rect(0, 0, w, h)。

ColorModel 应当返回 color.RGBAModel。

At 应当返回一个颜色。上一个图片生成器的值 v 对应于此次的 color.RGBA{v, v, 255, 255}。

背景知识

这一次,我们需要更多的接口具体实现细节了。

1. 什么是图片生成器?
func main() {
    m := image.NewRGBA(image.Rect(0, 0, 100, 100))
    fmt.Println(m.Bounds())
    fmt.Println(m.At(0, 0).RGBA())
}

image接口类型
type Image interface {
    ColorModel() color.Model
    Bounds() Rectangle
    At(x, y int) color.Color
}

NewRGBA函数
func NewRGBA(r Rectangle) *RGBA {
    w, h := r.Dx(), r.Dy()
    buf := make([]uint8, 4*w*h)
    return &RGBA{buf, 4 * w, r}
}

2. 查看image包的源代码以及image/color的源代码。

实现思路

  1. 需要实现Image类型的三个指定接口。
  2. 第一个接口直接返回color.RGBAModel
  3. 第二个接口,需要初始化部分变量。
  4. 第三个接口,部分变量做算法计算,赋值给color.RGBA

实现代码

GitHub

参考链接

  1. 练习:图像