092017
 

排序算法是一种采用列表或数组并以特定顺序对其元素进行重新排序的算法。有几十种不同的排序算法,如果你已经学习了计算机科学,那么你至少熟悉了其中的一些算法。 它们也是很受欢迎的面试问题,所以在重要面试前不要因为它而伤心。

这是一个大多数常见的排序算法的小型引擎,实例采用 Golang 实现。

冒泡排序

冒泡排序是最基本的就地排序算法,几乎每个人都很熟悉。 它具有 O(n²) 最坏情况和平均时间复杂度,这使得它在大型列表中效率低下。它的实现非常简单。

在循环中,从第一个元素到第 n 个(n = len(items))迭代数组。比较相邻的值,如果它们的顺序错误,交换它们。 您可以通过在每次迭代后将 n 递减 1 来优化算法。

时间复杂度:

* 最坏情况下:O(n²)
* 平均情况下:O(n²)
* 最好情况下:O(n)

空间复杂度:

* 最坏情况下:O(1)

package main

import (
    "fmt"
)

func main() {
    items := []int{4, 202, 3, 9, 6, 5, 1, 43, 506, 2, 0, 8, 7, 100, 25, 4, 5, 97, 1000, 27}
    bubbleSort(items)
    fmt.Println(items)
}

func bubbleSort(items []int) {
    var (
        n       = len(items)
        swapped = true
    )
    for swapped {
        swapped = false
        for i := 0; i < n-1; i++ {
            if items[i] > items[i+1] {
                items[i+1], items[i] = items[i], items[i+1]
                swapped = true
            }
        }
        n = n - 1
    }
}

选择排序

选择排序是另一种简单的平均情况 O(n²) 就地分拣算法。该算法将列表分为两个子列表,一个用于已排序的列表,该列表开始为空,并从列表的开头从左到右构建,第二个子列表用于剩余的未排序的元素。

选择排序可以通过两个嵌套 for 循环来实现。外部循环遍历列表 n 次(n = len(items))。内部循环将始终以外部循环的当前迭代器值开始(因此在每个迭代中,它将从列表中的更右侧的位置开始),并找出子列表的最小值。使用找到的最小值交换子列表的第一项。

时间复杂度:

* 最坏情况下:O(n²)
* 平均情况下:O(n²)
* 最好情况下:O(n²)

空间复杂度:

* 最坏情况下:O(1)

package main

import (
    "fmt"
)

func main() {
    items := []int{4, 202, 3, 9, 6, 5, 1, 43, 506, 2, 0, 8, 7, 100, 25, 4, 5, 97, 1000, 27}
    selectionSort(items)
    fmt.Println(items)
}

func selectionSort(items []int) {
    var n = len(items)
    for i := 0; i < n; i++ {
        var minIdx = i
        for j := i; j < n; j++ {
            if items[j] < items[minIdx] {
                minIdx = j
            }
        }
        items[i], items[minIdx] = items[minIdx], items[i]
    }
}

插入排序

插入排序是简单的就地 O(n²) 排序算法。同样,它在大型列表中效率较低,但它具有很少有的优点:

* 自适应:时间复杂度随着已经基本排序的列表而减少 – 如果每个元素不超过其最终排序位置的 k 个位置,则 O(nk)
* 稳定:相等值的索引的相对位置不变
* 就地:只需要一个常数 O(1) 的额外的内存空间
* 在实践中比泡沫或选择排序更有效

时间复杂度:

* 最坏情况下:O(n²)
* 平均情况下:O(n²)
* 最好情况下:O(n)

空间复杂度:

* 最坏情况下:O(1)

实现是非常自然的,因为它的工作方式类似于你如何排序手中的排,如果你正在玩一个纸牌游戏。

package main

import (
    "fmt"
)

func main() {
    items := []int{4, 202, 3, 9, 6, 5, 1, 43, 506, 2, 0, 8, 7, 100, 25, 4, 5, 97, 1000, 27}
    insertionSort(items)
    fmt.Println(items)
}

func insertionSort(items []int) {
    var n = len(items)
    for i := 1; i < n; i++ {
        j := i
        for j > 0 {
            if items[j-1] > items[j] {
                items[j-1], items[j] = items[j], items[j-1]
            }
            j = j - 1
        }
    }
}

希尔排序(shell sort)

希尔排序是插入排序的泛化。这是一个有趣的排序算法,通过将列表排列成一组交错排序的子列表来工作。

首先,选择一连串的间隙。有许多不同的公式来产生间隙序列,算法的平均时间复杂度取决于这个变量。例如,我们选择 (2 ^ k ) – 1,前缀为1,这将给我们[1,3,7,15,31,63 ...]。 反转顺序:[...,63,31,15,7,3,q]。

现在遍历颠倒的间隙列表,并在每个子列表中使用插入排序。所以在第一次迭代中,每第63个元素都应用插入排序。在第二次迭代中,每31个元素应用插入排序。所以一路下来到1。最后一次迭代将在整个列表中运行插入。

时间复杂度:

* 最坏情况下:O(n(log(n))²)
* 平均情况下:依赖于间隙序列
* 最好情况下:O(n(log(n)))

空间复杂度:

* 最坏情况下:O(1)

package main

import (
    "fmt"
)

func main() {
    items := []int{4, 202, 3, 9, 6, 5, 1, 43, 506, 2, 0, 8, 7, 100, 25, 4, 5, 97, 1000, 27}
    shellshort(items)
    fmt.Println(items)
}

func shellshort(items []int) {
    var (
        n    = len(items)
        gaps = []int{1}
        k    = 1
    )

    for {
        gap := pow(2, k) + 1
        if gap > n-1 {
            break
        }
        gaps = append([]int{gap}, gaps...)
        k++
    }
    for _, gap := range gaps {
        for i := gap; i < n; i += gap {
            j := i
            for j > 0 {
                if items[j-gap] > items[j] {
                    items[j-gap], items[j] = items[j], items[j-gap]
                }
                j = j - gap
            }
        }
    }
}

func pow(a, b int) int {
    p := 1
    for b > 0 {
        if b&1 != 0 {
            p *= a
        }
        b >>= 1
        a *= a
    }
    return p
}

梳排序

梳排序是冒泡排序算法的改进。虽然冒泡排序总是比较相邻元素(gap = 1),梳排序以 gap = n/1.3 开始,其中 n = len(items),并在每次迭代时缩小 1.3 倍。

这种改进背后的想法是消除所谓的海龟(靠近列表末尾的小值)。最后的迭代与 gap = 1 的简单冒泡排序相同。

时间复杂度:

* 最坏情况下:O(n²)
* 平均情况下:O(n²/2^p) (p 是增量的数量)
* 最好情况下:O(n(log(n)))

空间复杂度:

* 最坏情况下:O(1)

package main

import (
    "fmt"
)

func main() {
    items := []int{4, 202, 3, 9, 6, 5, 1, 43, 506, 2, 0, 8, 7, 100, 25, 4, 5, 97, 1000, 27}
    combsort(items)
    fmt.Println(items)
}

func combsort(items []int) {
    var (
        n       = len(items)
        gap     = len(items)
        shrink  = 1.3
        swapped = true
    )

    for swapped {
        swapped = false
        gap = int(float64(gap) / shrink)
        if gap < 1 {
            gap = 1
        }
        for i := 0; i+gap < n; i++ {
            if items[i] > items[i+gap] {
                items[i+gap], items[i] = items[i], items[i+gap]
                swapped = true
            }
        }
    }
}

归并排序

归并排序是一种非常有效的通用排序算法。这是分治算法的典型应用,这意味着列表被递归地分解成更小的列表,这些列表被排序然后被递归地组合以形成完整的列表。

来自维基百科:在概念上,合并排序的工作方式如下:
1.将未排序的列表划分为n个子列表,每个子列表包含1个元素(1个元素的列表被视为排序)。
2.重复合并子列表以生成新的排序子列表,直到只剩下1个子列表。 这将是排序列表。

时间复杂度:

* 最坏情况下:O(n(log(n)))
* 平均情况下:O(n(log(n)))
* 最好情况下:O(n(log(n)))

空间复杂度:

* 最坏情况下:O(n)

package main

import (
    "fmt"
)

func main() {
    items := []int{4, 202, 3, 9, 6, 5, 1, 43, 506, 2, 0, 8, 7, 100, 25, 4, 5, 97, 1000, 27}
    sortedItems := mergeSort(items)
    fmt.Println(sortedItems)
}

func mergeSort(items []int) []int {
    var n = len(items)

    if n == 1 {
        return items
    }

    middle := int(n / 2)
    var (
        left  = make([]int, middle)
        right = make([]int, n-middle)
    )
    for i := 0; i < n; i++ {
        if i < middle {
            left[i] = items[i]
        } else {
            right[i-middle] = items[i]
        }
    }

    return merge(mergeSort(left), mergeSort(right))
}

func merge(left, right []int) (result []int) {
    result = make([]int, len(left)+len(right))

    i := 0
    for len(left) > 0 && len(right) > 0 {
        if left[0] < right[0] {
            result[i] = left[0]
            left = left[1:]
        } else {
            result[i] = right[0]
            right = right[1:]
        }
        i++
    }

    // Either left or right may have elements left; consume them.
    // (Only one of the following loops will actually be entered.)
    for j := 0; j < len(left); j++ {
        result[i] = left[j]
        i++
    }
    for j := 0; j < len(right); j++ {
        result[i] = right[j]
        i++
    }

    return
}
202017
 

静态站点生成器是一种工具,给一些输入(例如,markdown),使用HTML,CSS和JavaScript生成完全静态的网站。

为什么这很酷?一般来说,搭建一个静态网站更容易,而且通常运行也会比较快一些,同时占用资源也更少。虽然静态网站不是所有场景的最佳选择,但是对于大多数非交互型网站(如博客)来说,它们是非常好的。

在这篇文章中,我将讲述我用Go写的静态博客生成器。

动机

您可能熟悉静态站点生成器,比如伟大的Hugo,它具有关于静态站点生成的所有功能。

那么为什么我还要来编写另外一个功能较少的类似工具呢? 原因是双重的。

一个原因是我想深入了解Go,一个基于命令行的静态站点生成器似乎是磨练我技能很好的方式。

第二个原因就是我从来没有这样做过。 我已经完成了平常的Web开发工作,但是我从未创建过一个静态站点生成器。

这听起来很有趣,因为理论上,从我的网站开发背景来看,我满足所有先决条件和技能来构建这样一个工具,,但我从来没有尝试过这样做。

大约2个星期,我实现了它,并且很享受做的过程。 我使用我的博客生成器创建我的博客,迄今为止,它运行良好。

概念

早些时候,我决定采用 markdown 格式写博客,同时保存在 GitHub Repo。这些文章是以文件夹的形式组织的,它们代表博客文章的网址。

对于元数据,如发布日期,标签,标题和副标题,我决定保存在每篇文章的(post.md) meta.yml 文件中,它具有以下格式:

标题:玩BoltDB
简介:“为你的 Go 应用程序寻找一个简单的 key/value 存储器吗?看它足够了!
日期:20.04.2017
标签:
- golang
- go
- boltdb
- bolt

这样,我将内容与元数据分开了,但稍后会发现,其实仍然是将所有内容都放在了同一个地方。

GitHub Repo 是我的数据源。下一步是想功能,我想出了如下功能列表:

* 非常精益(在 gzipped 压缩情况下,入口页1请求应<10K)
* 列表存档
* 在博客文章中使用代码语法高亮和和图像
* tags
* RSS feed(index.xml)
* 可选静态页面(例如 About)
* 高可维护性 – 使用尽可能少的模板
* 针对 SEO 的 sitemap.xml
* 整个博客的本地预览(一个简单的 run.sh 脚本)

相当健康的功能集。 从一开始,对我来说非常重要的是保持一切简单,快速和干净 – 没有任何第三方跟踪器或广告,因为这会影响隐私,并会影响速度。

基于这些想法,我开始制定一个粗略的架构计划并开始编码。

架构概述

应用程序足够简单 高层次的要素有:

* 命令行工具(CLI)
* 数据源(DataSource)
* 生成器(Generators)

在这种场景下,CLI 非常简单,因为我没有在可配置性方面添加任何功能。它基本上只是从DataSource 获取数据,并在其上运行 Generator。

DataSource 接口如下所示:

type DataSource interface {
    Fetch(from, to string) ([]string, error)
}

Generator 接口如下所示:

type Generator interface {
    Generate() error
}

很简单。每个生成器还接收一个配置结构,其中包含生成器所需的所有必要数据。

目前已有 7 个生成器:

* SiteGenerator
* ListingGenerator
* PostGenerator
* RSSGenerator
* SitemapGenerator
* StaticsGenerator
* TagsGenerator

SiteGenerator 是元生成器,它调用所有其他生成器并输出整个静态网站。

目前版本是基于 HTML 模板的,使用的是 Go 的 html/template 包。

实现细节

在本节中,我将只介绍几个有觉得有意思的部分,例如 git DataSource 和不同的 Generators。

数据源

首先,我们需要一些数据来生成我们的博客。如上所述,这些数据存储在 git 仓库。 以下 Fetch 函数涵盖了 DataSource 实现的大部分内容:

func (ds *GitDataSource) Fetch(from, to string) ([]string, error) {
    fmt.Printf("Fetching data from %s into %s...\n", from, to)
    if err := createFolderIfNotExist(to); err != nil {
        return nil, err
    }
    if err := clearFolder(to); err != nil {
        return nil, err
    }
    if err := cloneRepo(to, from); err != nil {
        return nil, err
    }
    dirs, err := getContentFolders(to)
    if err != nil {
        return nil, err
    }
    fmt.Print("Fetching complete.\n")
    return dirs, nil
}

使用两个参数调用 Fetch,from 是一个仓库 URL,to 是目标文件夹。 该函数创建并清除目标文件夹,使用 os/exec 加上 git 命令克隆仓库,最后读取文件夹,返回仓库中所有文件的路径列表。

如上所述,仓库仅包含表示不同博客文章的文件夹。 然后将具有这些文件夹路径的数组传递给生成器,它可以为仓库中的每个博客文章执行其相应的操作。

拉开帷幕

Fetch 之后,就是 Generate 阶段。执行博客生成器时,最高层执行以下代码:

ds := datasource.New()
dirs, err := ds.Fetch(RepoURL, TmpFolder)
if err != nil {
    log.Fatal(err)
}
g := generator.New(&generator.SiteConfig{
    Sources:     dirs,
    Destination: DestFolder,
})
err = g.Generate()
if err != nil {
    log.Fatal(err)
}

generator.New 函数创建一个新的 SiteGenerator,这是一个基础生成器,它会调用其他生成器。这里我们提供了仓库中的博客文章目录(数据源)和目标文件夹。

由于每个生成器都实现了上述接口的 Generator,因此 SiteGenerator 有一个 Generate 方法,它返回 error。 SiteGenerator 的 Generate 方法准备目标文件夹,读取模板,准备博客文章的数据结构,注册其他生成器并并发的运行它们。

SiteGenerator 还为博客注册了一些设置信息,如URL,语言,日期格式等。这些设置只是全局常量,这当然不是最漂亮的解决方案,也不是最具可伸缩性的,但很简单,这也是我最高的目标。

文章

博客中最重要的概念是 – 惊喜,惊喜 – 博客文章! 在这个博客生成器的上下文中,它们由以下数据结构表示:

type Post struct {
    Name      string
    HTML      []byte
    Meta      *Meta
    ImagesDir string
    Images    []string
}

这些文章是通过遍历仓库中的文件夹,读取 meta.yml 文件,将 post.md 文件转换为 HTML 并添加图像(如果有的话)创建的。

相当多的工作,但是一旦我们将文章表示为一个数据结构,那么生成文章就会很简单,看起来像这样:

func (g *PostGenerator) Generate() error {
    post := g.Config.Post
    destination := g.Config.Destination
    t := g.Config.Template
    staticPath := fmt.Sprintf("%s%s", destination, post.Name)
    if err := os.Mkdir(staticPath, os.ModePerm); err != nil {
      return fmt.Errorf("error creating directory at %s: %v", staticPath, err)
    }
    if post.ImagesDir != "" {
      if err := copyImagesDir(post.ImagesDir, staticPath); err != nil {
          return err
      }
    }
    if err := writeIndexHTML(staticPath, post.Meta.Title, template.HTML(string(post.HTML)), t); err != nil {
      return err
    }
    return nil
}

首先,我们为该文章创建一个目录,然后我们复制图像,最后使用模板创建该文章的 index.html 文件。

列表创建

当用户访问博客的着陆页时,她会看到最新的文章,其中包含文章的阅读时间和简短描述等信息。 对于此功能和归档,我实现了ListingGenerator,它使用以下配置:

type ListingConfig struct {
    Posts                  []*Post
    Template               *template.Template
    Destination, PageTitle string
}

该生成器的 Generate 方法遍历该文章,组装其元数据,并根据给定的模板创建概要。 然后这些块被附加并写入相应的 index 模板。

我喜欢一个媒体的功能:文章大概阅读时间,所以我实现了我自己的版本,基于一个普通人每分钟读取大约 200 个字的假设。 图像也计入整体阅读时间,并为该帖子中的每个 img 标签添加了一个常量 12 秒。这显然不会对任意内容进行扩展,但对于我惯常的文章应该是一个很好的近似值:

func calculateTimeToRead(input string) string {
    // an average human reads about 200 wpm
    var secondsPerWord = 60.0 / 200.0
    // multiply with the amount of words
    words := secondsPerWord * float64(len(strings.Split(input, " ")))
    // add 12 seconds for each image
    images := 12.0 * strings.Count(input, "<img")
    result := (words + float64(images)) / 60.0
    if result < 1.0 {
        result = 1.0
    }
    return fmt.Sprintf("%.0fm", result)
}

Tags

接下来,要有一种按主题归类和过滤文章的方法,我选择实现一个简单的 tag(标签) 机制。 文章在他们的 meta.yml 文件中有一个标签列表。这些标签应该列在单独的标签页上,并且点击标签后,用户应该看到带有所选标签的文章列表。

首先,我们创建一个从 tag 到 Post 的 map:

func createTagPostsMap(posts []*Post) map[string][]*Post {
result := make(map[string][]*Post)
    for _, post := range posts {
        for _, tag := range post.Meta.Tags {
            key := strings.ToLower(tag)
             if result[key] == nil {
                 result[key] = []*Post{post}
             } else {
                 result[key] = append(result[key], post)
             }
        }
    }
    return result
}

接着有两项任务要实现:

* 标签页
* 所选标签的文章列表

标签(Tag)的数据结构如下所示:

type Tag struct {
    Name  string
    Link  string
    Count int
}

所以,我们有实际的标签(名称),链接到标签的列表页面和使用此标签的文章数量。这些标签是从 tagPostsMap 创建的,然后按 Count 降序排序。

tags := []*Tag{}
for tag, posts := range tagPostsMap {
    tags = append(tags, &Tag{Name: tag, Link: getTagLink(tag), Count: len(posts)})
}
sort.Sort(ByCountDesc(tags))

标签页基本上只是包含在 tags/index.html 文件中的列表。

所选标签的文章列表可以使用上述的 ListingGenerator 来实现。 我们只需要迭代标签,为每个标签创建一个文件夹,选择要显示的帖子并为它们生成一个列表。

Sitemap 和 RSS

为了提高网络的可搜索性,最好建立一个可以由机器人爬取的 sitemap.xml。创建这样的文件是非常简单的,可以使用 Go 标准库来完成。

然而,在这个工具中,我选择使用了 etree 库,它为创建和读取 XML 提供了一个很好的 API。

SitemapGenerator 使用如下配置:

type SitemapConfig struct {
    Posts       []*Post
    TagPostsMap map[string][]*Post
    Destination string
}

博客生成器采用基本的方法来处理 sitemap,只需使用 addURL 函数生成 URL 和图像。

func addURL(element *etree.Element, location string, images []string) {
    url := element.CreateElement("url")
     loc := url.CreateElement("loc")
     loc.SetText(fmt.Sprintf("%s/%s/", blogURL, location))

     if len(images) > 0 {
         for _, image := range images {
            img := url.CreateElement("image:image")
             imgLoc := img.CreateElement("image:loc")
             imgLoc.SetText(fmt.Sprintf("%s/%s/images/%s", blogURL, location, image))
         }
     }
}

在使用 etree 创建XML文档之后,它将被保存到文件并存储在输出文件夹中。

RSS 生成工作方式相同 – 迭代所有文章并为每个文章创建 XML 条目,然后写入 index.xml。

处理静态资源

最后一个概念是静态资源,如 favicon.ico 或静态页面,如 About。 为此,该工具将使用下面配置运行 StaticsGenerator:

type StaticsConfig struct {
    FileToDestination map[string]string
    TemplateToFile    map[string]string
    Template          *template.Template
}

FileToDestination-map 表示静态文件,如图像或 robots.txt,TemplateToFile是从静态文件夹中的模板到其指定的输出路径的映射。

这种配置可能看起来像这样:

fileToDestination := map[string]string{
    "static/favicon.ico": fmt.Sprintf("%s/favicon.ico", destination),
    "static/robots.txt":  fmt.Sprintf("%s/robots.txt", destination),
    "static/about.png":   fmt.Sprintf("%s/about.png", destination),
}
templateToFile := map[string]string{
    "static/about.html": fmt.Sprintf("%s/about/index.html", destination),
}
statg := StaticsGenerator{&StaticsConfig{
FileToDestination: fileToDestination,
   TemplateToFile:    templateToFile,
   Template:          t,
}}

用于生成这些静态资源的代码并不是特别有趣 – 您可以想像,这些文件只是遍历并复制到给定的目标。

并行执行

为了使博客生成器运行更快,所有生成器应该并行执行。正因为此,它们都遵循 Generator 接口, 这样我们可以将它们全部放在一个 slice 中,并发地调用 Generate。

这些生成器都可以彼此独立工作,不使用任何全局可变状态,因此使用 channel 和 sync.WaitGroup 可以很容易的并发执行它们。

func runTasks(posts []*Post, t *template.Template, destination string) error {
    var wg sync.WaitGroup
    finished := make(chan bool, 1)
    errors := make(chan error, 1)
    pool := make(chan struct{}, 50)
    generators := []Generator{}

    for _, post := range posts {
        pg := PostGenerator{&PostConfig{
            Post:        post,
             Destination: destination,
             Template:    t,
        }}
        generators = append(generators, &pg)
    }

    fg := ListingGenerator{&ListingConfig{
        Posts:       posts[:getNumOfPagesOnFrontpage(posts)],
        Template:    t,
        Destination: destination,
        PageTitle:   "",
    }}

    …创建其他的生成器...

    generators = append(generators, &fg, &ag, &tg, &sg, &rg, &statg)

    for _, generator := range generators {
        wg.Add(1)
        go func(g Generator) {
            defer wg.Done()
            pool <- struct{}{}
            defer func() { <-pool }()
            if err := g.Generate(); err != nil {
                errors <- err
            }
        }(generator)
    }

    go func() {
        wg.Wait()
        close(finished)
    }()

    select {
    case <-finished:
        return nil
    case err := <-errors:
        if err != nil {
           return err
        }
    }
    return nil
}

runTasks 函数使用带缓冲的 channel,限制最多只能开启50个 goroutines,来创建所有生成器,将它们添加到一个 slice 中,然后并发运行。

这些例子只是在 Go 中编写静态站点生成器的基本概念的一个很短的片段。

如果您对完整的实现感兴趣,可以在此处找到代码

总结

写个人博客生成器是绝对的爆炸和伟大的学习实践。 使用我自己的工具创建我的博客也是非常令人满意的。

为了发布我的文章到 AWS,我还创建了 static-aws-deploy,这是另一个 Go命令行工具。

如果你想自己使用这个工具,只需要 fork repo 并更改配置。 但是,由于 Hugo 提供了所有这些和更多的功能,我没有花太多时间进行可定制性或可配置性。

当然,应该不要一直重新发明轮子,但是有时重新发明一两轮可能是有益的,可以帮助你在这个过程中学到很多东西。:)

英文原文

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 中获取。