qmhtmy / rustbook Goto Github PK
View Code? Open in Web Editor NEWA book about Rust Data Structures and Algorithms.
License: Apache License 2.0
A book about Rust Data Structures and Algorithms.
License: Apache License 2.0
example:
输入
["LRUCache", "put", "put", "get", "put", "get", "put", "get", "get", "get"]
[[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]]
输出
[null, null, null, 1, null, -1, null, -1, 3, 4]
解释
LRUCache lRUCache = new LRUCache(2);
lRUCache.put(1, 1); // 缓存是 {1=1}
lRUCache.put(2, 2); // 缓存是 {1=1, 2=2}
lRUCache.get(1); // 返回 1
lRUCache.put(3, 3); // 该操作会使得关键字 2 作废,缓存是 {1=1, 3=3}
lRUCache.get(2); // 返回 -1 (未找到)
lRUCache.put(4, 4); // 该操作会使得关键字 1 作废,缓存是 {4=4, 3=3}
lRUCache.get(1); // 返回 -1 (未找到)
lRUCache.get(3); // 返回 3
lRUCache.get(4); // 返回 4
get error:
预期结果:[null, null, null, 1, null, -1, null, -1, 3, 4]
输出结果:[null, null, null, 1, null, -1, null, 1, 3, 4]
code:
use std::collections::HashMap;
use std::hash::Hash;
/// 具体实现 参考 https://github.com/jeromefroe/lru-rs/blob/master/src/lib.result
/// Least Recently Used, 最近最少使用, 关键在于追踪每一个 entry 的 age, 每次淘汰最小的那一个 key
/// 假如淘汰逻辑要做到 O(1) 复杂度, 我们可以引入一个链表, 每次 touch 一个值时, 就删掉它重新 push_back, 而当达到容量要驱逐时, 则 pop_front
/// Rust 的链表不支持根据引用删除任意元素,也没有 LinkedHashMap,需要自己实现一个
// LRU 上的元素项
struct Entry<K, V> {
key: K,
val: Option<V>,
next: Option<usize>,
prev: Option<usize>,
}
struct LruCache<K, V> {
cap: usize,
head: Option<usize>,
tail: Option<usize>,
map: HashMap<K, usize>,
entries: Vec<Entry<K, V>>,
}
/**
* `&self` means the method takes an immutable reference.
* If you need a mutable reference, change it to `&mut self` instead.
*/
impl<K: Clone + Hash + Eq, V> LruCache<K, V> {
fn new(cap: usize) -> Self {
Self::with_capacity(cap)
}
fn with_capacity(cap: usize) -> Self {
LruCache {
cap,
head: None,
tail: None,
map: HashMap::with_capacity(cap),
entries: Vec::with_capacity(cap),
}
}
fn insert(&mut self, key: K, val: V) -> Option<V> {
if self.map.contains_key(&key) {
self.access(&key);
let entry = &mut self.entries[self.head.unwrap()];
let old_val = entry.val.take();
entry.val = Some(val);
old_val
} else {
self.ensure_room();
// 更新原始头指针
let index = self.entries.len();
self.head.map(|e| {
self.entries[e].prev = Some(index);
});
// 新的头结点
self.entries.push(Entry {
key: key.clone(),
val: Some(val),
prev: None,
next: self.head,
});
self.head = Some(index);
self.tail = self.tail.or(self.head);
self.map.insert(key, index);
None
}
}
fn remove(&mut self, key: &K) -> Option<V> {
self.map.remove(&key).map(|index| {
self.remove_from_list(index);
self.entries[index].val.take().unwrap()
})
}
fn get(&mut self, key: &K) -> Option<&V> {
if self.contains(key) {
self.access(key);
}
let entries = &self.entries;
self.map
.get(key)
.and_then(move |&i| entries[i].val.as_ref())
}
fn get_mut(&mut self, key: &K) -> Option<&mut V> {
if self.contains(key) {
self.access(key);
}
let entries = &mut self.entries;
self.map
.get(key)
.and_then(move |&i| entries[i].val.as_mut())
}
fn contains(&mut self, key: &K) -> bool {
self.map.contains_key(key)
}
fn is_empty(&self) -> bool {
self.map.is_empty()
}
fn is_full(&self) -> bool {
self.map.len() == self.cap
}
fn len(&self) -> usize {
self.map.len()
}
// 获取某个 key 的值,移除原来位置的值并在头部加入
fn access(&mut self, key: &K) {
let i = *self.map.get(key).unwrap();
self.remove_from_list(i);
self.head = Some(i);
}
fn remove_from_list(&mut self, i: usize) {
let (prev, next) = {
let entry = self.entries.get_mut(i).unwrap();
(entry.prev, entry.next)
};
match (prev, next) {
// 数据项在缓存中间
(Some(j), Some(k)) => {
let head = &mut self.entries[j];
head.next = next;
let next = &mut self.entries[k];
next.prev = prev;
}
// 数据项在缓存末尾
(Some(j), None) => {
let head = &mut self.entries[j];
head.next = None;
self.tail = prev;
}
// 数据项在缓存头部
_ => {
if self.len() > 1 {
let head = &mut self.entries[0];
head.next = None;
let next = &mut self.entries[1];
next.prev = None;
}
}
}
}
// 确保容量足够,满了就移除末尾的元素
fn ensure_room(&mut self) {
if self.cap == self.len() {
self.remove_tail();
}
}
fn remove_tail(&mut self) {
if let Some(index) = self.tail {
self.remove_from_list(index);
let key = &self.entries[index].key;
self.map.remove(key);
}
if self.tail.is_none() {
self.head = None;
}
}
}
struct LRUCache {
cache: LruCache<i32, i32>,
}
impl LRUCache {
fn new(capacity: i32) -> Self {
Self {
cache: LruCache::new(capacity as usize),
}
}
fn get(&mut self, key: i32) -> i32 {
if let Some(v) = self.cache.get(&key) {
*v
} else {
-1
}
}
fn put(&mut self, key: i32, value: i32) {
self.cache.insert(key, value);
}
}
/**
* Your LRUCache object will be instantiated and called as such:
* let obj = LRUCache::new(capacity);
* let ret_1: i32 = obj.get(key);
* obj.put(key, value);
*/
#[test]
fn it_works2() {
let mut obj = LRUCache::new(2);
obj.put(1, 1);
obj.put(2, 2);
assert_eq!(obj.get(1), 1);
obj.put(3, 3);
assert_eq!(obj.get(2), -1);
obj.put(4, 4);
assert_eq!(obj.get(1), -1);
assert_eq!(obj.get(3), 3);
assert_eq!(obj.get(4), 4);
}
README.md
: witten
should be written
;tooolchain
should be toolchain
.使用的代码为 https://github.com/QMHTMY/RustBook/blob/8c6ef29bc84672e37ca4d6b90aafccba10e9b6da/code/chapter06/heap_sort.rs
其中, main
函数略有不同 (删掉 nums
开头的 0
)
fn main() {
let mut nums = [ 54, 32, 99, 18, 75, 31, 43, 56, 21, 22];
heap_sort(&mut nums);
println!("sorted nums: {:?}", nums);
}
输出结果为
sorted nums: [54, 18, 21, 22, 31, 32, 43, 56, 75, 99]
期望的结果为
sorted nums: [18, 21, 22, 31, 32, 43, 54, 56, 75, 99]
bin_insertion_sort.rs 17行开始的以下代码段中
// 二分法找到 temp 的位置
while left <= right {
mid = (left + right) >> 1;
if temp < nums[mid] {
right = mid - 1;
} else {
left = mid + 1;
}
}
mid
为 usize
类型,若待排序数组为 [2,3,1,4]
,则会出现 0 usize - 1
的情况,造成程序 panic
,加上一段对 mid
为 0 的处理就好,代码如下
while left <= right {
mid = (left + right) >> 1;
if temp < nums[mid] {
if mid == 0 {break;}
right = mid - 1;
} else {
left = mid + 1;
}
}
https://github.com/QMHTMY/RustBook/blob/main/code/chapter03/list_stack.rs
fn pop(&mut self) -> Option<T>{
self.top.take().map(|node|{
let node = *node;
self.top = node.next;
self.size -= 1;
node.data
})
}
// queue.rs
// 队列
#[derive(Debug)]
struct Queue {
cap: usize, // 容量
data: Vec, // 数据容器
}
impl Queue {
fn new(size: usize) -> Self {
Queue {
cap: size,
data: Vec::with_capacity(size),
}
}
// 判断是否有剩余空间、有则数据加入队列
fn enqueue(&mut self, val: T) -> Result<(), String> {
if Self::size(&self) == self.cap {
return Err("No space available".to_string());
}
self.data.insert(0, val);
Ok(())
}
fn size(&self) -> usize {
self.data.len()
}
}
Because the function of "size(&self) " is a method belongs to one instance, so that we can't use the Self::size(&self) to obtain the size of self, the better choice is using self.size()......
Has there been any progress on the English version of this textbook? Would really love to read it.
我想在电子阅读器上阅读本书,但是pdf文件很难重新编辑改变字体大小。
麻烦可以提供一个字体更大的版本吗?(如果可以的话
如果转换格式的话会对阅读有很大的影响。
谢谢。
等宽字体便于代码阅读
https://github.com/QMHTMY/RustBook/blob/main/code/chapter05/interpolation_search.rs
不应该用上界处是否是 target来判断查找的结果
原来的代码:
fn interpolation_search(nums: &[i32], target: i32) -> bool {
if nums.is_empty() { return false; }
let mut high = nums.len() - 1;
let mut low = 0usize;
loop {
let low_val = nums[low];
let high_val = nums[high];
if high <= low || target < low_val || target > high_val {
break;
}
let offset = (target - low_val)*(high - low) as i32 / (high_val - low_val);
let interpolant = low + offset as usize;
if nums[interpolant] > target {
high = interpolant - 1;
} else if nums[interpolant] < target {
low = interpolant + 1;
} else {
break;
}
}
if target == nums[high] {
true
} else {
false
}
}
修改如下:
fn interpolation_search(nums: &[i32], target: i32) -> bool {
if nums.is_empty() { return false; }
let mut high = nums.len() - 1;
let mut low = 0usize;
loop {
let low_val = nums[low];
let high_val = nums[high];
if high <= low || target < low_val || target > high_val {
return false;
}
let offset = (target - low_val)*(high - low) as i32 / (high_val - low_val);
let interpolant = low + offset as usize;
if nums[interpolant] > target {
high = interpolant - 1;
} else if nums[interpolant] < target {
low = interpolant + 1;
} else {
return true;
}
}
}
131页开头的
macro_rules! parent { ($child:ident) => { $child >> 1 }; }
应当修改为
macro_rules! parent { ($child:ident) => { ($child-1) >> 1 }; }
129页讲解堆排序时下标从1开始,所以左右子节点分别是2n和2n+1,父节点为子节点除以2。131页的代码是以下标0开始,所以左右子节点分别是2n+1和2n+2,父节点应当为子节点减一后除以2,否则右子节点计算得到的是n+1而非n。
书中代码可以正常运行,是因为parent宏只在初始化时使用以减少move_down的次数,即使计算错误多执行一次也不影响正确性。
Hi Shieber, thanks for the book! However, it appears that the pdf could not be loaded/rendered on web browser (specifically Chrome that I'm currently using), any plan to fix that (by the way the download version is perfect) ?
Thanks!
书写得挺好的,不过偶然发现英文版和中文版同样的内容会出现不一样的代码
看得出来作者很用心,质量也很高,总之非常赞。
第25页:
2.5.2 集合类型
Rust 实现的 String 底层基于数组,所以 String 同数组一样不可更改。
这里描述是有问题的,标准库中 String
类型是由 Vec
实现的,也是可变的。
A declarative, efficient, and flexible JavaScript library for building user interfaces.
🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
An Open Source Machine Learning Framework for Everyone
The Web framework for perfectionists with deadlines.
A PHP framework for web artisans
Bring data to life with SVG, Canvas and HTML. 📊📈🎉
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
Some thing interesting about web. New door for the world.
A server is a program made to process requests and deliver data to clients.
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
Some thing interesting about visualization, use data art
Some thing interesting about game, make everyone happy.
We are working to build community through open source technology. NB: members must have two-factor auth.
Open source projects and samples from Microsoft.
Google ❤️ Open Source for everyone.
Alibaba Open Source for everyone
Data-Driven Documents codes.
China tencent open source team.