开发

最近抽时间看完了<<The secrets of Rust tools» 一书, 以下简称tools. Tools这边书属于入门级别的rust书籍, 一个周末, 每天看3到4个小时可以看完. 整本书分为了好几个小的项目, 每个项目的模式是一样的TDD. 项目 count lines (wc -l) 提到了 BufRead trait用来做入参, 使用collect 把lines() Vec<Result<» 收集为 Result<Vec<» 简单介绍了 anyhow:Result, bail, context等常见用法, 介绍了 assert_cmd crate直接测试 cargo 命令行crate, 简单介绍了clap解析flag等命令行参数, 以及在后面的章节介绍了clap开发 cargo plugin, logbook (clap, serde) 简单介绍了File的io操作, 以及File open option builder 模式, 介绍了AsRef<Path>参数,方便测试, 如何public lib crate, 介绍Path to PathBuf the From trait, 以及as_ref From AsRef to reference, 使用serde 和serde_json序列化从硬盘读写数据,保持数据 回顾clap 的用法 weather client (reqwest) 简单介绍reqwest blocking模式, ...

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来存储到达每个顶点的最短路径上的前一个顶点。 ...

Dijkstra’s algorithm is a graph traversal algorithm that finds the shortest path between the source vertex and all other vertices in the graph. data structure Vertex: a struct that holds the vertex id. Edge: a struct that holds the vertex id of the start and end points, and the cost of the edge which must be a positive integer. Graph: a struct that holds the vertices and edges. 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::cmp::Ordering; #[derive(Debug, PartialEq, Eq, Clone, Hash)] pub struct Vertex { // `id`: A unique identifier for the vertex, represented as a String. id: String, } #[derive(Debug, PartialEq, Eq, Clone)] pub struct Edge { // `from`: The ID of the starting vertex of the edge. from: String, // `to`: The ID of the ending vertex of the edge. to: String, // `cost`: The weight or cost associated with traversing the edge. cost: u32, } #[derive(Debug, PartialEq, Eq)] pub struct Graph { // `vertices`: A vector of `Vertex` structs, representing all vertices in the graph. vertices: Vec<Vertex>, // `edges`: A vector of `Edge` structs, representing all edges in the graph. edges: Vec<Edge>, } #[derive(Clone, Eq, PartialEq)] struct Node { // `cost`: The current shortest distance from the source vertex to this vertex. cost: u32, // `vertex_id`: The ID of the vertex represented by this node. vertex_id: String, } // Implement `Ord` trait for `Node` to make it usable in `BinaryHeap`. impl Ord for Node { fn cmp(&self, other: &Self) -> Ordering { // Reverse the ordering of `cost` to make `BinaryHeap` behave as a min-heap. // `BinaryHeap` in Rust is a max-heap by default, so flipping the comparison results // in a min-heap behavior. other.cost.cmp(&self.cost) } } // Implement `PartialOrd` trait for `Node`. impl PartialOrd for Node { fn partial_cmp(&self, other: &Self) -> Option<Ordering> { Some(self.cmp(other)) } } Dijkstra algorithm lowest cost Initialize the distance from the source vertex to itself as 0. Push the source vertex into the priority queue with cost 0. Loop until the priority queue is empty. Pop the vertex with the smallest distance from the priority queue. If the current vertex is the destination, break the loop. If a shorter path to the current vertex has already been found, skip it. Iterate over all edges starting from the current vertex. Calculate the cost to the neighbor vertex through the current vertex. If a shorter path to the neighbor vertex is found, update the distance, and push it into the priority queue. 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 { // Computes the lowest cost from src to dest using Dijkstra's algorithm. pub fn dijkstra_cost(&self, src: &str, dest: &str) -> Option<u32> { // `distances`: A `HashMap` to store the shortest distances from the source vertex to each vertex. let mut distances: HashMap<String, u32> = HashMap::new(); // `pq`: A `BinaryHeap` (priority queue) to efficiently select the vertex with the smallest distance. let mut pq: BinaryHeap<Node> = BinaryHeap::new(); // Initialize the distance from the source vertex to itself as 0. distances.insert(src.to_string(), 0); // Push the source vertex into the priority queue with cost 0. pq.push(Node { cost: 0, vertex_id: src.to_string(), }); // Loop until the priority queue is empty. while let Some(Node { cost, vertex_id }) = pq.pop() { // If the current vertex is the destination, return the cost. if vertex_id == dest { return Some(cost); } // If a shorter path to the current vertex has already been found, skip it. if cost > *distances.get(&vertex_id).unwrap_or(&u32::MAX) { continue; } // Iterate over all edges starting from the current vertex. for edge in self.edges.iter().filter(|e| e.from == vertex_id) { // Calculate the cost to the neighbor vertex through the current vertex. let next_cost = cost + edge.cost; // If a shorter path to the neighbor vertex is found, update the distance and push it into the priority queue. 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(), }); } } } // If no path is found, return None. None } } shortest path Much the same as the lowest cost, but keep a previous HashMap to store the previous vertex in the shortest path to each vertex. ...

什么是 Kafka Kafka 是一个分布式流处理平台。 可以将其视为一个高吞吐量、容错的消息队列。 它专为处理实时数据流而设计。 概念 主题（Topic）： 发布记录的类别或馈送名称。 分区（Partition）： 一个主题被分成多个分区，这些分区是有序的、不可变的记录序列。分区实现了并行性和可伸缩性。 生产者（Producer）： 将记录发布到 Kafka 主题的应用程序。 消费者（Consumer）： 订阅一个或多个主题并处理记录的应用程序。 代理（Broker）： Kafka 服务器。代理存储数据。 集群（Cluster）： 一起工作的代理组。 副本（Replica）： 每个分区可以跨多个代理进行复制，以实现容错。 领导者（Leader）： 分区的一个副本被指定为领导者，处理所有读写请求。 追随者（Follower）： 分区的其他副本是追随者，从领导者复制数据。 偏移量（Offset）： 分配给分区内每个记录的唯一、顺序 ID。消费者使用偏移量跟踪它们在分区中的位置。 消费者组（Consumer Group）： 一组消费者一起从一个主题消费记录。每个分区被分配给一个组内的一个消费者。 保留策略（Retention Policy）： 定义 Kafka 在删除记录之前保留记录的时间。 ZooKeeper： 用于管理和协调 Kafka 集群（尽管较新版本正在摆脱 ZooKeeper）。 常见应用场景 实时数据管道： 从各种来源摄取和处理数据流。 日志聚合： 将来自多个服务器的日志收集到一个中心位置。 流处理： 构建分析和响应数据流的实时应用程序。 事件溯源： 存储表示应用程序状态更改的事件序列。 消息传递： 应用程序之间可靠、高吞吐量的消息传递。 活动跟踪： 实时跟踪网站或应用程序上的用户活动。 提交日志： 用作分布式数据库的提交日志。 Kafka 在系统设计中的作用 解耦： Kafka 解耦了生产者和消费者，允许它们独立发展。 可伸缩性： Kafka 可以处理大量数据，并通过添加更多代理进行水平扩展。 可靠性： 容错确保数据不会丢失。 缓冲： ...

Create a Partial for Mermaid Initialization Create a new file in your layouts/partials directory named mermaid-init.html. Add the following code to mermaid-init.html: HTML 1 2 3 4 <script type="module"> import mermaid from '/js/mermaid.esm.min.mjs'; mermaid.initialize({ startOnLoad: true }); </script> Create a Shortcode for mermaid Create a new file named mermaid.html in layouts/shortcodes/. Add the follwoing code to 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> Explanation of Changes: ...

创建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> 说明: ...

Binary Search Tree (BST) data structure: left subtree nodes are less than root node right subtree nodes are greater than root node left and right subtree are also binary search tree empty node is also binary search tree insert new node: find the position insert left tree if val < current node insert right tree if val >= current node keep the binary search tree property repeat 1-4 Implement BST with Box<T> 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 Key Differences: ...

二叉搜索树(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; } } } 快速排序 ...

最近给一个项目加上了限速的功能，跑了一段时间后发现一个问题，超级管理员的速度阈值本来是最大的，实际使用是却发现好想是0。 打了个个断点， 发现admin的rate.Limit 确实是 -1000。 看了下代码，原来是overflow了。 1 2 - limit := rate.NewLimiter(rate.Limit(q.Speed*1000), 1000) + limit := rate.NewLimiter(rate.Limit(float64(q.Speed)*1000), 1000) q.Speed 的type是 int16 当时写的时候觉得float64怎么可能overflow， 现在发现 是int16 * 1000就已经overflow了。 所以类型转换的时候一定要先转换再计算。 update 如果是int64 转 int32 的话，则应该反过来： int32(a / 1000) 其中a是int64类型。 准确来说，小转大，先转换再计算； 大转小，先计算再转小。