性能优化方法和实例
方法
- 使用合适的数据结构。例如数组比向量更快
- 减少内存分配。多使用借用而不是复制整个数据结构。
- 尽可能选用栈上分配的数据结构，而不是堆上的
- 栈上分配的数据结构：基本数据类型（整数、浮点、布尔）、数组、元组
- 堆上分配的类型：动态大小数据结构(Vec、String)，Box，Rc，Arc
- 预分配内存。例如
Vec::with_capacity防止频繁 realloc - 内存分配到静态区域，使用 static 声明静态变量。
- 考虑并发
- 编译器优化
- unsafe模块
- 使用对象池。场景：对象的创建成本大，且需要频繁创建。功能：对象使用后进入对象池供下次使用，而不是直接销毁。
一些类型：
Vec<T>，栈上存放三元组，堆上连续分配数据Box，在堆上分配数据、非连续的
字符串中取数
结论：
- 用 bytes 时间消耗为 chars 的20%
- 用 bytes 有风险，遇到中文可能 Panic，且两者功能不同
代码：
let start = Instant::now(); // 记录开始时间点
let mut text1 = text.chars();
for i in 0..1000 {
let a = text1.nth(500);
}
let elapsed = start.elapsed(); // 计算时间间隔
let elapsed_ms = elapsed.as_secs() as f64 * 1000.0 + elapsed.subsec_nanos() as f64 / 1_000_000.0; // 转换为毫秒
println!("用时 {}", elapsed_ms);
// 0.05 ms
let start = Instant::now(); // 记录开始时间点
let text1 = text.clone().into_bytes();
for i in 0..1000 {
let a = text1[500];
}
let elapsed = start.elapsed(); // 计算时间间隔
let elapsed_ms = elapsed.as_secs() as f64 * 1000.0 + elapsed.subsec_nanos() as f64 / 1_000_000.0; // 转换为毫秒
println!("用时 {}", elapsed_ms);
// 0.01 ms
从 u8 创建 String
&str比String更快from_utf8_unchecked比from_utf8快。后者会检查 utf-8 编码，不合法的 utf-8 会 Panic
let a: &[u8; 3] = &[65, 68, 66];
// 以下4种方式时间消耗从高到低
let b1 = String::from_utf8(a.to_vec()).unwrap();
let b3 = unsafe { String::from_utf8_unchecked(a.to_vec()) };
let b2 = std::str::from_utf8(a).unwrap();
let b4 = unsafe { std::str::from_utf8_unchecked(a) };
// 时间消耗分别是 `4.542µs, 375ns, 84ns, 42ns`
Vec 的 get 与 取数
vec.get(idx)会检查 idx 是否越界，并返回一个 Optionvec[idx]直接返回结果，如果越界则会 Panic- 性能差别：
vec[idx]的时间消耗是vec.get(idx)0.1 倍（单次的结果，循环测试被编译器优化不好测）
常用代码
指向函数的“指针”
fn fn_add(a: i32, b: i32) -> i32 {
return a + b;
}
fn fn_sub(a: i32, b: i32) -> i32 {
return a - b;
}
// 可以把他们放到一个 arr 里面，前提是 这些函数的输入/输出的数量和类型都要一样
let fn_arr = [fn_add, fn_sub];
// 可以先定义它，在之后的代码具体赋值
let fun_op: fn(i32, i32) -> i32;
let idx = 0;
fun_op = fn_arr[idx];
println!("{}", fun_op(1, 2))
“指向对象的指针”
struct ClsOpt {
idx: i32,
func: fn(i32, i32) -> i32,
}
lazy_static! {
static ref obj_add: ClsOpt={
let idx=1;
ClsOpt{
idx,
func: fn_add
}};
}
fn main() {
println!("Counter: {}", (obj_add.func)(1, 3));
}
关于报错
一、不要使用 unwrap
// 一段不合法的 utf-8 编码，可能导致报错
let a: [u8; 3] = [230, 230, 220];
// let a: [u8; 3] = [97,98,99];
let val = String::from_utf8(a.to_vec());
// 推荐做法
match val {
Ok(x) => println!("{}", x),
Err(err) => println!("{}", err)
}
// unwrap_or_else 允许在遇到 Error 时执行一个回调函数来得到默认值
println!("hello {}", val.unwrap_or_else(|err| {
println!("报错");
"默认值".to_string()
}));
// 慎用的做法
val.unwrap(); // val 正确的时候，返回值。错误的时候 Panic
val.unwrap_err(); // val 正确的时候 Panic，错误的示范返回错误类型
val.unwrap_or("错啦".to_string()) // 错误的时候返回自定义值
val.unwrap_or_default(); // 错误则返回默认值
unsafe { println!("hello {}", val.unwrap_unchecked()); } // 必须与 unsafe 模块连用。不做检查，不抛出错误。
unsafe { println!("hello {}", val.unwrap_err_unchecked()); } // 必须与 unsafe 模块连用。不做检查，不抛出错误。
二、在最终接口加入 catch_unwind
// 这个代码中间某个位置反复报错，但可以
for i in 0..10 {
let x = i;
let result = panic::catch_unwind(|| {
if x % 2 == 0 {
panic!("错啦！x = {}", x);
} else { return 0; }
});
match result {
Ok(value) => println!("正确的: {:?}", value),
Err(error) => println!("错误的: {:?}", error),
}
}
一些需要特别注意的
vec.get(i) 会检查范围，而 vec[i] 超过返回直接 Panic
let val = unsafe { String::from_utf8_unchecked(a.to_vec()) }; // 不符合 utf-8 的，也不会报错
let val = String::from_utf8(a.to_vec()); // 如果不符合 utf-8 编码，会直接报错
string 的 idx 转化问题
// bytes 对应的 index，char 对应的 index
let s = "你好，hello";
let mut char_idx = 0;
for (byte_idx, _) in s.char_indices() {
println!("{},{}", byte_idx, char_idx);
char_idx += 1;
}
实战
这个抄的，& * 没搞懂
use std::collections::HashMap;
impl Solution {
pub fn two_sum(nums: Vec<i32>, target: i32) -> Vec<i32> {
let mut map: HashMap<i32, i32> = HashMap::new();
for (idx, n) in nums.iter().enumerate() {
match map.get(&(target - *n)) {
Some(&v) => return vec![v, idx as i32],
None => map.insert(*n, idx as i32),
};
}
vec![]
}
}
下面这个自己写的（似乎很多地方不需要借用）
use std::collections::HashMap;
pub fn two_sum(nums: Vec<i32>, target: i32) -> Vec<i32> {
let mut hash_map: HashMap<i32, i32> = HashMap::new();
for (idx, val) in nums.iter().enumerate() {
if hash_map.contains_key(val) {
return vec![hash_map[val], idx as i32];
}
hash_map.insert(target - val, idx as i32);
}
return Vec::new();
}
Rust的特点
对版本放心，借助 cargo，可以同时调用不同版本的包。
编译
- 一次编译，跨平台到处运行。得益于 LLVM
- 增量编译。只增量编译修改过的部分
核心库
- 最核心的部分，与标准库有重复。
- 基础的 trait：Copy、Debug、Display、Option
- 基本类型，bool、char、i8～i32/u8～u32/f8～f32、str、array、slice、tuple、pointer
- 常见数据结构 String、Vec、HashMap、Rc、Arc、Boc
- 常见宏定义
print!, assert!, panic!, vec!
#![no_std]
标准库
包 crate
- 第三方包在
crates.io上 - 文档自动发布到
docs.rs上
内存表达式相关
- 本地变量
- 静态变量
*exprvec[idx]- 字段引用
obj.field - 上面的组合
奇怪的设计
..语法不支持步长，你需要用一个 while 循环，或者 iter 语句，写一段长长的代码，而不是像python的(0..5).map(|x| x )合法，但是(0f64..5f64).map(|x| x )不合法
1
https://leetcode.cn/problems/remove-duplicates-from-sorted-array/
这个 beat 100%
impl Solution {
pub fn remove_duplicates(nums: &mut Vec<i32>) -> i32 {
let mut p1 = 0;
let mut p2 = 1;
while p2 < nums.len() {
if nums[p2] == nums[p1] {} else {
p1 += 1;
nums[p1] = nums[p2];
}
p2 += 1;
}
p1 += 1;
return p1 as i32;
}
}
这个就只能beat 20%，把!(nums[p2] == nums[p1]) 换成 nums[p2] != nums[p1]，也是同样结果
impl Solution {
pub fn remove_duplicates(nums: &mut Vec<i32>) -> i32 {
let mut p1 = 0;
let mut p2 = 1;
while p2 < nums.len() {
if !(nums[p2] == nums[p1]) {
p1 += 1;
nums[p1] = nums[p2];
}
p2 += 1;
}
p1 += 1;
return p1 as i32;
}
}
猜测：
- not运算比 else 分支要消耗很多资源
!=这个符号实际上也是not运算
数据结构
enum 实现二叉树
基于泛型的数据结构举例：实现一个二叉树
// 创建T类型值的有序集合
enum BinaryTree<T> { // BinaryTree的值只占1个机器字
Empty, // 不包含任何数据
NonEmpty(Box<TreeNode<T>>) // 包含一个Box，它是指向位于堆内存的TreeNode的指针
}
// BinaryTree的节点
struct TreeNode<T> {
element: T, // 实际的元素
left: BinaryTree<T>, // 左子树
right: BinaryTree<T> // 右子树
}
创建这个树的任何特定节点：
use self::BinaryTree::*
let jupiter_tree = NonEmpty(Box::new(TreeNode {
element: "Jupiter",
left: Empty,
right: Empty
}));
大一点的树可以基于小一点的树创建
// 将jupiter_node和mercury_node的所有权，通过赋值转移给新的父节点mars_tree
let mars_tree = NonEmpty(Box::new(TreeNode {
element: "Mars",
left: jupiter_tree,
right: mercury_tree
}));
根节点也使用相同的方式创建：
let tree = NonEmpty(Box::new(TreeNode {
element: "Saturn",
left: mars_tree,
right: uranus_tree
}));
假如这个树有一个 add 方法，那么可以通过这样调用这个树：
let mut tree = BinaryTree::Empty;
for planet in planets {
tree.add(planet);
}
附加：实现一个add功能的二叉树
enum BinaryTree<T> {
Empty,
NonEmpty(Box<TreeNode<T>>)
}
struct TreeNode<T> {
element: T,
left: BinaryTree<T>,
right: BinaryTree<T>
}
impl<T: Ord> BinaryTree<T> {
fn add(&mut self, value: T) {
match *self {
BinaryTree::Empty =>
*self = BinaryTree::NonEmpty(Box::new(TreeNode {
element: value,
left: BinaryTree::Empty,
right: BinaryTree::Empty
})),
BinaryTree::NonEmpty(ref mut node) =>
if value <= node.element {
node.left.add(value);
} else {
node.right.add(value);
}
}
}
}
临时
// 加上 mut 是可变的(mutable)，不加是不可变的
let mut guess = String::new();
io::stdin()
.read_line(&mut guess)
.expect("Failed to read line");
//
println!("You guessed: {}", guess);
猜数字
// rand = "0.8.3"
use std::cmp::Ordering;
use std::io;
use rand::Rng;
fn main() {
println!("Guess the num!");
let secret_num = rand::thread_rng().gen_range(1..101);
println!("secret num is {}", secret_num);
let mut guess = String::new();
loop {
println!("Please input you guess:");
// read_line 的时候，不会覆盖，而是会添加到后面，所以每次循环要clear
guess.clear();
io::stdin()
.read_line(&mut guess)
.expect("Failed to read line");
// let guess: u32 = guess.trim().parse().expect("Please type a number!");
let guess: u32 = match guess.trim().parse() {
Ok(num) => num,
Err(_) => {
println!("pleas input a num!");
continue;
}
};
println!("You guessed: {}", guess);
match guess.cmp(&secret_num) {
Ordering::Less => println!("Too small"),
Ordering::Greater => println!("Too big!"),
Ordering::Equal => {
println!("You win!");
break;
}
}
}
}
Rust如何实现“继承”，以复用父类的方法
Rust 不支持继承，单可以使用一些方法，实现类似“继承”的效果，以此提升代码复用
// 基类
struct Animal {
age: i32,
}
impl Animal {
fn new(age: i32) -> Self {
Animal { age }
}
// 基类方法，下面的代码中，它将会被子类复用
fn speak(&self) {
println!("I'm an animal. Age = {}", self.age);
}
}
// 子类
struct Dog {
supper: Animal,
name: String,
}
impl Dog {
fn new(name: String, age: i32) -> Self {
Dog { supper: Animal::new(age), name }
}
// 实现"复用父类的方法"
fn speak(&self) {
self.supper.speak();
}
}
fn main() {
let dog = Dog::new(String::from("Tom"), 2);
dog.speak();
}
以上代码实现了一个父类 Animal， 它有一个类方法 speak。
实现效果：“子类” Dog 的 speak 直接继承 父类 Animal 的 speak
废弃
// 相当于 enumerate
str1.char_indices()
在 Windows 上编译并运行 32 位程序
在 MacBook 上比较麻烦，需要 docker，但是 Windows 上很简单
# 安装工具
rustup target add i686-pc-windows-msvc
# 编译 32 位版本
cargo build --release --target i686-pc-windows-msvc
# 运行 32 位版本的可执行程序
target\i686-pc-windows-msvc\release\tmp.exe
GNU 的
# 安装工具
rustup target add i686-pc-windows-gnu
# 编译 32 位版本
cargo build --release --target i686-pc-windows-gnu
# 运行 32 位版本的可执行程序
target\i686-pc-windows-gnu\release\tmp.exe
由此发现 rand 在 32/64 位系统上的一个 bug
fn main() {
let pwd32 = [0u8; 32];
let mut rng = StdRng::from_seed(pwd32);
for _ in 0..5 {
let num = rng.gen_range(0..62usize);
print!("{}, ", num);
}
print!("\n")
}
运行结果：
- 在 32 位系统的结果是
25, 20, 4, 51, 45, - 在 64 位系统的结果是
20, 51, 4, 23, 46,
原因： usize 类型在 32 位系统上的长度为 32，在 64 位系统上的长度位 4；而 rand 做随机数生成的时候会根据类型的长度来分配下一个值
结论：定位这个问题挺不容易的，以后使用 usize 类型要慎重。
