【Rust日报】2022-01-25 Slas v0.2.0 —— Rust静态线性代数系统

2022-03-24 13:02:29 浏览数 (1)

（基础）精美图表详解线段树！

(Basic) Segment Trees with beautiful diagrams!

给定一个长度为N的数组arr，如果有以下操作：

  1. 查询区间[l,r]之间的最大值/最小值；
  2. 更新给定下标i的对应的值arr[i]；

则可以使用线段树来高效解决上述场景的查询和更新需求；

线段树的时空复杂度：

  1. 时间复杂度：O(logN)
  2. 空间复杂度：O(N)

Rust实现：

代码语言：javascript复制
// SegTree segment tree
fn main() {
    let arr = [4i32, 3, 2, 8, 5, 1, 2, 1];
    let max = |i, j| <i32>::max(i, j);

    let mut seg_tree = SegTree::new(&arr, max);
    println!("max(arr): {}", seg_tree.query((0, 7)));

    seg_tree.update(2, 10);
    println!("max(arr): {}", seg_tree.query((0, 7)));
}

struct SegTree<T, F, const N: usize>
    where
        [T; N]: Sized,
        F: Fn(T, T) -> T,
{
    buf: Vec<T>,
    f: F,
}

impl<T, F, const N: usize> SegTree<T, F, N>
    where
        T: Ord   Default   Copy,
        [T; N]: Sized,
        F: Fn(T, T) -> T,
{
    pub fn new(arr: &[T; N], f: F) -> Self {
        let mut buf = vec![T::default(); 2 * N];
        buf[N..2 * N].copy_from_slice(arr);
        for i in (1..N).rev() {
            buf[i] = f(buf[2 * i], buf[(2 * i   1)]);
        }
        SegTree { buf, f }
    }

    pub fn query(&self, (mut l, mut r): (usize, usize)) -> T {
        l  = N - 1;
        r  = N - 1;
        let mut ans = self.buf[l];
        while l <= r {
            if l % 2 == 1 {
                ans = (self.f)(ans, self.buf[l]);
                l  = 1;
            }
            if r % 2 == 0 {
                ans = (self.f)(ans, self.buf[r]);
                r -= 1;
            }
            l /= 2;
            r /= 2;
        }
        ans
    }

    pub fn update(&mut self, mut idx: usize, val: T) {
        idx  = N - 1;
        self.buf[idx] = val;
        idx /= 2;

        while idx != 1 {
            self.buf[idx] = (self.f)(self.buf[2 * idx], self.buf[2 * idx   1]);
            idx /= 2;
        }
    }
}

参考链接：

  • (Basic) Segment Trees;
  • segment-tree;

Thalo.rs —— Rust中的事件溯源库

Thalo.rs - Event Sourcing in Rust

Thalo是一个基于以下模式构建大型系统的事件溯源框架：

  • 事件溯源
  • CQRS
  • 事件驱动
  • 事务发件箱
  • DDD

它的设计是模块化的，带有实现大多数功能的额外库。

官方提供的库：

  • 核心库
    • thalo: 核心框架
    • thalo-testing: thalo的测试组件；
    • thalo-macros: 实现trait的宏（可以通过macro特性开关在核心库中打开此功能）；
  • 事件存储
    • thalo-postgres: 为Postgres实现EventStore trait；
    • thalo-inmemory: 内存实现EventStore；
    • thalo-filestore: 为filestore实现EventStore；
  • 事件流
    • thalo-kafka:为kafka实现EventStream；

电子邮件解析和生成库

E-mail parsing and building in Rust

作者刚刚发布了一个名为mail-builder的新库，可以在Rust中轻松生成MIME电子邮件。这个库与作者在几周前发布的邮件解析器mail-parser相结合，为构建和解析Rust中任何复杂的RFC5322电子邮件提供了全面支持。

mail-builder: https://crates.io/crates/mail-builder

mail-parser: https://crates.io/crates/mail-parser

Slas v0.2.0 —— Rust静态线性代数系统

Slas v0.2.0 - Static Linear Algebra System

提供静态分配的向量、矩阵和张量类型，高效的实现了blas/blis接口，默认情况下使用写时复制行为（又名cow）。

与v0.1.1版本相比，新版本的Slas有很多突破性的变化和功能，包括：

  • 模块化后端；
  • 更好的性能；
  • 支持矩阵和张量（张量仍然做不了多少）；
  • 向量支持可选的COW行为；
  • 更好的基准测试和文档；

项目地址：https://github.com/unic0rn9k/slas

From 日报小组 odd-cat

rust https 网络安全 编程算法 kafka

0 人点赞