062015
 

做过 Web 开发的,应该都用过或听过 jQuery,它提供了方便的操作 DOM 的 API。使用 Go 语言做服务器端开发,有时候需要解析 HTML 文件,比如抓取网站内容、写一个爬虫等。这时候如果有一个类似 jQuery 的库可以使用,操作 DOM 会很方便,而且,上手也会很快。github.com/PuerkitoBio/goquery 这个库就实现了类似 jQuery 的功能,让你能方便的使用 Go 语言操作 HTML 文档。

1 概述

Go 实现了类似 jQuery 的功能,包括链式操作语法、操作和查询 HTML 文档。它基于 Go net/html 包和 CSS 选择器库 cascadia。由于 net/html 解析器返回的是 DOM 节点,而不是完整的 DOM 树,因此,jQuery 的状态操作函数没有实现(像 height(),css(),detach())。

由于 net/html 解析器要求文档必须是 UTF-8 编码,因此 goquery 库也有此要求。如果文档不是 UTF-8 编码,使用者需要自己转换。进行编码转换,可以使用如下库:
iconv 的 Go 封装,如:github.com/djimenez/iconv-go
官方提供的 text 子仓库,text/encoding,用于其他编码和 UTF-8 之间进行转换

除了实现和 jQuery 类似的功能外,在函数名方面,也尽量和 jQuery 保持一致,也支持链式语法。

2 goquery 提供的主要类型和方法

2.1 Document

Document 代表一个将要被操作的 HTML 文档,不过,和 jQuery 不同,它装载的是 DOM 文档的一部分。

type Document struct {
	*Selection
	Url *url.URL
	rootNode *html.Node // 文档的根节点
}

因为 Document 中内嵌了一个 Selection 类型,因此,Document 可以直接使用 Selection 类型的方法。

有五种方法获取一个 Document 实例,分别是从一个 URL 创建、从一个 *html.Node 创建、从一个 io.Reader 创建、从一个 *http.Response 创建和从一个已有的 Document Clone 一个。

2.2 Selection

Selection 代表符合特定条件的节点集合。

type Selection struct {
	Nodes []*html.Node
	document *Document
	prevSel *Selection
}

一般地,得到了 Document 实例后,通过 Dcoument.Find 方法获取一个 Selection 实例,然后像 jQuery 一样使用链式语法和方法操作它。

Selection 类型提供的方法可以分为如下几大类(注意,3个点(…)表示有重载的方法):

1)类似函数的位置操作

- Eq()
- First()
- Get()
- Index…()
- Last()
- Slice()

2)扩大 Selection 集合(增加选择的节点)

- Add…()
- AndSelf()
- Union(), which is an alias for AddSelection()

3)过滤方法,减少节点集合

- End()
- Filter…()
- Has…()
- Intersection(), which is an alias of FilterSelection()
- Not…()

4)循环遍历选择的节点

- Each()
- EachWithBreak()
- Map()

5)修改文档

- After…()
- Append…()
- Before…()
- Clone()
- Empty()
- Prepend…()
- Remove…()
- ReplaceWith…()
- Unwrap()
- Wrap…()
- WrapAll…()
- WrapInner…()

6)检测或获取节点属性值

- Attr(), RemoveAttr(), SetAttr()
- AddClass(), HasClass(), RemoveClass(), ToggleClass()
- Html()
- Length()
- Size(), which is an alias for Length()
- Text()

7)查询或显示一个节点的身份

- Contains()
- Is…()

8)在文档树之间来回跳转(常用的查找节点方法)

- Children…()
- Contents()
- Find…()
- Next…()
- Parent[s]…()
- Prev…()
- Siblings…()

2.3 Matcher 接口

该接口定义了一些方法,用于匹配 HTML 节点和编译过的选择器字符串。Cascadia’s Selector 实现了该接口。

type Matcher interface {
	Match(*html.Node) bool
	MatchAll(*html.Node) []*html.Node
	Filter([]*html.Node) []*html.Node
}

3 实战演练

该库提供的类型很少,但方法却很多,我们不可能一个个方法讲解。这里通过模拟几个使用场景来讲解该库的使用。

3.1 抓取 Go语言中文网 社区主题 — http://studygolang.com/topics

查看页面 HTML 结构后,就跟使用 jQuery 操作页面一样。这个例子,我们获取社区主题的标题列表。

主要代码如下(为了节省篇幅,包导入等语句省略,完整代码,参见文章最后说明):

func main() {
	doc, err := goquery.NewDocument("http://studygolang.com/topics")
	if err != nil {
		log.Fatal(err)
	}

	doc.Find(".topics .topic").Each(func(i int, contentSelection *goquery.Selection) {
		title := contentSelection.Find(".title a").Text()
		log.Println("第", i+1, "个帖子的标题:", title)
	})
}

编译、运行输出如下(你看到的内容和当时社区的主题列表一致):

2015/04/06 22:15:24 第 1 个帖子的标题: 问个加载包的问题
2015/04/06 22:15:24 第 2 个帖子的标题: Tango v0.4版本发布,带来统一高性能的新路由
2015/04/06 22:15:24 第 3 个帖子的标题: 创业团队缺后端开发
2015/04/06 22:15:24 第 4 个帖子的标题: 自由是创造力和灵感的催化剂,需要golang后端开发人员
2015/04/06 22:15:24 第 5 个帖子的标题: cgo编译出来的文件怎么用?
2015/04/06 22:15:24 第 6 个帖子的标题: cgo编译问题,Undefined symbols
2015/04/06 22:15:24 第 7 个帖子的标题: 北京 GO 研发程序员,全职,20K+
2015/04/06 22:15:24 第 8 个帖子的标题: Go 1.5 计划启动,使用 Go 来编译 Go
2015/04/06 22:15:24 第 9 个帖子的标题: beego.Error 原理
2015/04/06 22:15:24 第 10 个帖子的标题: 插入数据库操作测试 1分钟一百万条数据 这数据怎么样?
2015/04/06 22:15:24 第 11 个帖子的标题: Go最新资料汇总(十一)
2015/04/06 22:15:24 第 12 个帖子的标题: Azul3D_Go开发的3D游戏引擎简介
2015/04/06 22:15:24 第 13 个帖子的标题: Golang中goroutine线程何时终止问题
2015/04/06 22:15:24 第 14 个帖子的标题: 标准库中文版的testing是不是打不开了?
2015/04/06 22:15:24 第 15 个帖子的标题: 如何使用cgo编译出来的文件

是不是很简单?

这里我们使用了 Each 这个方法。在 jQuery 中,each 迭代时,如果返回 false,可以终止迭代。比如,我们希望遇到标题中包含 cgo 的主题时,停止迭代,可以使用 EachWithBreak(之所以没有使用 Each,是因为迭代终止的功能是后来加入的,为了不改变 Each 的行为,保持兼容性,引入了该方法):

doc.Find(".topics .topic").EachWithBreak(func(i int, contentSelection *goquery.Selection) bool {
	title := contentSelection.Find(".title a").Text()
	log.Println("第", i+1, "个帖子的标题:", title)
	if strings.Contains(title, "cgo") {
		return false
	}
	return true
})

从上面的输出可以看到,Each 遍历是按照页面节点的顺序的。如果我们希望反着处理,也就是先处理页面最底下的节点。查看文档,发现没有直接提供这样的方法。那么该怎么实现呢?

topicsSelection := doc.Find(".topics .topic")

for i := topicsSelection.Length() - 1; i >= 0; i-- {
	// 返回的是 *html.Node
	topicNode := topicsSelection.Get(i)
	title := goquery.NewDocumentFromNode(topicNode).Find(".title a").Text()
	log.Println("第", i+1, "个帖子的标题:", title)
}

这里用到了 NewDocumentFromNode,把其中某一块 HTML 当做文档,对其进行操作。

输出如下:

2015/04/06 22:50:28 第 15 个帖子的标题: 如何使用cgo编译出来的文件
2015/04/06 22:50:28 第 14 个帖子的标题: 标准库中文版的testing是不是打不开了?
2015/04/06 22:50:28 第 13 个帖子的标题: Golang中goroutine线程何时终止问题
2015/04/06 22:50:28 第 12 个帖子的标题: Azul3D_Go开发的3D游戏引擎简介
2015/04/06 22:50:28 第 11 个帖子的标题: Go最新资料汇总(十一)
2015/04/06 22:50:28 第 10 个帖子的标题: 插入数据库操作测试 1分钟一百万条数据 这数据怎么样?
2015/04/06 22:50:28 第 9 个帖子的标题: beego.Error 原理
2015/04/06 22:50:28 第 8 个帖子的标题: Go 1.5 计划启动,使用 Go 来编译 Go
2015/04/06 22:50:28 第 7 个帖子的标题: 北京 GO 研发程序员,全职,20K+
2015/04/06 22:50:28 第 6 个帖子的标题: cgo编译问题,Undefined symbols
2015/04/06 22:50:28 第 5 个帖子的标题: cgo编译出来的文件怎么用?
2015/04/06 22:50:28 第 4 个帖子的标题: 自由是创造力和灵感的催化剂,需要golang后端开发人员
2015/04/06 22:50:28 第 3 个帖子的标题: 创业团队缺后端开发
2015/04/06 22:50:28 第 2 个帖子的标题: Tango v0.4版本发布,带来统一高性能的新路由
2015/04/06 22:50:28 第 1 个帖子的标题: 问个加载包的问题

除了获取节点的文本内容,还可以获取节点的属性值、判断是否有某个 class 等,gopher 们可以自己试验。

【未完待续。。。】

032014
 

工作中碰到这样一个问题:

有一个文本文件,有上亿行数据,每行数据是 unsigned int。现在需要将其中可能重复的数只保留一个,同时和另外一个或多个这样的文件进行排重(即和它们做差集)。要求尽可能快的筛选出来。

开始实现比较简单粗暴,将数据直接通过 LOAD DATA INFILE 导入 MySQL 表中,然后多表之间做 LEFT JOIN。数据不是特别大,比如几千万,且就要排重的文件不多时,比如一个,速度还可以接受。然而,当数据上亿,且有多个文件需要排重时,性能急剧下降,必须进行优化。而这,正是 Bitmap 的应用场景。

1、Bitmap 概念

Bitmap 是一个十分有用的数据结构。所谓的 Bit-map 就是用一个 bit 位来标记某个元素对应的 Value,而 Key 即是该元素。由于采用了 Bit 为单位来存储数据,因此在内存占用方面,可以大大节省。(《编程珠玑》第一章引入的问题,提到了 Bitmap)

2、Bitmap 的实现原理

以一个简单的数组排序来说明 Bitmap 的实现原理:array[4,6,3,1,7]

Bitmap 采用的是以空间换时间的思想,数组中最大元素值为7,所以在内存中开辟8位的存储空间,存储空间大小的确定方法是(元素最大值进位到8的倍数/8),之所以除以8,是因为开辟空间的时候以byte为单位,1byte=8bit。

开辟8位的空间后,每位初始化为0,如下表:

0号位 1号位 2号位 3号位 4号位 5号位 6号位 7号位
0 0 0 0 0 0 0 0

开始遍历 array 数组,array[0]=4 时,则将 4号位 置1,变为下表:

0号位 1号位 2号位 3号位 4号位 5号位 6号位 7号位
0 0 0 0 1 0 0 0

array[1]=6 时,则将 6号位 置1,变为下表:

0号位 1号位 2号位 3号位 4号位 5号位 6号位 7号位
0 0 0 0 1 0 1 0

直至遍历完 array 数组,空间各位如下表:

0号位 1号位 2号位 3号位 4号位 5号位 6号位 7号位
0 1 0 1 1 0 1 1

最后,从头开始遍历空间中各位,为1的输出其 位号,得:1,3,4,6,7,其效率为O(n)=8

3、Bitmap 编码实现

一般的,静态语言比较容易实现 Bitmap。在下面的实现中,Bitmap 数据结构可以直接定义为 byte 数组,然而,出于使用的方面原因,这里 Bitmap 的实现额外保存了一些其他信息,因此 Go 和 C 中,使用 struct 定义 Bitmap。

从上面的排序例子知道,实现的关键是 置位 和 清位。

3.1 Go 语言实现

Bitmap 数据结构定义如下:

type Bitmap struct {
    // 保存实际的 bit 数据
    data []byte
    // 指示该 Bitmap 的 bit 容量
    bitsize uint64
    // 该 Bitmap 被设置为 1 的最大位置(方便遍历)
    maxpos uint64
}

置位 和 清位 方法:

// SetBit 将 offset 位置的 bit 置为 value (0/1)
func (this *Bitmap) SetBit(offset uint64, value uint8) bool {
     index, pos := offset/8, offset%8

     if this.bitsize < offset {
          return false
     }

     if value == 0 {
          // &^ 清位
          this.data[index] &^= 0x01 << pos
     } else {
          this.data[index] |= 0x01 << pos

          // 记录曾经设置为 1 的最大位置
          if this.maxpos < offset {
               this.maxpos = offset
          }
     }

     return true
}

完整实现代码:Github Bitmap Golang

3.2 C 语言实现

Bitmap 数据结构定义如下:

typedef struct {
     uint64_t bitsize;
     uint64_t maxpos;

     /* 不定长,必须是结构的最后一个成员 */
     uint8_t data[];
} Bitmap;

置位 和 清位 方法:

bool set_bit(Bitmap* bitmap, uint64_t offset, uint8_t value)
{
     uint64_t index, pos;

     index = offset / 8;
     pos = offset % 8;

     if (bitmap->bitsize < offset) {
          return false;
     }

     if (value) {
          bitmap->data[index] |= 1 << pos;

          if (bitmap->maxpos < offset) {
               bitmap->maxpos = offset;
          }
     } else {
          bitmap->data[index] &= BITMAP_MASK ^ (1 << pos);
     }

     return true;
}

相比和 Go 语言版的不同点是,C 没有直接的 清位 操作符

完整实现代码:Github Bitmap C

3.3 Java 语言实现

Bitmap 采用类实现,定义如下成员变量

private byte[] data;

private long bitsize;
private long maxpos;

置位 和 清位 方法:

public boolean setBit(long offset, int value) {
     if (this.bitsize < offset) {
          return false;
     }

     int index = (int) offset / 8;
     int pos = (int) offset % 8;

     if (value == 1) {
          this.data[index] |= 1 << pos;
          if (this.maxpos < offset) {
               this.maxpos = offset;
          }
     } else {
          this.data[index] &= Bitmap.BITMAP_MASK ^ (1 << pos);
     }

     return true;
}

跟 C 语言一样, Java 也没有直接提供 清位 操作符。

完整实现代码:Github Bitmap Java

3.4 三种语言实现的不同点

通过对比三种语言的实现,可以看出一些不同点:

1)数据类型的支持:Go 和 C 可以实现 uint8/uint64,而 Java 不区分是否有符号(Java 8 提供了无符号数);
2)清位操作:Go 提供了清位操作符;而 C 和 Java 需要自己实现,关键点是 0×01 和 MASK 做异或操作;

4、Bitmap 具体实现的关键点

从上面三种语言的具体实现可以看出,Bitmap 实现的关键有如下几点:

1)使用 byte 数组保存数据,这样可以极大的节省内存空间;
2)某个元素(也就是某个位置)要置为0或1,通过对 8 (1byte=8bit) 做除法和取余来实现;
3)具体的置位或清位,使用位操作实现:没有直接提供操作符的,可以通过多种操作符组合实现;

5、Bitmap 更多应用

一般地涉及到无重复、int 类型的问题,可以考虑 Bitmap 是否能够实现。

1)文章开头提到的排重实现(代码见 github 的taskdiff)

2)《编程珠玑》第一章的问题,可以参考《编程珠玑–位图法排序》

3)已知某个文件内包含一些电话号码,每个号码为8位数字,统计不同号码的个数

8位最多99 999 999,大概需要99m个bit,大概10几m字节的内存即可。 (可以理解为从0-99 999 999的数字,每个数字对应一个Bit位,所以只需要99M个Bit==12.5MBytes,这样,就用了小小的12M左右的内存表示了所有的8位数的 电话)

4)2.5亿个整数中找出不重复的整数的个数(内存空间不足以容纳这2.5亿个整数)

将bit-map扩展一下,用2bit表示一个数即可,0表示未出现,1表示出现一次,2表示出现2次及以上,在遍历这些数的时候,如果对应位置的 值是0,则将其置为1;如果是1,将其置为2;如果是2,则保持不变。或者我们不用2bit来进行表示,我们用两个bit-map即可模拟实现这个 2bit-map,都是一样的道理。

6、题外话

用三种语言实现的Bitmap进行排重处理,C 和 Java 版本速度差不多,1.5 亿数据60秒内处理完;而 Go 版本需要 1分50秒 左右(主要 bufio 包性能不太理想);内存占用方面,C 最少,Go 次之,Java 最多。

082014
 

在公司内部,经常会有域名是需要绑定host才能访问的,如果是通过浏览器访问,我们会修改本机的hosts文件;然而,如果是要通过程序访问这样的域名,我们是否依然必须绑定host呢?答案当然是否定的,而且,依赖本地绑定的host,程序到其他机器部署,也必须在那台机器绑定host,如果机器很多呢?

本文示例:
IP:192.168.1.102,也就是说需要访问这台机器上的资源
域名:www.studygolang.com,nginx 配置的虚拟主机
url path:/testhost.txt,内容是:Welcome to studygolang.com

需求:需要请求服务器上的 testhost.txt 资源

1、Linux Shell的解决方案

Linux下的curl程序可以绑定host,因此,在 shell 中可以很简单的实现,如: curl -H “Host:www.studygolang.com” http://192.168.1.102/testhost.txt

2、PHP 的解决方案

1)通过 curl 扩展实现

     $ch = curl_init();
     curl_setopt($ch, CURLOPT_HTTPHEADER, array('Host:www.studygolang.com'));
     curl_setopt($ch, CURLOPT_URL, 'http://192.168.1.102/testhost.txt');
     curl_setopt($ch, CURLOPT_RETURNTRANSFER, 1);
     $ret = curl_exec($ch);
     var_dump($ret);
    

2)不依赖 curl 扩展的方式

     // Create a stream
     $opts = array(
         'http'=>array(
             'method'=>"GET",
             'header'=>"Host:www.studygolang.com"
         )
     );

     $context = stream_context_create($opts);

     // Open the file using the HTTP headers set above
     $ret = file_get_contents('http://192.168.1.102/testhost.txt', false, $context);
     var_dump($ret);
 

3、Golang 的解决方案

由于 Go 标准库实现了 http 协议,在 net/http 包中寻找解决方案。

一般的,请求一个 url,我们通过以下代码实现:

http.Get(url)

然而,针对本文说到的这种情况,无论 url = “http://192.168.1.102/testhost.txt” 还是 url = “http://www.studygolang.com/testhost.txt”,都无法请求到资源(没有绑定 host 的情况)。

在 http 包中的 Request 结构中,有一个字段:Host,我们可以参考上面两种解决方案,设置 Host 的值。方法如下:

     package main

     import (
         "net/http"
         "io/ioutil"
         "fmt"
     )

     func main() {
         req, err := http.NewRequest("GET", "http://192.168.1.102/testhost.txt", nil)
         if err != nil {
             panic(err)
         }
         req.Host = "www.studygolang.com"
         resp, err := http.DefaultClient.Do(req)
         if err != nil {
             panic(err)
         }
         defer resp.Body.Close()
         body, err := ioutil.ReadAll(resp.Body)
         if err != nil {
             panic(err)
         }
         fmt.Println(string(body))
     }

4、总结

不管是什么方式、什么语言,归根结底,需要告知服务器请求的是哪个 Host,这个是 HTTP 协议的 Host 头。如果不手动设置 Host 头,则会从请求的 url 中获取。