Rust 速通 LeetCode 之后

花了 3 天时间刷完了 LeetCode 75¹，然而 Top Interview 150² 却花了足足 2 周，链表是 Rust 里永远的神，古人诚不我欺。

算是给 The Rust Programming Language 的期末大作业吧。

从刷题的角度来说，Rust 真的是一个很糟糕的选择，为什么要来为难自己呢？

我不认为 LeetCode 对于 engineer 而言有多么重要，刷题的习惯很大程度上只是出于自己的兴趣。
但 LeetCode 同样也不是完全没有意义，这是一个平衡的问题。如果因为一些场合过于强调刷题，从而心生厌恶以至于完全否定算法，那么也自然拒绝了算法好的一面。

我认为刷题其实是 2 个过程，一个是对具体问题的建模，拆分、映射成已知的子问题；另一个是用代码对思维的准确表达。而这 2 个过程有着相同的内核在驱动 —— 精简，思维的精简，去除冗余步骤；代码的精简，关注执行的效率。

所以刷题其实十分适合练习一个新语言。在这个过程中探索常用的 API，以及它的不同之处。比如了解到 Rust 中 BinaryHeap 是最大堆，而最小堆的实现惯例是用 Reverse 包装内部的值，相比于手动取反，表义更清晰更不容易出错。

在对代码精简的过程中，也能训练如何以这种语言的方式来思考。用 Python 来作为反面教材，其实 Python 有非常多的糖，写起来可以十分优雅，但是很多人并没有利用这些特性，代码看起来像 C。当然如果朴素的代码连村口老太太都能看懂，也是一种优点。但是语言的特性其实相当于一种 pattern，这种 pattern 是社区用脚投票的结果，这么写有什么什么好处，所以我们鼓励做，这是一种在实践中择优的结果。遵从同样的 pattern，也更不容易出错。

什么是 Rust 中的编程范式呢？我们用二叉树中 2 个节点的最低公共祖先为例。一种解法是求得 node 到 root 的路径，然后找第一个相同的 node：

 1let mut p_path = vec![7, 2, 5, 3];
 2let mut q_path = vec![1, 4, 2, 5, 3];
 3let mut res: i32 = i32::MIN;
 4loop {
 5    match (p_path.pop(), q_path.pop()) {
 6        (Some(a), Some(b)) if a == b => res = a,
 7        _ => break,
 8    }
 9}
10res

我们在这里用 Rust 中的 pattern match，只用考虑 2 个 Vec 末尾的值相同的情况，不用再去关心 Vec 是否为空了。

这里说的范式也不是局限于语言层面的，函数式编程其实是这方面的代表，每一个 operator 都是一种范式，同样是上面的例子我们在 Rust 中用 iterator 怎么表示呢？

1let p_path = vec![7, 2, 5, 3];
2let q_path = vec![1, 4, 2, 5, 3];
3iter::zip(
4    p_path.iter().rev(), //
5    q_path.iter().rev(),
6)
7.map_while(|(a, b)| if a == b { Some(*a) } else { None })
8.last()
9.unwrap()

两个 Vec 从末尾遍历，找到最后一个相同的 item，这就是上面这段代码表达的意思。不用手动更新变量去关注如何实现逻辑，只用像搭积木一样组装逻辑。但 Rust 相比于其它语言可能更不适合函数式编程，这就是后文要聊到的另一个话题了。

学习新语言中，这种对于范式的探索并不是「茴香豆几种写法」的问题，如果一种写法更高效、更不容易出错，为什么不用呢？这其实是很多编程书籍中经常出现的 idiomatic 这个词了。

作为一名 rustacean wannabe，当然是喜欢 Rust 的，但是用来刷题真的痛苦，Python 中的 5 分钟在 Rust 可能就是 1 小时了。所以 Rust 刷题糟糕在哪里呢？

有一部分原因是 LeetCode 设计得不好导致的。

所有的 int 输入输出都是 i32 类型，尽管有些实际表示 size、count，作为 index 时总要转成 usize，输出再转成 i32。

在 LeetCode 数据结构的定义上，我们用链表和二叉树举例：

 1#[derive(PartialEq, Eq, Clone, Debug)]
 2pub struct ListNode {
 3    pub val: i32,
 4    pub next: Option<Box<ListNode>>,
 5}
 6
 7#[derive(Debug, PartialEq, Eq)]
 8pub struct TreeNode {
 9    pub val: i32,
10    pub left: Option<Rc<RefCell<TreeNode>>>,
11    pub right: Option<Rc<RefCell<TreeNode>>>,
12}

在此我们不讨论 Box<T> 和 Rc<RefCell<T>> 哪一种更合适，这其实是 API 准确性和易用性之间的取舍，如果链表的定义也用 Rc<RefCell<T>> 这种方式，Rust 中的链表可能就不难了，我也确实用这种方式实现的 LRU Cache 双向链表。

但是在两个等价的问题上，LeetCode 做出了不同的选择，这是一种设计理念的不一致，更不要说还有下面这个离谱的输入类型：

1// 114. Flatten Binary Tree to Linked List
2pub fn flatten(root: &mut Option<Rc<RefCell<TreeNode>>>) {}

给还不了解 Rust 智能指针的读者解释一下：

• Option<T> 是一个 Enum，有 Some(T) 和 None 两种变体

• Rc<T> 是一个引用计数指针。
  rc.clone() 只是引用计数 +1，这就是为什么新手们的二叉树都是一路 clone 走到 AC 的，因为真的好用效率也不算差。

• RefCell<T> 这个指针比较有意思。
  Rust 的 borrow 规则实在是太严格了，如果多个地方都可能修改，即使保证了一个时刻最多只有一处在修改，用现有的规则也不好写，所以有了 RefCell 这个 immutable 的类型，支持内部可变，即 Interior Mutability。至于 borrow 冲突什么的，runtime 遇到了再 panic 吧。

  • refCell.borrow() 获取 readonly 的 ref<T>，
  • refCell.borrow_mut() 获取 mutable 的 refMut<T>。

所以上面 API 中输入的 &mut 就完全没有意义，我们并不是用可变引用这种方式修改二叉树的。

上面 ListNode 没有实现 cmp::PartialOrd 和 cmp::Ord，不支持排序，我们需要自己实现这些 Trait，才能在必要的时候扔进 heap 里。

TreeNode 没有实现 hash::Hash 所以不能作为 Key 扔进 HashMap，很长一段时间我都不知道怎么对这样一个实际 mutable 的 node 做哈希，难到 Rust 的二叉树用不了 DP 了吗？直到我想出这么个鬼点子：

1trait Hash {
2    fn hash(&self) -> usize;
3}
4
5impl Hash for Rc<RefCell<TreeNode>> {
6    fn hash(&self) -> usize {
7        Rc::as_ptr(self) as usize
8    }
9}

Rc 随便 clone 但是内部的 RefCell 是唯一的，我们用这个 RefCell 的地址做 ID 吧。

类似这些对 struct 的扩展，实际上是可行的，但是理论上应该做吗？
对 struct 实现 Trait 的要求是，这个 struct 和 Trait 至少有一个是 local 的，为了避免多处有实现的冲突。
我应该把 ListNode、TreeNode 作为 local struct 吗？我不知道啊，对我而言他们都是预定义的结构。

LeetCode 对不同的语言都支持第三方 library³，但是 Rust 没有 BigInt。
是的，我没法用数组表示二叉树了。

但 LeetCode 尽力了，更多的是 Rust 自身设计导致的不适合刷题，因为编译器暴露了太多细节给 engineer。

一位学习小语种的朋友曾经和我说，不同语言不太会影响思考问题的方式，自然语言仍然是一个工具，重要的是背后表达的意思。

Coding 可不是这样的，engineer 需要在乎表达的这个过程，这个过程的起点是脑中的逻辑，终点是编译出的 binary 运行出期望的结果。对于编译器扔出来的这么多 error，看似是给逻辑表达的磕磕绊绊，但是无关好与坏。这其实是一个思考维度的问题，你在用代码表达脑中的逻辑，当下的重点是逻辑的正确性，那么代码执行的细节，你希望关注到什么程度？

这是一个关于抽象程度的平衡问题。

仍然用 Python 举个例子，在 Python 中我可以无脑用数组的方式序列化二叉树，考虑到这个数组可能过于稀疏效率太低，可以用 dict 来表示。当二叉树退化成单链表的形式，末尾的 node 对应的 key 就是 2 ^ N 了，题目中约束了 node 数量是 10 ^ 4 个。即使我在 Python 中写出这样的代码仍然可以 AC：

 1def serialize(self, root) -> str:
 2    if not root:
 3        return ""
 4    deque = Deque([(1, root)])
 5    map = {}
 6    while deque:
 7        for _ in range(len(deque)):
 8            i, n = deque.popleft()
 9            map[i] = n.val
10            if n.left:
11                deque += [(2 * i, n.left)]
12            if n.right:
13                deque += [(2 * i + 1, n.right)]
14    return ",".join(f"{k}:{v}" for k, v in map.items())

这里的 index 最大会是 2 ^ 10000，用自然语言写下来是长度 3000+ 的数字，然而 Python 贴心地做了所有转换，一个没有 overflow 的世界。

但这些信息，是 engineer 应该知道，也应该考虑的。

在 Rust 中甚至没办法把 f64 扔进 BinaryHeap，因为 float 并不支持完整空间内比较大小。是的，因为定义了 f64::NAN 这种东西，标准就是如此，所以要手动把 f64 包一层来自定义行为。

虽然 Rust 的编译器过于严格，但也可以从另一个角度说它十分地贴心，在 TRPL 中提到了一个概念是 Zero Cost Abstraction，意思是不论写出什么风格的代码，不论是 for-loop 还是 iterator，经过编译器洗一遍都是一样的，没有任何 runtime 的额外成本。很多人不满意 Rust 编译速度过慢，因为编译器做的事情真的太多了，甚至提供了 opt-level 定制编译优化的选项。

Rust 十分地鼓励 iterator 模式，或者说 Clippy 近乎狂热地在鼓励，但 Rust 在函数式编程上，甚至比别的语言有更多的限制。我们永远写不出这样的代码：

1let mut v = vec![0, 1, 2, 3, 4];
2(0..v.len()) //
3    .filter(|&i| v[i] % 2 == 0)
4    .for_each(|i| v[i] *= -1);
5            // ^ cannot borrow `v` as mutable
6            // because it is also borrowed as immutable

但从另一个角度，我们也可以说 Rust 是函数式编程的完美语言！因为 borrow rule 强迫我们不要修改中间状态，如果要修改状态，请在 iterator 结束的地方修改，不论是 reduce、fold、for_each。
这恰恰是函数式编程的灵魂之一 —— 纯函数。

TRPL 在鼓励我们用 iterator，Clippy 也一直建议用 iterator 的方式来写，但是 std::iter 中可用的 operator 还是有点少。对于二维数组我十分喜欢的一个 Python 写法是这样的：

1def foo(matrix: list[list[int]]):
2    R, C = len(matrix), len(matrix[0])
3    for r, c in product(range(R), range(C)):
4        pass

但 Rust 的 std::iter 中并不存在这样一个 product，如果真的要以函数式风格来写：

1let (row, col) = (matrix.len(), matrix[0].len());
2(0..row)
3    .flat_map(|r| (0..col).map(move |c| (r, c)))
4    .for_each(|(r, c)| {});

就十分的不优雅，于是回归庶民写法，啥事儿没干呢先来 2 层嵌套：

1let (row, col) = (matrix.len(), matrix[0].len());
2for r in 0..row {
3    for c in 0..col {
4
5    }
6}

或者用 itertools 这个 crate：

1use itertools::iproduct;
2
3fn main() {
4    let rows = 9;
5    let cols = 9;
6    for (x, y) in iproduct!(0..rows, 0..cols) {
7
8    }
9}

Rust 的 std 真的很小，看完 TRPL 甚至觉得整个语言都是在围绕 borrow rule 做的一个思维游戏，那些 std 没有提供的机制，鼓励大家去探索社区第三方 crate。

当然 LeetCode 永远不会探索这些 crate，它只用提供必须的依赖，没有动机去鼓励用户写出更精简优雅的代码。

所以这么多磕磕绊绊，为什么还要用 Rust 来玩 LeetCode 呢？

What’s life without whimsy?
不為無益之事，何以遣有涯之生。

—— Sheldon

因为真的很好玩啊！