2.2 短路与复杂度
独立游戏的叙事设计与分支对话 里有一类经验谈：条件写得越少越好，能用一句话说清就别堆三层判断——那是从玩家可读性出发的建议。本节换一个角度问同一个问题：求值器执行一个条件，要访问条件树里的多少个节点？短路这条几乎人人都在用的纪律，到底省下了什么、又必须不改变什么？
答案分两半。短路确实省节点，但它省的是常数而不是渐进量级；而且它有一条铁律——只减步数、不改结果。前一半是复杂度，后一半是正确性。这一节两半都要。
短路是什么
["and", c1, c2] 左假即停：若 c1 为假，无论 c2 是什么，整个合取都是假，于是 c2 的子树不必访问。["or", c1, c2] 左真即停：若 c1 为真，整体为真，c2 不必访问。这两条是布尔代数的恒等式——false ∧ x = false、true ∨ x = true——在执行上就成了一条剪枝。
["not", c] 是单目，没有可省的子树；flag / item / aff 是叶子，本来就只有一次读。所以短路只发生在 and / or 两个内点上。
短路不能改结果
短路是纯优化：它只改变「访问了哪些节点」，不改变「返回什么值」。要让这句话成立，求值器必须满足两条：
- 无副作用：访问右子树除了花时间，不能有别的可观测作用（不写状态、不打日志、不抛「只在右子树里才触发」的异常）。
- 纯函数：结果只由状态决定，与「之前访问过什么」无关。
违反任一条，短路就会从优化变成语义变更。正因为风险在这里，测试的第一组用例不是去数步数，而是把短路与不短路两种模式都与内核的 condOk 对齐：只要两模式在全部位点、全部代表状态上同值，短路就是安全的。
复杂度上界
设一棵条件树的节点数为 n（叶子 + 内点）。不短路（eager）实现两侧子树一律访问，步数恰为 n。短路下每个内点至多省掉一棵子树的访问，故步数 ≤ n。两者都是 O(n)——短路不改变渐进复杂度，只降低常数。
真正的差别在树的形状。当条件树是一条很长的 and 链、且首项为假时，eager 要走完整条链（O(n)），短路访问完首项就返回（O(1)）。所以「短路值不值」取决于条件树的形状，而不取决于节点总数。
S 层：两种实现的步数对照
S 层脚本对同一批条件（全规格 57 个位点）在 16 个代表状态上分别跑短路与不短路两种实现，累加被访问的节点数；另给一个长度 k 的 and 链合成对照，展示形状对步数的影响：
#!/usr/bin/env python3
# file: sim/ne_02_2_short_circuit.py
# tier: S
# verify: /opt/homebrew/bin/python3 sim/ne_02_2_short_circuit.py
"""卷二 2.2 短路与复杂度（S 层）：同一批条件在短路与不短路两种实现下的节点访问次数对照。
短路语义：["and", c1, c2] 左假即停（不再访问 c2 子树）；["or", c1, c2] 左真即停。
不短路（eager）语义：两侧子树一律访问。两种实现必须给出**同一个布尔值**——短路只影响
步数，不影响结果。步数定义 = 条件树里被访问的节点数（含叶子与内点）。
代表状态 = found_yan_journal ∈ {0,1} × yan ∈ {0,10,39,40,41,60,85,100} 共 16 个。
另给一个合成对照：长度 k 的 and 链、首项为假，展示短路把线性步数压到常数。
复用 sim/na_00_spec_check.py 的 load_spec。产出 out/ne_02_2_short_circuit.json。
"""
from __future__ import annotations
import json
import os
import sys
HERE = os.path.dirname(os.path.abspath(__file__))
sys.path.insert(0, HERE)
import na_00_spec_check as base # noqa: E402 复用 load_spec
OUT = os.path.join(os.path.dirname(HERE), "out/ne_02_2_short_circuit.json")
def sites(spec: dict) -> list:
out = []
for n in spec["dialogue"]:
if n.get("line_when"):
out.append((f"{n['id']}.line_when", n["line_when"]))
for c in (n.get("choices") or []):
if c.get("when"):
out.append((f"{n['id']}/{c['id']}", c["when"]))
for e in spec["scene_graph"]["edges"]:
if e.get("when"):
out.append((f"{e['from']}->{e['to']}", e["when"]))
for nd in spec["scene_graph"]["nodes"]:
if nd.get("enter_when"):
out.append((f"node {nd['id']}", nd["enter_when"]))
for loc in spec["world"]["locations"]:
if loc.get("unlock_when"):
out.append((f"location {loc['id']}", loc["unlock_when"]))
for e in spec["endings"]:
if e.get("when"):
out.append((f"ending {e['id']}", e["when"]))
return out
def ev(c, s, short: bool, steps: list) -> bool:
"""带步数计数的求值器。short=True 时 and/or 短路。"""
if c is None:
return True
steps[0] += 1
k = c[0]
if k == "flag":
return s["flags"].get(c[1], 0) == c[2]
if k == "item":
return s["items"].get(c[1], 0) == c[2]
if k == "aff":
v, op, n = s["aff"].get(c[1], 0), c[2], c[3]
return v >= n if op == ">=" else v < n if op == "<" else v == n if op == "==" else v != n
if k == "and":
left = ev(c[1], s, short, steps)
if short and not left:
return False
right = ev(c[2], s, short, steps)
return left and right
if k == "or":
left = ev(c[1], s, short, steps)
if short and left:
return True
right = ev(c[2], s, short, steps)
return left or right
return not ev(c[1], s, short, steps) # not
def count(c, s, short: bool) -> tuple:
steps = [0]
val = ev(c, s, short, steps)
return val, steps[0]
def battery(spec: dict) -> list:
out = []
for flag in (0, 1):
for yan in (0, 10, 39, 40, 41, 60, 85, 100):
st = {"node": "d_dq_2",
"aff": {v: next(c["affinity"]["init"] for c in spec["characters"] if c["id"] == v)
for v in spec["state"]["vars"]},
"flags": {f: 0 for f in spec["state"]["flags"]},
"items": {i: 0 for i in spec["state"]["items"]}, "path": []}
st["flags"]["found_yan_journal"] = flag
st["aff"]["yan"] = yan
out.append(st)
return out
def chain(k: int) -> dict:
"""长度 k 的 and 链，首项为假。节点数 = 2k-1（k 个叶子 + k-1 个 and 内点）。"""
atom = ["flag", "found_yan_journal", 1]
c = atom
for _ in range(k - 1):
c = ["and", atom, c]
return c
def main() -> int:
spec = base.load_spec()
all_sites = sites(spec)
states = battery(spec)
zero = {"node": "x", "aff": {v: 0 for v in spec["state"]["vars"]},
"flags": {f: 0 for f in spec["state"]["flags"]},
"items": {i: 0 for i in spec["state"]["items"]}, "path": []}
eager_total = short_total = 0
mismatch = 0
for _, c in all_sites:
for s in states:
v1, n1 = count(c, s, short=False)
v2, n2 = count(c, s, short=True)
eager_total += n1
short_total += n2
if v1 != v2:
mismatch += 1
print(f"条件位点 {len(all_sites)} 个 / 代表状态 {len(states)} 个")
print(f"不短路（eager）总步数 {eager_total}")
print(f"短路（short-circuit）总步数 {short_total}")
print(f"省下 {eager_total - short_total} 步（{(eager_total - short_total) * 100 // eager_total}%）")
print(f"两种实现结果不一致次数 {mismatch}（必须为 0）")
print("合成对照（长度 k 的 and 链，首项为假）：")
syn = []
for k in (1, 2, 4, 8, 16):
c = chain(k)
nodes = 2 * k - 1
_, e = count(c, zero, short=False)
_, sh = count(c, zero, short=True)
syn.append({"k": k, "nodes": nodes, "eager": e, "short": sh})
print(f" k={k:<2} 节点 {nodes:<2} eager {e:<2} 短路 {sh}")
print(f"上界：树内节点数 n 时，eager 步数 = n，短路步数 ≤ n")
report = {"sites": len(all_sites), "states": len(states), "eager_total": eager_total,
"short_total": short_total, "saved": eager_total - short_total,
"mismatch": mismatch, "synthetic": syn}
os.makedirs(os.path.dirname(OUT), exist_ok=True)
with open(OUT, "w", encoding="utf-8") as fh:
json.dump(report, fh, ensure_ascii=False, indent=2)
fh.write("\n")
if mismatch:
print(f"FAIL 短路改变了求值结果 {mismatch} 次")
return 1
print("OK ne_02_2_short_circuit：短路只减步数、不改结果")
return 0
if __name__ == "__main__":
sys.exit(main())
本机实跑 /opt/homebrew/bin/python3 sim/ne_02_2_short_circuit.py：
条件位点 57 个 / 代表状态 16 个
不短路（eager）总步数 1008
短路（short-circuit）总步数 992
省下 16 步（1%）
两种实现结果不一致次数 0（必须为 0）
合成对照（长度 k 的 and 链，首项为假）：
k=1 节点 1 eager 1 短路 1
k=2 节点 3 eager 3 短路 2
k=4 节点 7 eager 7 短路 2
k=8 节点 15 eager 15 短路 2
k=16 节点 31 eager 31 短路 2
上界：树内节点数 n 时，eager 步数 = n，短路步数 ≤ n
OK ne_02_2_short_circuit：短路只减步数、不改结果
P 层：带计数的求值器
P 层是同一台求值器的 TypeScript 版，多了一个 short 开关与一个步数计数器。测试同时跑两种模式并与内核对齐：
// file: core/src/inkwell/ne_02_2_short_circuit.ts
// tier: P
// verify: node --test 'core/test/ne_02_2_short_circuit.test.ts'
// 卷二 2.2：带步数计数的条件求值器。short=true 时 and 左假即停、or 左真即停；
// short=false 时两侧子树一律访问（eager）。短路只减步数、不改结果——两模式必须同值。
import type { Cond, State } from "./engine.ts";
export type Counted = { value: boolean; steps: number };
/** 求值并数「被访问的条件树节点数」（含叶子与内点）。 */
export function evalCounted(c: Cond | null | undefined, s: State, short: boolean): Counted {
let steps = 0;
const ev = (x: Cond | null | undefined): boolean => {
if (!x) return true;
steps += 1;
const k = x[0];
if (k === "flag") return (s.flags[x[1] as string] ?? 0) === (x[2] as number);
if (k === "item") return (s.items[x[1] as string] ?? 0) === (x[2] as number);
if (k === "aff") {
const v = s.aff[x[1] as string] ?? 0;
const op = x[2] as string;
const n = x[3] as number;
if (op === ">=") return v >= n;
if (op === "<") return v < n;
if (op === "==") return v === n;
return v !== n;
}
if (k === "and") {
const l = ev(x[1] as Cond);
if (short && !l) return false; // 左假即停
const r = ev(x[2] as Cond); // eager 下必须真访问右子树
return l && r;
}
if (k === "or") {
const l = ev(x[1] as Cond);
if (short && l) return true; // 左真即停
const r = ev(x[2] as Cond);
return l || r;
}
return !ev(x[1] as Cond); // not
};
return { value: ev(c), steps };
}
/** 长度 k 的 and 链，首项为假；节点数 2k-1。用于展示短路把线性步数压到常数。 */
export function andChain(k: number): Cond {
const atom: Cond = ["flag", "found_yan_journal", 1];
let c: Cond = atom;
for (let i = 1; i < k; i += 1) c = ["and", atom, c];
return c;
}
本机实跑 node --test 'core/test/ne_02_2_short_circuit.test.ts'：
短路对照：57 位点 × 16 状态 × 2 模式 = 1824 次同值
代表状态 16 个：eager 1008 步 / 短路 992 步 / 省 16 步
✔ 短路与不短路两种模式都与 condOk 同值（短路只减步数） (1.656917ms)
✔ 步数上界：eager = 树内节点数，短路 ≤ 树内节点数 (0.350375ms)
✔ 实测总步数：eager 1008 / 短路 992，省 16 步 (0.414417ms)
✔ 合成对照：长度 k 的 and 链首项为假，eager 2k-1 步、短路 ≤ 2 步 (0.139917ms)
ℹ tests 4
ℹ suites 0
ℹ pass 4
ℹ fail 0
ℹ cancelled 0
ℹ skipped 0
ℹ todo 0
ℹ duration_ms 148.13475
判读：本规格省得少，但上界守得住
第一，这份规格里短路几乎不省。 57 个位点、16 个代表状态，eager 1008 步、短路 992 步，只省 16 步（1%）。原因直接来自 2.1 的用量表：63 个树节点里只有 2 个 and、0 个 or，其余是叶子与 not。短路的收益 = 2 个 and 位点在「左假」状态下的 1 步 × 状态数，就是这个 16。树浅、且几乎没有合取，短路自然省不动。
第二，上界与形状才是要点。 合成对照把形状的影响放大给人看：
| and 链长度 k | 树内节点 | eager 步数 | 短路步数 |
|---|---|---|---|
| 1 | 1 | 1 | 1 |
| 2 | 3 | 3 | 2 |
| 4 | 7 | 7 | 2 |
| 8 | 15 | 15 | 2 |
| 16 | 31 | 31 | 2 |
首项为假的 and 链：eager 走完整条链（2k−1 步），短路访问完首项就返回（k=1 时是那唯一一个叶子 1 步，k≥2 时恒 2 步）。这不是说这份规格「慢」——1008 步在任何机器上都是零成本——而是说：短路的收益由条件树的形状决定，节点总数只给出上界。规格作者真正能控制的，是把「便宜的判据放左边」。
第三，短路只减步数、不改结果，这条有 1824 次同值作证。 两种模式在 57 位点 × 16 状态上全部同值——短路是纯优化，不是语义变更。
自检表
| 检查项 | 合格标准 |
|---|---|
| 短路不改结果 | 短路与不短路两模式在全部位点全部状态上同值 |
| 上界成立 | eager 步数恒等于树内节点数，短路步数恒不超过它 |
| 无副作用 | 访问右子树除花时间外无可观测作用 |
| 形状敏感 | 收益随条件树形状变化，而不随节点总数线性变化 |
| 步数是 proxy | 只做相对比较（短路 vs 不短路），不声称「更快」 |
短路管的是「一次求值花多少步」。下一个执行侧的问题更根本：一个条件在状态域里到底有没有解——它会不会恒假、是不是写了个永远不成立的门槛。下一节把可满足性做成可判定的。
阅读导航：上一节：2.1 条件表达式的求值器 · 下一节：2.3 条件的可满足性 。
继续阅读
探索更多技术文章
浏览归档，发现更多关于系统设计、工具链和工程实践的内容。