Go语言圣经
  • 前言
  • Go语言起源
  • Go语言项目
  • 本书的组织
  • 更多的信息
  • 致谢
  • 入门
    • Hello, World
    • 命令行参数
    • 查找重复的行
    • GIF动画
    • 获取URL
    • 并发获取多个URL
    • Web服务
    • 本章要点
  • 程序结构
    • 命名
    • 声明
    • 变量
    • 赋值
    • 类型
    • 包和文件
    • 作用域
  • 基础数据类型
    • 整型
    • 浮点数
    • 复数
    • 布尔型
    • 字符串
    • 常量
  • 复合数据类型
    • 数组
    • Slice
    • Map
    • 结构体
    • JSON
    • 文本和HTML模板
  • 函数
    • 函数声明
    • 递归
    • 多返回值
    • 错误
    • 函数值
    • 匿名函数
    • 可变参数
    • Deferred函数
    • Panic异常
    • Recover捕获异常
  • 方法
    • 方法声明
    • 基于指针对象的方法
    • 通过嵌入结构体来扩展类型
    • 方法值和方法表达式
    • 示例: Bit数组
    • 封装
  • 接口
    • 接口是合约
    • 接口类型
    • 实现接口的条件
    • flag.Value接口
    • 接口值
    • sort.Interface接口
    • http.Handler接口
    • error接口
    • 示例: 表达式求值
    • 类型断言
    • 基于类型断言识别错误类型
    • 通过类型断言查询接口
    • 类型分支
    • 示例: 基于标记的XML解码
    • 补充几点
  • Goroutines和Channels
    • Goroutines
    • 示例: 并发的Clock服务
    • 示例: 并发的Echo服务
    • Channels
    • 并发的循环
    • 示例: 并发的Web爬虫
    • 基于select的多路复用
    • 示例: 并发的字典遍历
    • 并发的退出
    • 示例: 聊天服务
  • 基于共享变量的并发
    • 竞争条件
    • sync.Mutex互斥锁
    • sync.RWMutex读写锁
    • 内存同步
    • sync.Once初始化
    • 竞争条件检测
    • 示例: 并发的非阻塞缓存
    • Goroutines和线程
  • 包和工具
    • 包简介
    • 导入路径
    • 包声明
    • 导入声明
    • 包的匿名导入
    • 包和命名
    • 工具
  • 测试
    • go test
    • 测试函数
    • 测试覆盖率
    • 基准测试
    • 剖析
    • 示例函数
  • 反射
    • 为何需要反射?
    • reflect.Type和reflect.Value
    • Display递归打印
    • 示例: 编码S表达式
    • 通过reflect.Value修改值
    • 示例: 解码S表达式
    • 获取结构体字段标识
    • 显示一个类型的方法集
    • 几点忠告
  • 底层编程
    • unsafe.Sizeof, Alignof 和 Offsetof
    • unsafe.Pointer
    • 示例: 深度相等判断
    • 通过cgo调用C代码
    • 几点忠告
  • 附录
    • 附录A:原文勘误
    • 附录B:作者译者
    • 附录C:译文授权
    • 附录D:其它语言
Powered by GitBook
On this page

Was this helpful?

  1. 方法

示例: Bit数组

Go语言里的集合一般会用map[T]bool这种形式来表示,T代表元素类型。集合用map类型来表示虽然非常灵活,但我们可以以一种更好的形式来表示它。例如在数据流分析领域,集合元素通常是一个非负整数,集合会包含很多元素,并且集合会经常进行并集、交集操作,这种情况下,bit数组会比map表现更加理想。(译注:这里再补充一个例子,比如我们执行一个http下载任务,把文件按照16kb一块划分为很多块,需要有一个全局变量来标识哪些块下载完成了,这种时候也需要用到bit数组)

一个bit数组通常会用一个无符号数或者称之为“字”的slice或者来表示,每一个元素的每一位都表示集合里的一个值。当集合的第i位被设置时,我们才说这个集合包含元素i。下面的这个程序展示了一个简单的bit数组类型,并且实现了三个函数来对这个bit数组来进行操作:

gopl.io/ch6/intset

// An IntSet is a set of small non-negative integers.
// Its zero value represents the empty set.
type IntSet struct {
    words []uint64
}

// Has reports whether the set contains the non-negative value x.
func (s *IntSet) Has(x int) bool {
    word, bit := x/64, uint(x%64)
    return word < len(s.words) && s.words[word]&(1<<bit) != 0
}

// Add adds the non-negative value x to the set.
func (s *IntSet) Add(x int) {
    word, bit := x/64, uint(x%64)
    for word >= len(s.words) {
        s.words = append(s.words, 0)
    }
    s.words[word] |= 1 << bit
}

// UnionWith sets s to the union of s and t.
func (s *IntSet) UnionWith(t *IntSet) {
    for i, tword := range t.words {
        if i < len(s.words) {
            s.words[i] |= tword
        } else {
            s.words = append(s.words, tword)
        }
    }
}

因为每一个字都有64个二进制位,所以为了定位x的bit位,我们用了x/64的商作为字的下标,并且用x%64得到的值作为这个字内的bit的所在位置。UnionWith这个方法里用到了bit位的“或”逻辑操作符号|来一次完成64个元素的或计算。(在练习6.5中我们还会程序用到这个64位字的例子。)

当前这个实现还缺少了很多必要的特性,我们把其中一些作为练习题列在本小节之后。但是有一个方法如果缺失的话我们的bit数组可能会比较难混:将IntSet作为一个字符串来打印。这里我们来实现它,让我们来给上面的例子添加一个String方法,类似2.5节中做的那样:

// String returns the set as a string of the form "{1 2 3}".
func (s *IntSet) String() string {
    var buf bytes.Buffer
    buf.WriteByte('{')
    for i, word := range s.words {
        if word == 0 {
            continue
        }
        for j := 0; j < 64; j++ {
            if word&(1<<uint(j)) != 0 {
                if buf.Len() > len("{") {
                    buf.WriteByte('}')
                }
                fmt.Fprintf(&buf, "%d", 64*i+j)
            }
        }
    }
    buf.WriteByte('}')
    return buf.String()
}

这里留意一下String方法,是不是和3.5.4节中的intsToString方法很相似;bytes.Buffer在String方法里经常这么用。当你为一个复杂的类型定义了一个String方法时,fmt包就会特殊对待这种类型的值,这样可以让这些类型在打印的时候看起来更加友好,而不是直接打印其原始的值。fmt会直接调用用户定义的String方法。这种机制依赖于接口和类型断言,在第7章中我们会详细介绍。

现在我们就可以在实战中直接用上面定义好的IntSet了:

var x, y IntSet
x.Add(1)
x.Add(144)
x.Add(9)
fmt.Println(x.String()) // "{1 9 144}"

y.Add(9)
y.Add(42)
fmt.Println(y.String()) // "{9 42}"

x.UnionWith(&y)
fmt.Println(x.String()) // "{1 9 42 144}"
fmt.Println(x.Has(9), x.Has(123)) // "true false"

这里要注意:我们声明的String和Has两个方法都是以指针类型*IntSet来作为接收器的,但实际上对于这两个类型来说,把接收器声明为指针类型也没什么必要。不过另外两个函数就不是这样了,因为另外两个函数操作的是s.words对象,如果你不把接收器声明为指针对象,那么实际操作的是拷贝对象,而不是原来的那个对象。因此,因为我们的String方法定义在IntSet指针上,所以当我们的变量是IntSet类型而不是IntSet指针时,可能会有下面这样让人意外的情况:

fmt.Println(&x)         // "{1 9 42 144}"
fmt.Println(x.String()) // "{1 9 42 144}"
fmt.Println(x)          // "{[4398046511618 0 65536]}"

在第一个Println中,我们打印一个*IntSet的指针,这个类型的指针确实有自定义的String方法。第二Println,我们直接调用了x变量的String()方法;这种情况下编译器会隐式地在x前插入&操作符,这样相当远我们还是调用的IntSet指针的String方法。在第三个Println中,因为IntSet类型没有String方法,所以Println方法会直接以原始的方式理解并打印。所以在这种情况下&符号是不能忘的。在我们这种场景下,你把String方法绑定到IntSet对象上,而不是IntSet指针上可能会更合适一些,不过这也需要具体问题具体分析。

练习6.1: 为bit数组实现下面这些方法

func (*IntSet) Len() int      // return the number of elements
func (*IntSet) Remove(x int)  // remove x from the set
func (*IntSet) Clear()        // remove all elements from the set
func (*IntSet) Copy() *IntSet // return a copy of the set

练习 6.2: 定义一个变参方法(*IntSet).AddAll(...int),这个方法可以为一组IntSet值求和,比如s.AddAll(1,2,3)。

练习 6.3: (*IntSet).UnionWith会用|操作符计算两个集合的交集,我们再为IntSet实现另外的几个函数IntersectWith(交集:元素在A集合B集合均出现),DifferenceWith(差集:元素出现在A集合,未出现在B集合),SymmetricDifference(并差集:元素出现在A但没有出现在B,或者出现在B没有出现在A)。 练习6.4: 实现一个Elems方法,返回集合中的所有元素,用于做一些range之类的遍历操作。

练习 6.5: 我们这章定义的IntSet里的每个字都是用的uint64类型,但是64位的数值可能在32位的平台上不高效。修改程序,使其使用uint类型,这种类型对于32位平台来说更合适。当然了,这里我们可以不用简单粗暴地除64,可以定义一个常量来决定是用32还是64,这里你可能会用到平台的自动判断的一个智能表达式:32 << (^uint(0) >> 63)

Previous方法值和方法表达式Next封装

Last updated 4 years ago

Was this helpful?