duangsuse::Echo

#China #book #school #life 🏫📔 最近从本校的物理老师处得赠了一本 #Algorithm 算法书《算法》 Algorithms in C++ I-IV: Fundamentals, Data Structure, Sorting, and Searching by Robert Sedgewick
https://book.douban.com/subject/1116599/

这本书甚是有价值，不仅仅在它的三观、逻辑、数学、图示、新奇、编程实现上，我就不谈它的价格相比之下实在是不高了，质量上，高德纳(Donald Knuth)的学生，算法，不是盖的。

包括这本书的作者据称都是刚开始写 C++，一个离开计算机都能编程的人，又是计算机科学研究者、算法研究者…… emmm……

我从这本书（我第一次见到用 TeX 排版得这么好看的书，前一次是看 Kanru Hua 的信号处理(signal processing)论文和期刊切片，排版带内联的，虽然我没看懂）的代码块里了解到了原来还有人和我一样不那么遵循所谓的『代码风格』……
他们说，他们努力设计出了一套简洁、可移植的 C++ 编程模板（这里不是 template<> 的意思）。
尽管我不是很喜欢数学的表达方式，我还是得承认我实在找不出一点茬子了 — 比起我从其他书里，尤其是 LLVM Cookbook — 那简直无法入眼的 C++ 代码、类 — 那哪能叫设计啊？分明就是无序杂乱的方法定义！即便能够工作，却怎么也不可能达到 Algorithms 一书示例代码的层次。

虽然我的智商不高所以能实现的东西不多，但我觉得，我的代码依然相对而言较甜，而 Algorithms 一书的代码则是带点数学薄荷的咖啡，醇香微苦，不过 — 都从不油腻、不会拖泥带水让人无从入眼。

这本书里，我学（且暂时只学到）了快速查找、合并查找（不带权重和压缩的）（因为我智商低，而且最重要的是，我有别的事还要完成……）

#include <iostream>
const size_t N = 1000;
int main() { unsigned up[N], b, c; size_t it;
  while (cin >> b >> c) {
    auto a = up[b]; // R(a, b): up[a] = up[b]
    if (up[c] == a) continue; // c R b
    for(it=0; it<N; it++)
      if (up[it] == c) up[it] = a; // R(it, c)
    cout << b << " " << c; } }

其中的 unsigned up[N]; 也可以被泛化为 std::map<unsigned, unsigned>

这是快速查找（也可以作为实现集合数据结构的一种算法），怎么快速法呢？
是解决『传递性问题』的一种算法，它的合并操作速度较慢（所以也叫慢合并），不过判断速度很快。
我们知道，对于一个 M 个输入，它都只需要 O(1) 的时间复杂度来判断是否联通，可在更新时每次都要执行 O(N·M) 次比较 (==) 运算。

这个问题就是给你一堆『对』，如果它是新的，输出它，否则就继续下一个（C++ iostream 扫描器）。
因为快速查找(quick search)/合并(merge search)有 up（父树）所以也称树状数组。

1 2
2 3
4 0
0 1 — 4-0-1-2-3

我们的输入上有一个性质(property)：

forall a b c. a R b, b R c => a R c

我们管叫逻辑断言的传递性(transitive)。
1 R 2
2 R 3 => 1 R 3
4 R 0
0 R 1 => 0 R 2, 0 R 1 R 2 R 3 且 3 R 4
（因为 R(a=1, b=2, c=3) 得证 1 R 3 且 R(a=0, b=1, c=4) 得证 0 R 4）
细心的同学可能会觉得奇怪：假如我有 b - a; d - a，他们在树上不是一个树支的，可是却被认为在一起了。
其实这很正常：传递性关系是对称(symmetric) 的，也就是说

forall a b. a R b ≡ b R a

换句话说，这实际上不是一棵树，是一个树状的集合，因为集合关系 (a `是同集` b) 也具有传递性，即 『小鸡是小鸭同集、小鸭是小鹅同集，小鸡也是小鹅同集』。
至于为什么像是树，这是因为集合传递性就是树状的

问题是：这不是一个逻辑问题啊，
上面的实现被称为快速查找，你可以注意到它把离散的 a R b; b R c 传递来了，至于为什么没有 a，是因为我们的实现方式是 unsigned up[N]; 数组，如果我们用的是 strcut { unsigned *up; } 就也还是一样……
我不会算法可视化，所以没有图（不像那个，我艹还是算法可视化专业研究者，计算机图形学基础啊。

至于合并查找（我不知道两颗树的权重算法和路径压缩该怎么做）（题外话，我自己设计了一个类似 Dijkstra 的 DFS 算法当然还没实现，关于狄克斯特拉算法我也自己想了6个细节，只等着写文。）

它就是

size_t i, j;
for (i=0; up[i] != i; i = up[i]);
for (j=0; up[j] != j; j = up[j]);
if (i == j) continue; // common ancestor
else up[i] = up[j]; // merge ancestor

也就是说，找到 a R b R c R … 里的这个 a，它的 parent 绝对是它自己，它就是最大的太爷爷。
（准确的说也没啥 parent 不 parent 的，一切都是临时的，比如我们每次把 c1 的 up 都置为 a，实际上只是需要一个『最大』的集合加入。换句话说，如果 c1 是以后被另一个 up=a 的 d 关联起来的，都一样）
如果他们有同一个太爷爷（也就是说，之前 up[x] = a c1 R a 的那种）
就是 up[a] = up[b] = up[c] 的情况（有关系的，我们都应用了相等关系的传递性，和传递性伴生的对称性）

就像 Rc(refcount GC)、hashmap 一样，树状数组也是只记录部分信息的，就是传递的关系，而不实际保持「继承」关系，所以才能有优化啊（要不然你只能 xs.filter { it.first == this }.exist { it.second == x } 递归下去[因为这一个表达式应该被叫做『存直接链接』]，就不好了）（当然，也可以 dfs 或者 bfs。）

至于那个 O(...) 呢，书上也有在 Fundamentals 一节讲到，定义是：

对于所有 c、N0，若有 g(N) 使得对于所有 N0 < N，g(N) < c·f(N) 成立，则说 g(N) 是 O(f(N))。

就是说数学函数的变化率啦，数学喜欢 \lim_{n\to\infty}{\frac{a}{b}} 趋近于 0 表示 b 渐进地大于 a 什么的……

O(g(n)) = {f(n):存在正常量c和n0，使得对所有n>=n0,有0
唉，没一个讲清楚的，这些数学家真的会自然语言吗？真的知道啥是定语啥是状语吗？
看不懂的话，自己用反对称套一下给自己一个主语，不然算了，毕竟数学不是给常人用的。

书上还有讲状态机、形式化文法等常见计算机科学/算法问题的，不能不说是丰富丰富再丰富。
谈到算法：数组（二分查找、选择排序、冒泡排序、合并排序）、链表、递归（尾递归）、分治算法（快速排序）、哈希表、图（无向、有向无环、广度优先搜索bfs、深度优先搜索dfs、狄克斯特拉算法）、动态编程DP、线性规划、傅里叶变换、二项式、随机化、状态机、形式化文法、二分查找树BST、跳跃链表SkipList、哈希算法、非对称密钥系统……

现在时间比较不充裕，我只能暂时先写这么多。
尽管在学校里我几乎没读这本书，我还是非常感谢赠我这本书的老师，要不然，或许我自己是找不到它的，谢谢你！
更详细的书评/笔记等我以后，会慢慢发出来、写成文集。
但愿我能够理解那些烧脑精妙的算法、但愿我能设计出我所需要所有简单的算法、但愿不论我走到多远、多高，都能够保持不卑不亢，也不会忘记曾经那个真心爱着技术的自己。

Douban

算法Ⅰ~Ⅳ(C++实现):基础、数据结构、排序和搜索 (豆瓣)

图书算法Ⅰ~Ⅳ(C++实现):基础、数据结构、排序和搜索介绍、书评、论坛及推荐

28 viewsduangsuse /'dʊɔːŋ sjuːz/ | [⃪PLD, FPλ], edited 11:15