Algorithm

本周选择的算法题是：Snapshot Array。

struct SnapshotArray {
    snapshots: Vec<Vec<(i32, i32)>>,
    snap_id: i32,
}

/** 
 * `&self` means the method takes an immutable reference.
 * If you need a mutable reference, change it to `&mut self` instead.
 */
impl SnapshotArray {
    fn new(length: i32) -> Self {
        Self {
            snapshots: vec![vec![(0, 0)]; length as usize],
            snap_id: 0
        }
    }
    
    fn set(&mut self, index: i32, val: i32) {
        if self.snapshots[index as usize].last().unwrap().0 == self.snap_id {
            self.snapshots[index as usize].pop();
        }
        self.snapshots[index as usize].push((self.snap_id, val));

    }
    
    fn snap(&mut self) -> i32 {
        self.snap_id += 1;
        self.snap_id - 1
    }
    
    fn get(&self, index: i32, snap_id: i32) -> i32 {
        let res = self.snapshots[index as usize].binary_search(&(snap_id, i32::MAX));
        match res {
            Ok(pos) => self.snapshots[index as usize][pos].1,
            Err(pos) => self.snapshots[index as usize][pos - 1].1
        }
    }
}

/**
 * Your SnapshotArray object will be instantiated and called as such:
 * let obj = SnapshotArray::new(length);
 * obj.set(index, val);
 * let ret_2: i32 = obj.snap();
 * let ret_3: i32 = obj.get(index, snap_id);
 */

Review

Rust Compiler Development Guide

一份官方指南，用于了解 Rust 的编译器设计。Rust 的整体编译器架构大致分为这么几个过程：

Lexing: 把源程序解析为 token 流
Parsing: 把 token 流转换为 AST（Abstract Syntax Tree），这其中包括宏扩展、AST 验证、名称解析和早期静态检查
HIR lowering: 将 AST 转换为高级中间表示 HIR（High-level IR），这是一种更适合编译器处理的抽象语法树表示。此过程还涉及一些语法糖的转化，如循环和 async fn。然后使用 HIR 进行类型推断、特征解析和类型检查
MIR lowering: 将 HIR 转换到 MIR（Middle-level IR），用于借用检查和其他重要的基于数据流的检查，例如检查未初始化的值。在此过程中还构建了更具类型信息的类型化 HIR（THIR），THIR 主要用于模式匹配检查
Code generation: 主要基于 LLVM 进行代码生成，同时也支持 Cranelift

为什么要了解 Rust 的编译器？因为 Rust 编译器在 Rust 这门语言中起着至关重要的作用，也是 Rust 与其他语言区别的原因和优势所在，比如这些重要方面：

内存安全和线程安全：Rust 的最大特点之一是内存安全和线程安全。Rust 的编译器通过所有权、借用和生命周期等概念，对代码进行静态分析和验证，以确保代码在编译期间不会出现数据竞争、空指针解引用和其他常见的内存错误
零成本抽象：Rust 的编译器对高级抽象的处理非常高效。它利用了各种编译器优化技术，如内联、零拷贝、零运行时开销的函数调用等，以减少高层抽象带来的性能损失。这使得开发者可以使用诸如高级数据结构、迭代器、模式匹配等抽象，而无需担心性能问题
领域特定语言（DSL）：Rust 支持通过宏和语法扩展机制创建领域特定语言（DSL）。这使得开发者可以根据特定领域的需求创建专用的抽象，以提高代码的可读性和可维护性，而不会引入额外的运行时开销

由于 Rust 编译器在保证内存安全、生成优化的机器码、进行静态类型检查、处理错误和异常、以及支持语言扩展方面发挥着关键作用，它是 Rust 语言的核心组件之一，了解 Rust 编译器的设计和工作原理有助于深入理解 Rust 这门语言，并能够更好地利用其安全、高效和灵活的特性进行软件开发。

Tip

一个英语聊天机器人: Samantha，可用于学习口语。

分享最近看的一本书

不知不觉这已经是第 200 篇 ARTS 了，第一篇始自 2019-06-06-ARTS #1，刚好 4 年时间，这 4 年不敢说认知有多少提升，但坚持 ARTS 对我的帮助是显而易见的，阅读书籍、评论文章、参与讨论，毫无疑问，接触新观点是促进认知提升的有效途径，具体到 ARTS 里：

Algorithm，每周至少做一个 Leetcode 的算法题。主要是为了编程训练和学习。如果不训练看再多的算法书，依然不会做算法题
Review，阅读并点评至少一篇英文技术文章。主要是为了学习英文，如果英文不行，基本上无缘技术高手
Tip，学习至少一个技术技巧。主要是为了总结和归纳在日常工作中所遇到的知识点
Share，分享一篇有观点和思考的技术文章。主要是为了建立你的影响力，能够输出价值观

ARTS 的动机很清晰，通过积极主动地学习和获取新知识，不断扩展思维边界和认知领域，做起来也并不难，只需要持之以恒学习即可。

很遗憾，发起 ARTS 的大佬已于上月离开：

但这份洞察我将持续执行下去，我依然希望能在这个领域取得更深入的理解和见解。

回到本周分享的书，是一本关于上古历史的书：翦商。

它讲述了商亡周兴的历史巨变，也记录了人祭被革除的过程，背后通过上千年的大量考古学和古文献资料的相互佐证，为读者呈现出了一个立体的王朝印象。拿我自身来说，《翦商》中提到的盘龙城就发生在我的故乡湖北，离我老家也就 100 公里吧，只知道它是古代城市遗址，有一些文化遗存，出土过玉器、石器等文物，可能对中国古代文明演变的理解提供了线索和参考。但不读这本书，永远不知道这块儿土地到底曾经发生过什么事，比如原来占据盘龙城据点的商人贵族曾是放弃人祭的先锋，也影响了商朝的政治格局。

商代的社会组织、文化信仰、社会习俗远超过了现代人的理解范畴，如果你对历史感兴趣，对这些话题感兴趣：

神权的更迭
商代的扩张和现代化能力
献祭、吃人的恐怖 “传说”
隐忍含蓄的生存之道
华夏文明的转变
《易经》到底是干嘛的

那这本书会帮你填上记忆空白的部分，不过需要提醒一下，它不是一本有趣的书，但它一定是本能颠覆固有观念的书。

Algorithm

Review

Tip

Share

分享最近看的一本书