Go 实现与实战练习¶

学习目标¶

学完本章后，学习者应该能够：

使用 Go 标准库实现常见算法需求。
用泛型封装简单数据结构。
编写表格驱动测试验证算法代码。
使用 benchmark 初步比较不同实现。

Go 标准库优先¶

工程中不要一上来手写所有结构。Go 标准库已经提供了很多基础能力：

需求	标准库
排序	`sort`
堆	`container/heap`
链表	`container/list`
字符串处理	`strings`
字节处理	`bytes`
哈希	`hash`、`crypto`
时间	`time`
并发同步	`sync`

高级工程师应该知道什么时候使用标准库，什么时候自己封装，什么时候引入成熟第三方库。

表格驱动测试¶

算法代码很适合用表格驱动测试。

func TestBinarySearch(t *testing.T) {
    tests := []struct {
        name   string
        nums   []int
        target int
        want   int
    }{
        {name: "found", nums: []int{1, 2, 3}, target: 2, want: 1},
        {name: "missing", nums: []int{1, 2, 3}, target: 4, want: -1},
        {name: "empty", nums: nil, target: 1, want: -1},
    }

    for _, tt := range tests {
        t.Run(tt.name, func(t *testing.T) {
            got := BinarySearch(tt.nums, tt.target)
            if got != tt.want {
                t.Fatalf("got %d, want %d", got, tt.want)
            }
        })
    }
}

测试要覆盖：

正常输入。
空输入。
边界输入。
重复元素。
不存在目标。

Benchmark¶

当你不确定两种实现性能差异时，可以写 benchmark。

func BenchmarkHasDuplicateFast(b *testing.B) {
    nums := make([]int, 10000)
    for i := range nums {
        nums[i] = i
    }

    b.ResetTimer()
    for i := 0; i < b.N; i++ {
        _ = hasDuplicateFast(nums)
    }
}

运行：

Windows PowerShellLinux / macOS

go test -bench=. -benchmem

go test -bench=. -benchmem

-benchmem 可以显示内存分配情况。

泛型实现 Set¶

Go 泛型适合封装简单通用结构。

type Set[T comparable] struct {
    items map[T]struct{}
}

func NewSet[T comparable]() *Set[T] {
    return &Set[T]{items: make(map[T]struct{})}
}

func (s *Set[T]) Add(v T) {
    s.items[v] = struct{}{}
}

func (s *Set[T]) Remove(v T) {
    delete(s.items, v)
}

func (s *Set[T]) Contains(v T) bool {
    _, ok := s.items[v]
    return ok
}

func (s *Set[T]) Len() int {
    return len(s.items)
}

注意：这个 Set 不是并发安全的。

并发安全¶

如果多个 goroutine 同时访问 map，需要加锁：

type SafeSet[T comparable] struct {
    mu    sync.RWMutex
    items map[T]struct{}
}

func (s *SafeSet[T]) Contains(v T) bool {
    s.mu.RLock()
    defer s.mu.RUnlock()
    _, ok := s.items[v]
    return ok
}

但不要看到并发就盲目加锁。锁会带来复杂度和性能成本。也可以通过 channel 把状态管理收敛到单 goroutine。

Go 后端实际应用例子¶

例子一：为批量接口参数去重¶

批量查询接口经常需要对 ID 去重，避免重复查询数据库或缓存：

func UniqueIDs(ids []int64) []int64 {
    seen := make(map[int64]struct{}, len(ids))
    result := make([]int64, 0, len(ids))

    for _, id := range ids {
        if _, ok := seen[id]; ok {
            continue
        }
        seen[id] = struct{}{}
        result = append(result, id)
    }

    return result
}

这个例子背后就是 map 实现 Set 的思想。它比双重循环更适合大批量 ID，但会额外使用 O(n) 空间。

例子二：用 benchmark 比较去重实现¶

如果有人提出“用双重循环避免 map 分配更快”，不要只凭感觉争论，可以写 benchmark 验证：

func BenchmarkUniqueIDs(b *testing.B) {
    ids := make([]int64, 0, 10000)
    for i := 0; i < 10000; i++ {
        ids = append(ids, int64(i%1000))
    }

    b.ResetTimer()
    for i := 0; i < b.N; i++ {
        _ = UniqueIDs(ids)
    }
}

用数据判断取舍，是高级工程师写算法代码时很重要的习惯。

实战任务¶

完成一个小型算法工具包：

Set[T comparable]
Stack[T any]
Queue[T any]
BinarySearch
TopK

要求：

每个结构都有单元测试。
测试覆盖空输入和边界条件。
至少为一个函数写 benchmark。
README 中写清楚复杂度。

参考实现方向

可以按下面目录组织：

algokit/
  set.go
  stack.go
  queue.go
  search.go
  topk.go
  set_test.go
  stack_test.go
  queue_test.go
  search_test.go
  topk_test.go
  README.md

Set[T comparable] 可以用 map[T]struct{}；Stack[T] 可以用 slice 尾部入栈和出栈；Queue[T] 可以先用 slice 实现，进阶版改成环形队列；BinarySearch 要求输入有序；TopK 可以先用排序实现，再用堆优化。

README 中应写明：

结构或函数	时间复杂度	空间复杂度
Set Contains	O(1) average	O(n)
Stack Push/Pop	O(1) amortized	O(n)
Queue Push/Pop	O(1) amortized	O(n)
BinarySearch	O(log n)	O(1)
TopK by sort	O(n log n)	O(n) 或 O(1)，取决于是否复制

表格驱动测试至少覆盖空输入、单元素、重复元素、目标不存在、k 大于列表长度等情况。benchmark 可以优先写 UniqueIDs、TopK 或 BinarySearch。

面试题¶

1. 什么时候应该手写数据结构，什么时候应该使用标准库？¶

参考答案

优先使用标准库，因为标准库经过充分测试，维护成本低。只有当标准库不能满足业务语义、性能要求或封装表达时，才考虑自己实现。

例如排序应优先使用 sort，堆可以用 container/heap。如果需要业务语义明确的 Set，可以用 map 封装一个轻量结构。

2. 为什么算法代码适合表格驱动测试？¶

参考答案

算法函数通常输入输出明确，很适合用多组测试数据覆盖不同场景。表格驱动测试可以把正常、异常、边界、空输入、重复输入等情况集中表达，结构清晰，也方便新增用例。

它还能避免只测试“快乐路径”，提高算法代码可靠性。

3. Benchmark 能解决什么问题？¶

参考答案

Benchmark 用于比较实现的性能，包括耗时和内存分配。它能帮助我们验证优化是否真的有效，而不是凭感觉判断。

但 benchmark 也要谨慎设计，避免编译器优化掉测试逻辑，输入数据要接近真实场景，结果要结合可读性和维护成本一起判断。

4. Go 泛型适合用在哪些数据结构上？¶

参考答案

泛型适合封装类型无关、逻辑一致的数据结构，比如 Set、Stack、Queue、Heap 包装等。它可以减少重复代码，同时保留类型安全。

但泛型不应滥用。如果业务结构和行为强相关，直接写具体类型可能更清晰。

5. 如何让基于 map 的 Set 并发安全？¶

参考答案

可以用 sync.RWMutex 保护 map，读操作加读锁，写操作加写锁。也可以使用 sync.Map，但它更适合特定读多写少或 key 稳定的场景。

另一种方式是通过 channel 把所有操作集中到一个 goroutine 中，避免共享内存。选择哪种方式要看读写比例、性能要求和代码复杂度。