Column 2 · Aha! Algorithms：把难题变成已会的问题

按第二版Column 2重建three problems、missing integer外部划分、ubiquitous binary search、vector rotation primitives、sorting signatures与anagram pipeline。

从“先预测答案会长什么样”开始

Aha Algorithm（）不是背诵奇技，而是训练看见structure。

先预测：下面three problems看起来毫无关系，它们各自隐藏了什么可复用primitive？

  1. 在至多four billion个random 32-bit integers中找一个missing integer。
  2. 把n-element vector向左rotate d positions，要求O(n) time与O(1) extra space。
  3. 在dictionary中找出all sets of anagrams。
problem
rotate n items left by d
representation
compose reversals or cycles
aha insight
powerful primitives
Each little problem becomes simple only after choosing a view that exposes monotonicity, permutation structure, or canonical equality.

它们分别会变成：反复缩小underfull universe、组合reverse operations、把equivalence转成sortable canonical keys。

2.1 Three Problems A：Missing 32-bit integer

32-bit unsigned universe有：

U=232=4,294,967,296U=2^{32}=4,294,967,296

File至多含4,000,000,000 integers，所以即使all distinct，也至少缺少：

232−4,000,000,000=294,967,2962^{32}-4,000,000,000 =294,967,296

个values。Existence来自pigeonhole principle，不需要扫描后才知道。

若有ample memory，分配 2322^{32} bits的bitmap，约512 MiB；scan file设置bits，再scan bitmap找first zero。Time O(m+U)，space O(U) bits。

真正有趣的是：只有few hundred bytes main memory，但允许sequential scratch files，怎样保持linear-scale I/O？

2.2 External partitioning：找underfull half

按most significant bit把records分成0-prefix与1-prefix两个scratch streams，同时count。每个half最多容纳 2312^{31} distinct values；至少一个half的record count小于capacity，它必含missing value。

保留underfull half，按next bit再分；每轮prefix增加one bit，capacity减半。32 rounds后prefix本身就是missing integer。

Invariant：

records⁡(P)<capacity⁡(P)=232−∣P∣\operatorname{records}(P) < \operatorname{capacity}(P) =2^{32-|P|}

因此prefix P覆盖的range必有hole。Partition只需当前bit、two output buffers和counts；main memory可保持constant。

for (int bit = 31; bit >= 0; --bit) {
    split_by_bit(current, zero_file, one_file, bit, &zeros, &ones);
    uint64_t half_capacity = UINT64_C(1) << bit;
    current = zeros < half_capacity ? zero_file : one_file;
    prefix = (prefix << 1) | (current == one_file);
}

Production实现不应真的反复创建无界temporary files；可复用two files，或在memory允许时先count many high-bit buckets，再对one underfull bucket做local bitmap。

2.3 Ubiquitous Binary Search：寻找单调边界

二分查找（）不只是在sorted array中找key。它是“寻找单调transition”的general pattern。

Column的经典场景是一叠约1000张cards，其中one bad card会让整批program output异常。测试一个subset代价高，但能回答“bad card是否在这个half”。逐半测试约：

⌈log⁡21000⌉=10\left\lceil\log_2 1000\right\rceil=10

次即可定位。

抽象接口不是array[mid] < target，而是predicate：

function firstTrue(low: number, high: number, pred: (i: number) => boolean) {
  while (low < high) {
    const mid = low + Math.floor((high - low) / 2);
    if (pred(mid)) high = mid;
    else low = mid + 1;
  }
  return low;
}

Precondition是predicate在search interval内形如false...false,true...true。若它nonmonotone，binary search可能稳定返回错误答案。

Binary search也能用于version regression、configuration changes、failure-inducing input prefix、capacity threshold和minimum feasible resource。每次test必须清楚回答哪一half仍含boundary。

2.4 Three Problems B：Vector Rotation

向量旋转（）要求：

x[0:n]=ab⟶bax[0:n]=ab \longrightarrow ba

例如abcdefgh left rotate 3得到defghabc。

Straightforward methods揭示tradeoffs：

  • Copy prefix a，shift b，再copy a：O(n) time、O(d) extra space。
  • Left shift one position，repeat d times：O(nd) time、O(1) space。
  • Juggling cycles：O(n) time、O(1) space。
  • Block swap：O(n) time、O(1) space。
  • Three reversals：O(n) time、O(1) space，proof最简洁。

2.5 The Power of Primitives：three reversals

反转（）primitive：

void reverse(Item *x, size_t first, size_t last) {
    while (first < last) {
        Item tmp = x[first];
        x[first++] = x[last];
        x[last--] = tmp;
    }
}

把x写成ab，依次：

ab→rev⁡(a)aRb→rev⁡(b)aRbR→rev⁡(all)baab \xrightarrow{\operatorname{rev}(a)} a^Rb \xrightarrow{\operatorname{rev}(b)} a^Rb^R \xrightarrow{\operatorname{rev}(all)} ba 
d %= n;
if (d != 0) {
    reverse(x, 0, d - 1);
    reverse(x, d, n - 1);
    reverse(x, 0, n - 1);
}

Total swaps不超过n；extra state是indexes和one temporary Item。Empty vector要在d %= n前special-case，避免division by zero。

2.6 Juggling Algorithm：rotation的cycle structure

Rotation把old index j映射到：

π(j)=(j−d) mod n\pi(j)=(j-d)\bmod n

这个permutation分成：

g=gcd⁡(n,d)g=\gcd(n,d)

个disjoint cycles，每个length n/gn/g。每个cycle保留one temporary value，沿 j+d mod nj+d\bmod n 搬运。

size_t cycles = gcd(n, d);
for (size_t start = 0; start < cycles; ++start) {
    Item saved = x[start];
    size_t current = start;
    for (;;) {
        size_t next = current + d;
        if (next >= n) next -= n;
        if (next == start) break;
        x[current] = x[next];
        current = next;
    }
    x[current] = saved;
}

Proof来自cycle decomposition：cycles不重叠且cover every index；each assignment把正确source搬到destination；closing write恢复saved value。

Three reversals通常更容易review，juggling则揭示permutation algebra。Aha insight不要求只存在one solution，而是让不同primitives暴露不同proof与constant factors。

2.7 Three Problems C：Anagram equivalence

Anagrams是letters multiset相同的words。Pairwise比较dictionary中all word pairs需要O(D²) equivalence tests。关键是构造canonical signature：

sig⁡(w)=sort⁡(normalize⁡(w))\operatorname{sig}(w) = \operatorname{sort}(\operatorname{normalize}(w))

Anagram Signature（）把permutation equivalence变成string equality。

Correctness有两个方向：

  • Same letters with same multiplicities经过sorting得到identical sequence。
  • Identical sorted sequences意味着每个character count相同，所以words互为permutations。

Normalization policy必须明确case、punctuation、accents与Unicode graphemes。ASCII lowercase classroom dictionary可按bytes排序；general text不能假装byte等于character。

2.8 Getting It Together: Sorting

Sorting不只是产生ordered report，还能把equal keys聚在一起：

  1. 对每个word计算signature。
  2. Emit (signature, originalWord) pair。
  3. Sort pairs by signature。
  4. Linear scan adjacent equal signatures，输出size至少2的groups。

若D个words，total characters为L，逐word sorting cost约：

O(∑i∣wi∣log⁡∣wi∣)O\left(\sum_i |w_i|\log|w_i|\right)

Pair sorting O(D log D) key comparisons，final scan O(D)。若alphabet很小，可用frequency vector signature把per-word key construction降到O(|w|+alphabet)。

const pairs = words.map(word => ({
  key: [...normalize(word)].sort().join(""),
  word,
}));
pairs.sort((a, b) => a.key.localeCompare(b.key));
const groups = groupAdjacentEqualKeys(pairs);

这就是getting it together sorting：先把problem变成“equal items share key”，再让general sort完成grouping的hard work。

2.9 Implementing an Anagram Program

Unix-style pipeline可拆成two small programs：

  • sign读dictionary，每行输出signature与word。
  • System sort按first field排序。
  • squash扫描adjacent equal signatures并emit groups。

拆分的价值是每段都可独立test，sort复用成熟tool，intermediate representation可直接inspection。成本是text parsing与process I/O；large-scale production可在one process内保留same logical stages。

Test cases需覆盖：

  • Repeated letters：letter与reletter并非anagrams。
  • Case normalization：Tea与eat是否同组取决于contract。
  • Duplicate dictionary entries：deduplicate还是保留必须定义。
  • Empty strings与one-letter words。
  • Non-ASCII combining marks与locale。

2.10 从三个题抽象出的design moves

三个solutions共享一条chain：

  1. Expose invariant：underfull capacity、monotone predicate、permutation、equivalence。
  2. Choose representation：prefix range、ordered interval、ab decomposition、canonical signature。
  3. Apply primitive：partition/count、binary search、reverse、sort。
  4. Lift result：missing prefix、bad card index、rotated vector、anagram groups。
  5. Prove resources：passes、probes、moves、memory与sort cost。

“Aha”发生在step 2到3，但可靠program还需要其余steps。

2.11 Failure modes与边界

  • Missing integer若允许duplicates，bucket raw count可能超过distinct occupancy，underfull proof失效。
  • Signed integer mapping需要定义bit-preserving reinterpretation或offset；不能混用numeric order。
  • Rotation必须normalize d，处理d=0、d=n、n=0和large d。
  • Binary predicate若test有nondeterministic failures，应重复采样或改变model。
  • Signature若仅用sum of character codes，会collision，不是canonical equivalence。
  • External scratch file要处理partial writes、disk full与cleanup。

2.12 Principles

  • 先动手纸上求解three problems，再读solution，训练representation change。
  • Binary search是寻找monotone boundary的pattern，不只是array routine。
  • Simple primitives可通过composition解决surprising problems。
  • Sorting能完成grouping、duplicate detection、canonical clustering与set operations。
  • Pigeonhole principle可把existence proof直接变成algorithm。
  • Algebraic view如gcd cycles能解释为什么in-place permutation正确。
  • A clever transformation必须附correctness equivalence和resource accounting。

2.13 Independent certificate

Missing integer certificate检查chosen prefix每轮record count严格小于capacity，最终value未在input。

Rotation certificate检查output length不变、element multiset不变，并对每个index：

y[j]=x[(j+d) mod n]y[j]=x[(j+d)\bmod n]

Anagram certificate检查every group内signatures equal、不同groups signatures distinct、all dictionary words accounted exactly once。

Property-based tests可随机生成n、d，与copy-based oracle比较rotation；随机删除one universe value，验证missing finder返回absent member；随机shuffle letters，验证signature invariance。

2.14 逐步运行路线

小结

  • Aha Algorithms通过representation change让困难问题调用简单primitive。
  • Three Problems分别是missing 32-bit integer、in-place vector rotation和dictionary anagrams。
  • Underfull prefix与pigeonhole principle让tiny-memory external narrowing可行。
  • Ubiquitous Binary Search寻找monotone boundary，也可定位bad data或regression。
  • Vector Rotation可用three reversals、juggling cycles或block swaps实现O(n) time、O(1) space。
  • Power of Primitives强调reverse、sort和predicate search的可组合性。
  • Anagram Signature把letter-multiset equivalence转成canonical key equality。
  • Getting It Together: Sorting让equal signatures adjacent，linear scan即可分组。
  • Aha insight必须附preconditions、two-way correctness与resource proof。
复习本章（4 题）

讨论

评论区加载中…