Published on

用 Rust 刷 Leetcode 的一點行前建議

Authors

這篇文章想要講什麼？

在此肯定不是想要討論演算法本身。

眾所皆知，Rust 為了兼顧執行期效能與記憶體資料安全性，而立下了相對高門檻的編譯規則，自然限制了演算法的實作手段。然而，刷 LeetCode 或是各種演算法題庫的主要目的，無非是為了訓練個人對於問題情境與演算法的分析連結能力，以及對於選定演算法的實作。Rust 的語言規則使得前者更難達成，強化後者意圖性。

  • 對於初入這類演算題庫者，還是比較建議先使用其它更易用的語言，專注於演算法本身的練習。
  • 如果已有解題經驗，Rust 是作為第 2+ 語言，想籍重新解題以提昇語言熟悉度、但還不熟悉 module system 的情況，可以先考慮專注在生態本身，excercism 上面有些不錯的練習材料。
  • 承上且已熟悉生態的話，希望這篇文章能多少為您減輕學習負擔。

以下內容的實作可以參考我的 repository。

cargo test 是你的好朋友

應該沒有人會否認 unit test 的好處。解題難免 WA，即便是可用的解法，在相同運算複雜度之下，仍可能有編譯或執行期底層細節造成的微妙差異，進而需要一致化的 benchmark 協助我們確認效能。動手解題前先寫好 test suite 會是個好習慣，例如 pXYZ.rs 可能長得像這樣：

/*
Problem XYZ. Problem title
==========================
https://leetcode.com/problems/blah-blah/
Given foo, get bar.
*/

impl Solution {
    pub fn foo_bar(input: InputT) -> OutputT {
        // some implementation
    }
}

pub struct Solution;

#[cfg(test)]
mod tests {
extern crate test;
use super::Solution;

    #[test]
    fn test() {
        assert_eq!(Solution::foo_bar(...), test_data);
    }

    #[bench]
    fn bench(b: &mut test::Bencher) {
        b.iter(|| Solution::foo_bar(...))
    }
}

也別忘了在 lib.rs/mod.rs 加入相關的模組宣告。如此這般，cargo test --lib pXYZ::tests 便能讓測試自動化，每次 WA 新增測資之後持續改善解答，落實 TDD。

認識手上已有的東西

除了 std::collections 裡面的各種容器外，為將答案標準化，LeetCode 預定義了部份常見的資料結構：linked list 與 tree。這邊衍生了兩個問題：

  1. 如何方便地產出比對用的資料結構，以利前述的 test case 設計。總不太可能真的在測資裡面大量手寫 Option、Rc、RefCell、Box 各種嵌套出來的俄羅斯娃娃，真的硬幹下去最後測不過的話，也很難快速確認到底是哪一層測資抄錯、還是演算法解答實作真的有未竟之處。
  2. linked list 的實作品常會撞到資料擁有權規則，這部份我們稍後討論。

市面上已有些 crate 可以幫我們減輕解題以外的負擔，例如 leetcode_prelude 可以輕易定義這樣的複雜 btree 測資：

//       5
//      / \
//     4   8
//    /   / \
//   11  13  4
//  /  \      \
// 7    2      1

btree![5, 4, 8, 11, null, 13, 4, 7, 2, null, null, null, 1]

解題順序

大家入門資料結構時的第一塊入門磚通常是 linked list，也時常作為初入 LeetCode 解題暖身期的目標類題。但如同前節所述，LeetCode 提供的 linked list 實作品是最簡陋的 owned Option<Box<T>>，必須解決嵌套結構下的變數擁有權問題，實作難度已往上跳一級；又，未採用 Rc 的實作在語言層面明示我們，在未踏入 unsafe 之前，無法實作例如 two cursor 等等一邊引用一邊寫入資料的高效能演算法實作，本可以只迭代一次的情境可能被迫多次迭代。身為 rustaceans，豈能容忍這種效率浪費？個人的建議是：

  • 從累積語言實作經驗的觀點，先去刷其它種類的題目，把 linked list 相關題目的優先度放低，能自在玩弄變數所有權規則之後再回頭解決這部份。越級打怪對學習效率的影響仍是弊大於利。
  • 為了語言規則而棄絕 unsafe 說實在也並不現實，畢竟這也是語言的一部份，練完演算法的實戰場景仍可能會為了 FFI 等等需求被迫進入 unsafe。真的要開始練習這部份之前，至少先把黑魔法入門書《The Dark Arts of Unsafe Rust》掃過一遍，保護別人也保護自己，而後開始善用 unsafe 帶來的自由性來解決我們的演算法效能。
Discuss on Twitter