结构化数据、图算法与数据库¶

这一章回答:程序怎么和「别人家」的数据打交道? 三条路:JSON(网络时代的通用语,重点是怎么流式处理而不是一次性吞进内存)、图算法(拿 JSON 描述的图,算两条经典的最优化路径)、数据库(database/sql 一个门面,背后换 SQLite 或 PostgreSQL 只改连接那几行)。读完你会拿到「数据进得来、算得快、存得下、报得出」的完整一环。

1. 这一章在原书里的位置¶

原书第 7 章,第二部分的中段。第 5、6 章学会了和一台机器的本地资源打交道, 本章开始和别的系统的数据打交道——「你的 Go 程序开始长得像一个生产程序了」是原书的原话精神¹。第 8、9 章接着把它送上网络。

2. 顶层全景¶

  JSON(§3–§5)          图(§6–§8)              数据库(§9–§11)
  Decoder/Encoder 流     TSP:Held-Karp DP       database/sql 门面
  比逐条 Marshal 快 30%   (位掩码 + dp 表)        ├─ SQLite:单文件,CGO
  json/v2:更严更快       Dijkstra:小顶堆          └─ PostgreSQL:pgx + Docker
  (实验性,无流式 API)    (单源最短路)            报表:动态 IN 占位符 + JSON 导出

图说:三块共用同一批基础设施——struct tag(第 3 号)、buffer 与流(第 7 号)、 benchmark(第 6 号)。本章几乎没有新语法,全是组合。

3. JSON 流:一条一条地吃,别一口吞¶

要处理的 JSON 是一连串记录(日志、事件流)时,书上的答案是 json.Decoder: 它挂在任意 io.Reader(文件、网络连接、stdin)上,每次 Decode 吐出一条记录, 流结束返回 io.EOF。坏记录跳过、继续,处理过程内存占用恒定²:

dec := json.NewDecoder(f)
for {
    var rec Record
    if err := dec.Decode(&rec); err != nil {   // io.EOF = 流干净地结束
        if err == io.EOF { break }
        fmt.Println("Skipping invalid JSON:", err)
        continue
    }
    // 处理这条:fmt.Printf("ID: %d | Event: %s | Time: %s\n", …)
}

对照组有两种常见姿势,各有一课:

json.Unmarshal(data, &rec) 配 os.ReadFile:整个文件先进内存, 一条一条解析时还要反复造临时切片——benchmark 见下。
json/v2(Go 1.25,GOEXPERIMENT=jsonv2):严格遵循 RFC 8259、 拒绝重复键、错误信息更准、unmarshal 分配更少;但流式 API 还没实现, 书中的示例只好手动按行扫、数方括号、剥逗号——书里诚实地对比: 这「更灵活但增加复杂度和解析错误的风险」, 规范的顺序数据流,json.Decoder 仍是首选³。

benchmark:流式 vs 逐条¶

同样 1000 条记录、同样的结构体⁴:

  BenchmarkSingleRecord-14   1897 次   656289 ns/op   416185 B/op   9000 allocs/op
  BenchmarkStream-14         2562 次   465048 ns/op    23880 B/op   2009 allocs/op
                              ↑ 快约 30%     ↑ 内存 1/17    ↑ 分配不到 1/4

图说:每对 Marshal/Unmarshal 都新造缓冲,分配 9 次 × 1000 条; Decoder 复用内部缓冲、增量解析。再叠上第 5 号的教训: 分配少 = GC 活少 = 长尾延迟低——流式赢的不只是平均时间。

4. JSON ↔ XML:tag 的双面人生¶

json2xml.go 展示了同一结构体同时挂两类 tag:

type Record struct {
    ID    int    `json:"id" xml:"id"`
    Event string `json:"event" xml:"event"`
    Time  string `json:"timestamp" xml:"timestamp"`
}
type Records struct {
    XMLName xml.Name `xml:"records"`        // 根元素名
    Items   []Record `xml:"record"`          // 每个元素的标签
}

json.Unmarshal 按行读、收进切片,xml.MarshalIndent 一次成型, 输出 <records><record><id>1</id>…⁵。这是 03 号拆解 struct tag 一节的实战兑现:tag 就是「同一个结构体对多个世界」的翻译表。 (现实的 JSON→XML 转换有属性、命名空间、数组语义的深坑,书里是教学简化版。)

5. 生成图数据:一个自产自销的测试工具¶

generateGraph.go 造完全图(每对不同节点间都有边,权重 1–10 随机): 节点叫 A、B、C…(string('A'+i)),双层 map 存边(edges[u][v] = 权重), json.MarshalIndent 落盘⁶。这个工具本身就是一课: 给算法造可控输入的生成器,和算法一样值得写——第 12 章造时间序列数据时同一招。

6. 主线例子(一):TSP 与 Held-Karp 动态规划¶

旅行商问题(TSP):每对城市间有距离,求「每城恰好访问一次并回到起点」的最短路线。它是 NP-complete 的——城市一多,精确解就不存在高效算法⁷。书上用 Held-Karp:动态规划 + 位掩码,把暴力的阶乘复杂度压到 O(n²·2ⁿ), 代价是 O(n·2ⁿ) 的内存。5–20 城规模内这是精确解的标准做法。

机制三层,照书上的 fiveNodes 图(A–E)走:

① 状态 = (已访问集合, 当前所在城)。 集合用位掩码表示:n 个城,n 个比特, mask 的第 i 位为 1 表示第 i 城已访问。dp[mask][u] = 「从 A 出发、走过 mask 里的城、停在 u」的最小代价;path[mask][u] 记录这个最优状态是从哪个城来的 (回头拼路线用)。全部初始化为 ∞(还没有路)⁸。

② 填表。 从只含起点的集合出发(dp[1<<0][0] = 0),按集合从小到大: 对每个「在集合里的 u、不在集合里的 v、u→v 有边」, dp[mask|1<<v][v] = min(现有值, dp[mask][u] + w)。掩码按整数递增枚举恰好保证「小子集先算、大子集后算」——DP 的顺序依赖。

③ 收尾与回溯。 全集合 mask(所有位为 1)时,对每个 u 加上回起点的边, 取最小得 bestCost;沿 path 表从最后一个城倒着走、每步从掩码里抹掉该城, 就拼出路线⁹。

实测输出(5 城随机图):Optimal path: [A D C B E]、Total cost: 14.00¹⁰。 每个承重机制都在这条主线上占了一步:位掩码是状态、双层循环是转移、 path 表是回溯。这正是第 5 号 PGO 例子说的「复杂控制流」——如果给这段代码跑 PGO, 位运算的热循环正是编译器想要的信息。

7. 主线例子(二):Dijkstra,小顶堆定的胜负¶

Dijkstra:单源最短路(边权非负;有负权要换 Bellman-Ford)¹¹。直觉一句话:每次从未确定的城里挑「当前离起点最近」的那个,它的最短距离就定死了 (任何绕道都更长),然后用它松驰邻居。挑最小这一步用不用高效数据结构, 决定算法的档次:

实现	复杂度	书里
每次扫一遍数组挑最小	O(V²)	不用
小顶堆(优先队列)	O((V+E) log V)	用这个

Go 的 container/heap 要求实现五个方法(Len/Less/Swap/Push/Pop), 书上给了完整的一份 PriorityQueue(Item 带 node、priority、index)¹²。算法主体短得出奇:

dist[source] = 0; heap.Push(pq, &Item{source, 0})
for pq.Len() > 0 {
    u := heap.Pop(pq).(*Item)               // 当前最近的未确定城
    for v, w := range g.Edges[u.node] {
        if alt := dist[u.node] + w; alt < dist[v] {   // 松驰:经过 u 更近?
            dist[v] = alt; prev[v] = u.node
            heap.Push(pq, &Item{v, alt})
        }
    }
}

真实输出(15 城图,源 A)有个绝佳的教学点:A 到 C 的最短路不是直连,而是 [A J E C],总代价 4.00——比「看起来近」的边更绕的组合反而更短, 这正是「松驰」存在的意义;prev 链往回走就重建出路径¹³。

8. 两个算法放一起看¶

TSP 和 Dijkstra 共用同一种「松弛」语言: dp 转移 dp[mask][u]+w < dp[newMask][v] 和 Dijkstra 的 alt < dist[v] 是同构的——「经过当前状态去下一个状态,更短就更新」是最优化问题的通用句型。区别在状态定义:TSP 的状态带「集合」(2ⁿ 个),所以是指数级; Dijkstra 的状态只有「单点」(V 个),所以能近线性。原书把这两个放同一章, 讲的其实是同一件事:算法复杂度由「状态的多少」决定,数据结构负责把每步变便宜。

9. SQLite:database/sql 门面的第一课¶

database/sql 是 Go 官方的数据库抽象层:sql.Open("驱动名", 连接串) 拿句柄, 之后 Exec(写)、Query(读多行)、Prepare(预编译)全是统一 API, 底下换驱动就换数据库。SQLite 用 mattn/go-sqlite3 驱动(注意:它依赖 CGO, 二进制不再完全自包含、交叉编译变麻烦——第 1 章「静态链接」卖点的第一个例外, 书里明说了)¹⁴。

CRUD 四件套 + 两个进阶:

// 连接即建表:CREATE TABLE IF NOT EXISTS,幂等
db, err := sql.Open("sqlite3", dbFile)

// 增:? 占位符,参数化查询——SQL 注入的解药
db.Exec(`INSERT INTO users (name, email) VALUES (?, ?)`, name, email)

// 批量增:Prepare 一次、循环 Exec——SQL 只编译一遍
stmt, _ := db.Prepare(`INSERT INTO users (name, email) VALUES (?, ?)`)
defer stmt.Close()                       // 资源必还
for name, email := range users { stmt.Exec(name, email) }

// 查:rows.Next + rows.Scan 逐行进变量;defer rows.Close();完事查 rows.Err()
rows, _ := db.Query(`SELECT id, name, email FROM users ORDER BY id`)

「流式 JSON → SQLite」的合龙(storeJSON.go)值得单独看: json.NewDecoder 读一条、预编译 stmt 插一条,INSERT OR IGNORE 让重复 ID 静默跳过——「流式解析 + 预编译写入」是数据搬运管道的标准形态¹⁵。 (sql.Open 是惰性的:它不真连;SQLite 靠文件建库,PostgreSQL 要靠 db.Ping() 验证连通——这个差别就是下一节 connectDB 多一行 Ping 的原因。)

10. PostgreSQL:换驱动,不换代码¶

PostgreSQL 版只有 connectDB 不同:sql.Open("pgx", "postgres://用户:密码@主机:5432/库名?sslmode=disable") + db.Ping() + 建表(自增列从 INTEGER PRIMARY KEY AUTOINCREMENT 换成 SERIAL); 增删改查、预编译语句全部逐字相同¹⁶——这是 database/sql 抽象的价值宣言。

起服务的姿势是 docker-compose(书里给了完整 YAML): postgres:15 镜像、环境变量设好账号密码库名、端口映射 5432, docker-compose up -d 起、docker-compose down -v 连数据卷一起删—— -v 的意义:volume 设计上容器删了数据还在,不 -v 下次起库时 UNIQUE 约束(如 email UNIQUE)会让重跑撞duplicate key 报错¹⁷。

11. 报表:动态 SQL 的克制版¶

报表程序(createReports.go)生成三类汇总:每客户销售额、每月订单数、热销产品。值得学的机制是「可选过滤 + 动态占位符」:

query := `SELECT c.name, SUM(p.price * o.quantity) AS total_sales
          FROM orders o JOIN customers c … JOIN products p …`
var args []interface{}
if len(customers) > 0 {                       // 用户给了过滤名单才拼 WHERE
    query += "WHERE c.name IN (" + placeholders(len(customers)) + ") "
    for _, c := range customers { args = append(args, c) }
}
query += "GROUP BY c.name ORDER BY total_sales DESC"
rows, _ := db.Query(query, args...)           // 占位符照旧,注入仍然无处可钻

placeholders(n) 造 (?, ?, ?);动态拼的是 SQL 的骨架,值永远走占位符—— 这是「动态 SQL」和「字符串拼 SQL(注入温床)」的分界线¹⁸。输出两路:终端表格 + json.NewEncoder 带缩进写文件(enc.SetIndent("", " ")), 一个查询、两种消费者。报表查询是 JOIN + GROUP BY + 聚合的标准作业, 读者零基础可直接照抄结构。

12. 作者的判断与证据¶

判断	性质	依据
顺序 JSON 流首选 json.Decoder	benchmark 实证 + 作者立场	30% 提速、分配 1/4⁴;json/v2 手动解析的风险自评³
Held-Karp 是中小规模 TSP 的实用精确解	算法学共识,书里如实给了复杂度	NP-complete 说明 + O(n²·2ⁿ) 描述⁷
小顶堆是 Dijkstra 的正确配套	复杂度对比实证	O(V²) vs O((V+E) log V) 同段给出¹²
预编译语句批量插入优于逐条 Exec	机制事实(编译一次) + 代码示范	insertUsersPrepared 的对比说明¹⁵
database/sql 让换库只改连接	代码事实	SQLite↔PostgreSQL 的逐段对照¹⁶
动态 SQL 拼骨架、值走占位符	安全常识 + 作者惯用法	IN 占位符构造¹⁸

13. 边界与局限¶

CGO 依赖的坑只警告了 mattn/sqlite3 一家。纯 Go 的 SQLite 驱动 (modernc.org/sqlite)书里没提——这是「单文件自包含」和「零 CGO」的真实取舍题。
并发访问 SQLite(WAL 模式、busy_timeout)没讲;mattn 驱动下多 goroutine 争用会拿到 "database is locked",生产里要配置,本章示例全是单连接顺序跑。
Dijkstra 的堆里会累积过期条目(松驰后旧 priority 的 Item 没删,靠弹出时 dist 已更小来跳过)——经典实现细节,书中代码没做这个校验, 非负权下结果仍正确,但堆会偏大。
报表的动态 IN 有上限(SQLite 默认 999 变量、PostgreSQL 65535), 大名单要分批——书里没提。
json/v2 的状态写得谨慎(实验性、需 GOEXPERIMENT),但没给转正路线图, 读者引用时该查最新发布说明。

14. 可带走的¶

成流的 JSON 用 json.Decoder/Encoder;benchmark 证明它快 30%、分配少 4 倍, 大文件还不会撑爆内存。
json/v2 更严(拒重复键)、更省分配,但暂时没有流式 API; 顺序流仍用 v1,不规则输入才考虑手动解析。
TSP 精确解 = Held-Karp:状态带集合(位掩码)+ dp 转移 + path 回溯; 5 城代价 14、路线 [A D C B E]。
Dijkstra:每次取最近的未确定点、松驰邻居;小顶堆把 O(V²) 压到 O((V+E) log V); 最短路常比「直连」更绕([A J E C] < 直连)。
「经过 X 去 Y 更短就更新」是最优化问题的通用句型; 复杂度由状态的多少决定,数据结构负责每步的成本。
database/sql:Open(惰性)→ Ping(真连)→ Exec/Query/Prepare; 换库只换驱动名和连接串。
批量写用预编译语句;INSERT OR IGNORE 去重;参数化占位符是注入的唯一解。
「Decoder 读一条 → stmt 插一条」是数据管道的标准件。
动态 SQL:拼骨架可以,拼值不行;IN 列表用占位符工厂。
Docker 起数据库,down -v 才有「下次全新」。

15. 原文地图¶

主题	原书章	原文位置
流式 JSON(Decoder)	Working with JSON data	`text/80-fm-working-with-json-data.txt:30`(搜「json.NewDecoder」) · `:56`(搜「ID: 1
流 vs 逐条 benchmark	Working with JSON data	`text/80-fm-working-with-json-data.txt:146`(搜「656289」) · `:162`(搜「internal buffers」)
json/v2 与手动解析的取舍	Working with JSON data	`text/80-fm-working-with-json-data.txt:291`(搜「json/v2」) · `text/81-fm-solving-the-traveling-salesman-problem.txt:17`(搜「increases the risk」)
JSON→XML 双 tag	Working with JSON data	`text/80-fm-working-with-json-data.txt:188`(搜「xml.Name」) · `:263`(搜「<records>」)
图生成器	Solving the traveling salesman problem	`text/81-fm-solving-the-traveling-salesman-problem.txt:79`(搜「generateGraph.go」)
TSP 定义与 Held-Karp	Solving the traveling salesman problem	`text/81-fm-solving-the-traveling-salesman-problem.txt:163`(搜「shortest possible route」) · `:173`(搜「Held–Karp」)
tspDP 三段(掩码/转移/回溯)	Solving the traveling salesman problem	`text/81-fm-solving-the-traveling-salesman-problem.txt:193`(搜「func tspDP」) · `:230`(搜「dp[1<<start]」) · `:268`(搜「endMask」) · `text/82-fm-implementing-the-dijkstra-algorithm.txt:158`(搜「reconstruct path」)
TSP 实测输出	Solving the traveling salesman problem	`text/82-fm-implementing-the-dijkstra-algorithm.txt:27`(搜「Optimal path」)
Dijkstra 直觉与负权边界	Implementing the Dijkstra algorithm	`text/82-fm-implementing-the-dijkstra-algorithm.txt:37`(搜「single source」) · `:40`(搜「Bellman-Ford」)
优先队列五方法与复杂度	Implementing the Dijkstra algorithm	`text/82-fm-implementing-the-dijkstra-algorithm.txt:59`(搜「type Item struct」) · `:93`(搜「O(n²)」)
dijkstra() 主循环与 [A J E C]	Implementing the Dijkstra algorithm	`text/82-fm-implementing-the-dijkstra-algorithm.txt:118`(搜「func dijkstra」) · `:191`(搜「A J E C」)
SQLite CRUD 与预编译	Working with SQLite3	`text/83-fm-working-with-sqlite3.txt:50`(搜「connectDB」) · `:91`(搜「insertUsersPrepared」) · `:112`(搜「parsing and compiling」)
CGO 警告	Working with SQLite3	`text/83-fm-working-with-sqlite3.txt:22`(搜「not fully self-contained」)
流式入库与 OR IGNORE	Working with SQLite3	`text/83-fm-working-with-sqlite3.txt:223`(搜「INSERT OR IGNORE」) · `text/84-fm-working-with-postgresql.txt:22`(搜「Inserted: ID=1」)
pgx 连接与 Ping	Working with PostgreSQL	`text/84-fm-working-with-postgresql.txt:51`(搜「func connectDB」) · `:78`(搜「Ping」)
docker-compose 与 down -v	Working with PostgreSQL	`text/84-fm-working-with-postgresql.txt:100`(搜「docker-compose.yaml」) · `:153`(搜「down -v」)
动态 IN 占位符报表	Creating database reports	`text/85-fm-creating-database-reports.txt:108`(搜「reportSalesPerCustomer」) · `:121`(搜「placeholders」)

出处:「Working with Structured Data and Databases」(text/79-ch07.txt:7,搜「start to feel real」)。「your Go programs start to feel real」。 ↩
出处:「Working with a stream of JSON records」(text/80-fm-working-with-json-data.txt:30,搜「json.NewDecoder」;:56,搜「ID: 1 | Event: login」)。坏记录跳过与 EOF 语义见第 33–41 行。 ↩
出处:「JSON's evolution: json/v2」(text/80-fm-working-with-json-data.txt:291,搜「json/v2」;:300,搜「not supported」)与对比段(text/81-fm-solving-the-traveling-salesman-problem.txt:17,搜「increases the risk」;:23,搜「preferred choice」)。RFC 8259 与拒重复键见第 295–296 行。 ↩↩
出处:「JSON benchmarking」(text/80-fm-working-with-json-data.txt:146,搜「656289」;:147,搜「465048」;:151,搜「9,000」;:161,搜「30% improvement」)。 ↩↩
出处:「Converting from JSON to XML」(text/80-fm-working-with-json-data.txt:188,搜「xml.Name」;:262,搜「json2xml.go」;:263,搜「<records>」)。 ↩
出处:「Creating sample graphs」(text/81-fm-solving-the-traveling-salesman-problem.txt:79,搜「generateGraph.go」;:103,搜「Round」)。string('A'+i) 命名与去自环(u==v continue)见第 93–101 行。 ↩
出处:「Implementing the traveling salesman algorithm」第 148–175 段(text/81-fm-solving-the-traveling-salesman-problem.txt:152,搜「Hamiltonian cycle」;:158,搜「NP-complete」;:173,搜「Held–Karp」)。 ↩↩
出处:「Implementing the traveling salesman algorithm」(text/81-fm-solving-the-traveling-salesman-problem.txt:193,搜「func tspDP」)。size := 1 << n、dp/path 双表、Inf 初始化见第 200–210 行。 ↩
出处:「Implementing the traveling salesman algorithm」(text/81-fm-solving-the-traveling-salesman-problem.txt:230,搜「dp[1<<start][start] = 0」;:245,搜「dp[mask][u]+w」;:268,搜「endMask」;text/82-fm-implementing-the-dijkstra-algorithm.txt:158,搜「reconstruct path」)。掩码递增序=子集从小到大的说明见 text/81-fm-solving-the-traveling-salesman-problem.txt:263。 ↩
出处:「Implementing the traveling salesman algorithm」(text/82-fm-implementing-the-dijkstra-algorithm.txt:27,搜「Optimal path: [A D C B E]」;:28,搜「Total cost: 14.00」)。 ↩
出处:「Implementing the Dijkstra algorithm」第 34–43 段(text/82-fm-implementing-the-dijkstra-algorithm.txt:37,搜「single source」;:40,搜「Bellman-Ford」;:44,搜「assigning a distance of zero」)。 ↩
出处:「Implementing the Dijkstra algorithm」(text/82-fm-implementing-the-dijkstra-algorithm.txt:59,搜「type Item struct」;:66,搜「heap.Interface」;:93,搜「O(n²)」;:113,搜「O((V + E) log V)」)。Less 的小顶堆语义见第 100–103 行。 ↩↩
出处:「Implementing the Dijkstra algorithm」(text/82-fm-implementing-the-dijkstra-algorithm.txt:118,搜「func dijkstra」;:160,搜「reconstructPath」;:191,搜「A J E C」;:199,搜「2.00」)。 ↩
出处:「The use of external Go modules」(text/83-fm-working-with-sqlite3.txt:22,搜「not fully self-contained」;:28,搜「go.sum」)。go.mod/go.sum 的分工与完整性校验在同段。 ↩
出处:「Demonstrating SQLite3 interactions」(text/83-fm-working-with-sqlite3.txt:91,搜「insertUsersPrepared」;:112,搜「parsing and compiling」);「Storing JSON data」(text/83-fm-working-with-sqlite3.txt:223,搜「INSERT OR IGNORE」;:230,搜「json.NewDecoder(f)」)。 ↩↩
出处:「Working with PostgreSQL」(text/84-fm-working-with-postgresql.txt:51,搜「func connectDB」;:78,搜「Ping」;:86,搜「essentially identical」)。SERIAL 与 AUTOINCREMENT 的差异见第 43、82 行。 ↩↩
出处:「Using a Docker image for PostgreSQL」(text/84-fm-working-with-postgresql.txt:100,搜「docker-compose.yaml」;:153,搜「down -v」;:162,搜「UNIQUE NOT NULL」)。 ↩
出处:「Creating database reports」(text/85-fm-creating-database-reports.txt:108,搜「reportSalesPerCustomer」;:121,搜「placeholders(len(customers))」;:139,搜「db.Query(query, args...)」)。saveJSON 的 SetIndent 用法见第 44–56 行。 ↩↩