Review

很難通過(guò)某種單一的方式，就能get到所有Rust技能，學(xué)習(xí)的方式方法要多樣化：

• 循序漸進(jìn)的系統(tǒng)性學(xué)習(xí)（內(nèi)存管理->類型系統(tǒng)->所有權(quán)）
• 主題學(xué)習(xí)（異步、宏）
• 交流學(xué)習(xí)（開發(fā)者大會(huì)、社區(qū)）
• 刻意練習(xí)（LeetCode）

剛剛結(jié)束的首屆Rust China Conf 2020就是一種交流學(xué)習(xí)的方式。Rust中文社區(qū)采用直播并提供視頻回放，為所有Rustacean提供了絕佳的、寶貴的學(xué)習(xí)資料。

本篇回?cái)]一把《淺談Rust在算法題和競(jìng)賽中的應(yīng)用》，琳瑯滿目的特性和應(yīng)用，讓人愛(ài)不釋手。

Speaker: Wu Aoxiang (吳翱翔)

視頻：Day2 ，03:54:00~04:20:00

1 std::iter::Iterator::peekable

很實(shí)用的迭代器能力，標(biāo)準(zhǔn)庫(kù)的注釋如下：

Creates an iterator which can use [peek](https://doc.rust-lang.org/std/iter/struct.Peekable.html%23method.peek) to look at the next element of the iterator without consuming it.

fn peekable(self) -> Peekable<Self>

let xs = [1, 2, 3];
?
let mut iter = xs.iter().peekable();
?
// peek() lets us see into the future
assert_eq!(iter.peek(), Some(&&1));
assert_eq!(iter.next(), Some(&1));

2 ?的Option解包能力的應(yīng)用：LeetCode 7 整數(shù)反轉(zhuǎn)。

impl Solution {
    pub fn reverse(mut x: i32) -> i32 {
        || -> Option<i32> {
            let mut ret = 0i32;
            while x.abs() != 0 {
                ret = ret.checked_mul(10)?.checked_add(x%10)?;
                x /= 10;
            }
            Some(ret)
        }().unwrap_or(0)
    }
}

3 std::iter::Iterator::fold的應(yīng)用：LeetCode 1486 數(shù)組異或操作

impl Solution {
    pub fn xor_operation(n: i32, start: i32) -> i32 {
        (1..n).fold(start, |acc, i| { acc ^ start + 2*i as i32 })
    }
}

4 std::net::IpAddr的應(yīng)用：LeetCode 468 驗(yàn)證IP地址

IpAddr是個(gè)枚舉類型，能通過(guò)String::parse直接進(jìn)行解析。以下PPT上的代碼并不能通過(guò)，所以我猜講者只想給出一個(gè)算法框架方便做演示。

use std::net::IpAddr;
?
impl Solution {
    pub fn valid_ip_address(ip: String) -> String {
        match ip.parse::<IpAddr>() {
            Ok(IpAddr::V4(_)) => String::from("IPv4"),
            Ok(IpAddr::V6(_)) => String::from("IPv6"),
            _ => String::from("Neither"),
        }
    }
}

添加檢查后可以通過(guò)測(cè)試，代碼如下?？梢?jiàn)標(biāo)準(zhǔn)庫(kù)對(duì)IP地址的合法性還是比較寬容的。

use std::net::IpAddr;
?
impl Solution {
    pub fn valid_ip_address(ip: String) -> String {
        match ip.parse::<IpAddr>() {
            Ok(IpAddr::V4(x)) => {
                let array: Vec<Vec<char>> = ip.split('.').map(|x| x.chars().collect()).collect();
                for i in 0..array.len() {
                    if (array[i][0] == '0' && array[i].len() > 1) { return String::from("Neither"); }
                }
                String::from("IPv4")
            },
            Ok(IpAddr::V6(_)) => {
                let array: Vec<Vec<char>> = ip.split(':').map(|x| x.chars().collect()).collect();
                for i in 0..array.len() {
                    if array[i].len() == 0  { return String::from("Neither"); }
                }
                String::from("IPv6")
            },
            _ => String::from("Neither"),
        }
    }
}

5 Rust調(diào)用C函數(shù)

調(diào)用C函數(shù)的能力，使得Rust的能力范圍又?jǐn)U展了。

extern "C" {
    fn rand() -> i32;
}
?
fn main() {
    let rand = unsafe { rand() };
    println!("{}", rand);
}

6 String零開銷提供數(shù)組訪問(wèn)：std::string::String::into_bytes

從源碼來(lái)看，String提供字節(jié)數(shù)組訪問(wèn)，簡(jiǎn)直不費(fèi)吹灰之力。在ASCII范圍的場(chǎng)景（大多數(shù)LeetCode字符串題目），每個(gè)字節(jié)通常對(duì)應(yīng)一個(gè)拉丁字符，CRUD都非常方便。

源碼如下：

This consumes the String, so we do not need to copy its contents.

#[inline]
#[stable(feature = "rust1", since = "1.0.0")]
pub fn into_bytes(self) -> Vec<u8> {
    self.vec
}

需要注意的是，如果字符串涉及到國(guó)際化的時(shí)候，一個(gè)字節(jié)可能已經(jīng)不再能映射一個(gè)字符了（比如中文字需要多字節(jié)存儲(chǔ)），此時(shí)直接在字節(jié)層面進(jìn)行CRUD都是非常危險(xiǎn)的。

7 飽和運(yùn)算（防溢出）

各類型的整數(shù)和浮點(diǎn)數(shù)都有saturating運(yùn)算系列，以u(píng)8減法為例：

pub const fn saturating_sub(self, rhs: u8) -> u8

assert_eq!(100u8.saturating_sub(27), 73);
assert_eq!(13u8.saturating_sub(127), 0);

講者在分析LeetCode 《1512 好數(shù)對(duì)的數(shù)目》一題中應(yīng)用了該方法。但是就該題目來(lái)說(shuō)，本文給出一種更加簡(jiǎn)單的解法，一次迭代即可。

同時(shí)講者還使用了cargo bench，來(lái)得到該方法納秒級(jí)的運(yùn)行時(shí)間，比LeetCode的毫秒級(jí)要精確1000倍了。

這里需要注意的是，盡管Rust 2018已經(jīng)放棄了extern crate，還是需要使用extern crate test來(lái)引入test "sysroot" crates。這是例外。

#![feature(test)]
extern crate test;
?
pub fn num_identical_pairs(nums: Vec<i32>) -> i32 {
    let mut map: [i32;101] = [0;101];
    nums.into_iter().fold(0, |mut acc, x| { 
        acc += map[x as usize];
        map[x as usize] += 1;
        acc })
}
?
#[cfg(test)]
mod tests {
    use test::Bencher;
    use super::*;
    #[bench]
    fn bench_func(b: &mut Bencher) {
        b.iter(|| {
            num_identical_pairs(vec![1,2,3,1,1,3,1]);
        });
    }
}

輸出：

PS D:\Project\rust_II\Language\r10_64_benchmark> cargo bench
    Finished bench [optimized] target(s) in 0.02s
     Running target\release\deps\r10_64_benchmark-8eb89c8ab9ad043d.exe
?
running 1 test
test tests::bench_func ... bench:          81 ns/iter (+/- 74)
?
test result: ok. 0 passed; 0 failed; 0 ignored; 1 measured; 0 filtered out

8 善用cargo clippy

使用clippy，多多益善。cargo clippy是CI友好的，如果你是眼睛里容不下warning的人，可以設(shè)置使任何warning導(dǎo)致編譯失?。?/p>

cargo clippy -- -D warnings