最近抽时间看完了<<The secrets of Rust tools» 一书, 以下简称tools. Tools这边书属于入门级别的rust书籍, 一个周末, 每天看3到4个小时可以看完. ...

Dijkstra算法是一种图遍历算法,用于找到源顶点到图中所有其他顶点的最短路径。 数据结构 顶点(Vertex): 一个保存顶点id的结构体。 边(Edge): 一个保存起点和终点顶点id的结构体,以及边的权重(代价),必须是正整数。 图(Graph): 一个保存所有顶点和边的结构体。 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 use std::cmp::Ordering; #[derive(Debug, PartialEq, Eq, Clone, Hash)] pub struct Vertex { // `id`: 顶点的唯一标识符,用字符串表示。 id: String, } #[derive(Debug, PartialEq, Eq, Clone)] pub struct Edge { // `from`: 边的起点顶点id。 from: String, // `to`: 边的终点顶点id。 to: String, // `cost`: 遍历该边的权重或代价。 cost: u32, } #[derive(Debug, PartialEq, Eq)] pub struct Graph { // `vertices`: 一个包含所有顶点的`Vertex`结构体向量。 vertices: Vec<Vertex>, // `edges`: 一个包含所有边的`Edge`结构体向量。 edges: Vec<Edge>, } #[derive(Clone, Eq, PartialEq)] struct Node { // `cost`: 从源顶点到该顶点的当前最短距离。 cost: u32, // `vertex_id`: 该节点所代表顶点的id。 vertex_id: String, } // 为`Node`实现`Ord`特性,使其可用于`BinaryHeap`。 impl Ord for Node { fn cmp(&self, other: &Self) -> Ordering { // 反转`cost`的排序,使`BinaryHeap`表现为最小堆。 // Rust中的`BinaryHeap`默认是最大堆,反转比较结果会使其成为最小堆。 other.cost.cmp(&self.cost) } } // 为`Node`实现`PartialOrd`特性。 impl PartialOrd for Node { fn partial_cmp(&self, other: &Self) -> Option<Ordering> { Some(self.cmp(other)) } } Dijkstra算法 最低代价 将源顶点到自身的距离初始化为0。 将源顶点及代价0推入优先队列。 循环直到优先队列为空。 从优先队列中弹出距离最小的顶点。 如果当前顶点是目标顶点,则跳出循环。 如果已经找到了更短的路径到达当前顶点,则跳过。 遍历所有以当前顶点为起点的边。 计算通过当前顶点到达邻居顶点的代价。 如果找到了更短的路径到达邻居顶点,则更新距离,并将其推入优先队列。 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 use std::collections::{BinaryHeap, HashMap}; impl Graph { // 使用Dijkstra算法计算从src到dest的最低代价。 pub fn dijkstra_cost(&self, src: &str, dest: &str) -> Option<u32> { // `distances`: 一个`HashMap`用于存储从源顶点到每个顶点的最短距离。 let mut distances: HashMap<String, u32> = HashMap::new(); // `pq`: 一个`BinaryHeap`(优先队列)用于高效选择距离最小的顶点。 let mut pq: BinaryHeap<Node> = BinaryHeap::new(); // 将源顶点到自身的距离初始化为0。 distances.insert(src.to_string(), 0); // 将源顶点及代价0推入优先队列。 pq.push(Node { cost: 0, vertex_id: src.to_string(), }); // 循环直到优先队列为空。 while let Some(Node { cost, vertex_id }) = pq.pop() { // 如果当前顶点是目标顶点,则返回代价。 if vertex_id == dest { return Some(cost); } // 如果已经找到了更短的路径到达当前顶点,则跳过。 if cost > *distances.get(&vertex_id).unwrap_or(&u32::MAX) { continue; } // 遍历所有以当前顶点为起点的边。 for edge in self.edges.iter().filter(|e| e.from == vertex_id) { // 计算通过当前顶点到达邻居顶点的代价。 let next_cost = cost + edge.cost; // 如果找到了更短的路径到达邻居顶点,则更新距离,并将其推入优先队列。 if next_cost < *distances.get(&edge.to).unwrap_or(&u32::MAX) { distances.insert(edge.to.clone(), next_cost); pq.push(Node { cost: next_cost, vertex_id: edge.to.clone(), }); } } } // 如果没有找到路径,则返回None。 None } } 最短路径 与最低代价的算法大致相同,但需要保存一个previous的HashMap来存储到达每个顶点的最短路径上的前一个顶点。 ...

什么是 Kafka Kafka 是一个分布式流处理平台。 可以将其视为一个高吞吐量、容错的消息队列。 它专为处理实时数据流而设计。 概念 主题（Topic）： 发布记录的类别或馈送名称。 ...

创建Mermaid初始化的局部视图 在你的 layouts/partials 目录下创建一个名为 mermaid-init.html 的新文件。 将以下代码添加到 mermaid-init.html 中: 1 2 3 4 <script type="module"> import mermaid from '/js/mermaid.esm.min.mjs'; mermaid.initialize({ startOnLoad: true }); </script> 添加shortcodes 新建 layouts/shortcodes/mermaid.html 文件. 将以下代码添加到 mermaid.html 中: 1 2 3 4 5 6 7 8 9 10 11 12 13 {{- $scratch := .Page.Scratch -}} {{- if not ($scratch.Get "mermaid-counter") -}} {{- $scratch.Set "mermaid-counter" 1 -}} {{- partial "mermaid-init.html" . -}} {{- else -}} {{- $scratch.Add "mermaid-counter" 1 -}} {{- end -}} {{- $id := printf "mermaid-%d" ($scratch.Get "mermaid-counter") -}} <div id="{{ $id }}"> <pre class="mermaid"> {{- .Inner | safeHTML }} </pre> </div> 说明: ...

二叉搜索树(BST) 数据结构: 左子树节点的值都小于根节点的值 右子树节点的值都大于根节点的值 左右子树也分别为二叉搜索树 空节点为二叉搜索树 插入操作: 找到合适的位置, 小于当前节点插左树,大于等于当前节点插右树,空树直接插入, 保持二叉搜索树的性质, 重复1-3 基于Box<T>的二叉搜索树的实现 数据结构和Insert方法: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 // Maybe I should use a reference count instead of a box pointer // for the bfs method. #[derive(Debug, PartialEq, Eq, Clone)] pub struct BinarySearchBoxNode { val: i32, left: Option<Box<Self>>, right: Option<Box<Self>>, } impl BinarySearchBoxNode { fn new(val: i32) -> Self { Self { val, left: None, right: None, } } fn insert(&mut self, val: i32) { if val < self.val { if let Some(left) = &mut self.left { left.insert(val); } else { self.left = Some(Box::new(Self::new(val))); } return; } if let Some(right) = &mut self.right { right.insert(val); } else { self.right = Some(Box::new(Self::new(val))); } } } BFS vs DFS 主要区别： ...

归并排序 归并排序的步骤 递归地把当前序列拆分为两个子序列，直到每个子序列只有一个元素 对每个子序列递归地调用归并排序 将两个有序子序列合并成一个最终的有序序列 重复步骤1~3，直到排序完成 归并排序的步骤实现 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 pub fn merge_sort(data: &mut [i32]) { // base case if data.len() <= 1 { return; } let mid = data.len() / 2; // recusive call two sub array merge_sort(&mut data[0..mid]); merge_sort(&mut data[mid..]); // merge the two sorted sub array; merge(data, 0, mid, data.len()); } fn merge(data: &mut [i32], low: usize, mid: usize, high: usize) { // copy left and right sub array let left = &data[low..mid].to_vec(); let right = &data[mid..high].to_vec(); // keep two pointer to two sub array let mut i = 0; let mut j = 0; // the merged array index let mut k = low; // the merge loop, increasing k from low to high; while k >= low && k < high { // assign the smaller value to data[k] while i < left.len() && j < right.len() { if left[i] <= right[j] { data[k] = left[i]; i += 1; } else { data[k] = right[j]; j += 1; } k += 1; } // assign the rest value of left part to data[k..] while i < left.len() { data[k] = left[i]; i += 1; k += 1; } // assign the rest value of right part to data[k..] while j < right.len() { data[k] = right[j]; j += 1; k += 1; } } } 快速排序 ...

为什么 GitHub 不喜欢我的 MTU 让我来告诉你我花了一整天与我的 WireGuard VPN 搏斗的挫败经历， 以及为什么 GitHub 成了唯一一个不配合的网站。我希望我的经验， 特别是如果你像我一样在 microk8s 环境中运行 WireGuard，能帮你省去一些麻烦。 ...

今天在Hacker New上看到了一篇称赞Raisl的文章Why Rails Still Matters。 原文用黑胶唱片做为引子,说明以rails为代表的老旧web技术是ok的,不比 新的Next.js之类差很多,大家的应用场景不同而已. ...

今天在Hacker New上看到了一篇称赞rust的文章Writing New Code in Rust Is a Win for All of Us。 原文内容就不贴出来了，maillist的内容一般都可以活的很久，随时可以去阅读。 ...