curl --proto '=https' --tlsv1.2 -sSf https://sh.rustup.rs | sh

source "$HOME/.cargo/env"

rustc --version
cargo --version

rustc 1.8x.0 (xxxxxxxx 20xx-xx-xx)
cargo 1.8x.0 (xxxxxxxx 20xx-xx-xx)

cd ~
cargo new hello
cd hello

hello/
  Cargo.toml
  src/
    main.rs

fn main() {
    println!("Hello, world!");
}

cargo run

   Compiling hello v0.1.0 (/home/你的用户名/hello)
    Finished `dev` profile [unoptimized + debuginfo] target(s) in 0.xxs
     Running `target/debug/hello`
Hello, world!

cd ~
cargo new m1_rust_basics
cd m1_rust_basics

// M1：对话记录本 —— 你的 Rust 第一课
// 功能：内存里存 5 条 DeepSeek 对话，支持 list / find <id> / quit 三种命令

// 一条对话记录。struct 就是"自定义的一张表"，下面三行是三个字段
struct Message {
    id: u64,      // 编号。u64 是"无符号 64 位整数"，也就是 0 到 1844 亿亿
    ts: u64,      // 时间戳：从 1970 年 1 月 1 日零点到现在的秒数
    text: String, // 聊天内容。String 是"归自己所有的字符串"，存在堆上
}

impl Message {
    // 关联函数，作用类似"构造函数"：Message::new(...) 造一条记录
    // 注意参数 text 的类型是 &str（借来的字符串），不是 String
    fn new(id: u64, ts: u64, text: &str) -> Message {
        Message {
            id: id,
            ts: ts,
            text: String::from(text), // 把借来的 &str 复制成自己的 String
        }
    }
}

// 在记录本里按 id 找一条。
// 参数 &[Message] 表示"借一整本记录来看一下"，不拿走所有权。
// 返回 Option<&Message>：找到就 Some(借你一条)，没找到就 None。
fn find_message(messages: &[Message], id: u64) -> Option<&Message> {
    for m in messages {
        if m.id == id {
            return Some(m); // Some 是"有，东西在里面"
        }
    }
    None // None 是"没有"
}

// 执行一条命令。返回 Result<bool, String>：
// Ok(true) 表示继续，Ok(false) 表示退出，Err(...) 表示命令本身有问题。
fn run_command(messages: &[Message], cmd: &str) -> Result<bool, String> {
    // 按空白把命令切成几段，比如 "find 3" 切成 ["find", "3"]
    let parts: Vec<&str> = cmd.split_whitespace().collect();
    if parts.is_empty() {
        return Err("空命令".to_string());
    }

    match parts[0] {
        "list" => {
            println!("---- 全部 {} 条对话 ----", messages.len());
            for m in messages {
                println!("[id={}] ts={} | {}", m.id, m.ts, m.text);
            }
            Ok(true)
        }
        "find" => {
            if parts.len() < 2 {
                return Err("find 后面要跟一个 id，比如 find 3".to_string());
            }
            // parse 把字符串变成数字，返回 Result：可能成功，也可能失败
            match parts[1].parse::<u64>() {
                Ok(id) => match find_message(messages, id) {
                    Some(m) => {
                        println!("[id={}] ts={} | {}", m.id, m.ts, m.text);
                        Ok(true)
                    }
                    None => {
                        println!("没找到 id={} 的记录", id);
                        Ok(true)
                    }
                },
                Err(_) => Err("id 必须是一个非负整数".to_string()),
            }
        }
        "quit" => {
            println!("再见！");
            Ok(false)
        }
        _ => {
            println!("不认识的命令：{}", parts[0]);
            println!("支持：list / find <id> / quit");
            Ok(true)
        }
    }
}

fn main() {
    // 造 5 条对话，假装是和 DeepSeek 的聊天记录
    let messages: Vec<Message> = vec![
        Message::new(1, 1717401600, "你好，请介绍一下 Rust"),
        Message::new(2, 1717401660, "Rust 的所有权是什么？"),
        Message::new(3, 1717401720, "帮我写一个快速排序"),
        Message::new(4, 1717401780, "解释一下生命周期"),
        Message::new(5, 1717401840, "谢谢，再见"),
    ];

    // 为了让你屏幕上的输出和书上完全一致，我们不读键盘，把命令写死
    let commands = vec!["list", "find 3", "find 99", "find abc", "hello", "quit"];

    for cmd in commands {
        println!("> {}", cmd);
        match run_command(&messages, cmd) {
            Ok(go_on) => {
                if !go_on {
                    break;
                }
            }
            Err(e) => println!("出错了：{}", e),
        }
    }
}

cargo run

> list
---- 全部 5 条对话 ----
[id=1] ts=1717401600 | 你好，请介绍一下 Rust
[id=2] ts=1717401660 | Rust 的所有权是什么？
[id=3] ts=1717401720 | 帮我写一个快速排序
[id=4] ts=1717401780 | 解释一下生命周期
[id=5] ts=1717401840 | 谢谢，再见
> find 3
[id=3] ts=1717401720 | 帮我写一个快速排序
> find 99
没找到 id=99 的记录
> find abc
出错了：id 必须是一个非负整数
> hello
不认识的命令：hello
支持：list / find <id> / quit
> quit
再见！

cd ~
cargo new m2_knn
cd m2_knn

// M2：暴力 KNN —— 在 1000 条"对话向量"里找最相似的 5 条
// 每条向量 128 维，你可以把它想象成 DeepSeek 给每句历史对话算出的"语义指纹"

// 一条向量记录：编号 + 128 个浮点数
struct VectorRecord {
    id: u64,
    data: Vec<f32>, // f32 是 32 位浮点数，机器学习里最常用
}

// 线性同余发生器（Linear Congruential Generator，LCG）：
// 一个自己能手算、能复现的伪随机数发生器。
// 每次调用把 state 往前推一格，并吐出一个 [-1, 1) 之间的 f32。
// 注意参数是 &mut u64：借进来并且允许修改，这样种子才能"走"。
fn next_f32(state: &mut u64) -> f32 {
    // 三个魔法数字来自经典教材；% 2147483648 是把结果压回 2 的 31 次方以内
    *state = (*state * 1103515245 + 12345) % 2147483648;
    // 取高位的 15 个比特，范围 [0, 32767]
    let v = (*state >> 16) as u32;
    // 映射到 [-1, 1)
    v as f32 / 32768.0 * 2.0 - 1.0
}

// 生成 n 条 dim 维的随机向量，seed 是种子：种子相同，结果永远相同
fn gen_vectors(n: usize, dim: usize, seed: u64) -> Vec<VectorRecord> {
    let mut state = seed; // mut：因为 next_f32 会改它
    let mut records = Vec::new(); // mut：因为要往里 push
    for i in 0..n {
        let mut data = Vec::new();
        for _ in 0..dim {
            data.push(next_f32(&mut state));
        }
        records.push(VectorRecord {
            id: i as u64, // as 是类型转换：usize 转成 u64
            data: data,
        });
    }
    records
}

// 余弦相似度（Cosine Similarity）：
// 公式是 dot(a,b) / (|a| * |b|)，结果越接近 1 越像，越接近 0 越无关。
// 参数 &[f32] 是"借一段浮点数切片看"，只借不拿。
fn cosine_similarity(a: &[f32], b: &[f32]) -> f32 {
    let mut dot = 0.0f32;     // 点积：对应维度相乘再相加
    let mut norm_a = 0.0f32;  // a 的长度平方
    let mut norm_b = 0.0f32;  // b 的长度平方
    for i in 0..a.len() {
        dot += a[i] * b[i];
        norm_a += a[i] * a[i];
        norm_b += b[i] * b[i];
    }
    dot / (norm_a.sqrt() * norm_b.sqrt())
}

// 暴力 KNN：对所有记录算一遍相似度，排序，取前 top_k 个。
// 返回值是 (id, 分数) 的列表，分数从大到小。
fn query(records: &[VectorRecord], q: &[f32], top_k: usize) -> Vec<(u64, f32)> {
    let mut scores: Vec<(u64, f32)> = Vec::new();
    for r in records {
        let s = cosine_similarity(&r.data, q);
        scores.push((r.id, s));
    }
    // sort_by 接收一个比较规则。浮点数没有"全序"，所以用 partial_cmp；
    // y.1 和 x.1 反过来写，就是从大到小排。
    // 我们的分数不会是 NaN，所以 unwrap 是安全的。
    scores.sort_by(|x, y| y.1.partial_cmp(&x.1).unwrap());
    // 只保留前 top_k 个，后面全扔掉
    scores.truncate(top_k);
    scores
}

fn main() {
    let records = gen_vectors(1000, 128, 42);
    println!("共生成 {} 条向量，每条 {} 维", records.len(), 128);
    println!(
        "第一条向量的前 4 维: {:.4}, {:.4}, {:.4}, {:.4}",
        records[0].data[0], records[0].data[1], records[0].data[2], records[0].data[3]
    );

    // 拿 id=42 那条向量本身当查询向量：
    // 它和它自己完全一样，所以第一名一定是 id=42，分数 1.0000。
    // 这里必须 clone：records 里的数据不能"搬走"，只能复制一份新的。
    let q = records[42].data.clone();

    let t0 = std::time::Instant::now(); // 开始计时
    let results = query(&records, &q, 5);
    let elapsed = t0.elapsed(); // 结束计时

    println!("与 id=42 最相似的 5 条记录：");
    for (rank, item) in results.iter().enumerate() {
        println!("top{}: id={}, score={:.4}", rank + 1, item.0, item.1);
    }
    println!("暴力扫描 1000 条耗时：{:?}", elapsed);
}

cargo run

共生成 1000 条向量，每条 128 维
第一条向量的前 4 维: 0.1646, 0.0396, -0.0681, 0.5540
与 id=42 最相似的 5 条记录：
top1: id=42, score=1.0000
top2: id=855, score=0.2333
top3: id=766, score=0.2328
top4: id=103, score=0.2195
top5: id=718, score=0.2161
暴力扫描 1000 条耗时：1.2ms

cd ~
cargo new m3_time_segments
cd m3_time_segments

// M3：时间段剪枝 —— 本篇的灵魂
// 核心思想：向量按时间戳分段存放。查询时先看每段的 [min_ts, max_ts]，
// 和时间窗口不挨着的段整段跳过，一次距离都不用算。

// ---------- 随机数（和 M2 一模一样的 LCG） ----------
fn next_f32(state: &mut u64) -> f32 {
    *state = (*state * 1103515245 + 12345) % 2147483648;
    let v = (*state >> 16) as u32;
    v as f32 / 32768.0 * 2.0 - 1.0
}

// ---------- 余弦相似度（和 M2 一模一样） ----------
fn cosine_similarity(a: &[f32], b: &[f32]) -> f32 {
    let mut dot = 0.0f32;
    let mut norm_a = 0.0f32;
    let mut norm_b = 0.0f32;
    for i in 0..a.len() {
        dot += a[i] * b[i];
        norm_a += a[i] * a[i];
        norm_b += b[i] * b[i];
    }
    dot / (norm_a.sqrt() * norm_b.sqrt())
}

// ---------- 段：一段时间内的向量装箱 ----------
// 每条记录是 (内部 id, 时间戳, 向量) 的三元组
struct Segment {
    min_ts: u64, // 本段最早的时间戳
    max_ts: u64, // 本段最晚的时间戳
    vectors: Vec<(u64, u64, Vec<f32>)>,
}

impl Segment {
    fn new() -> Segment {
        // 空段还没有任何记录，先把 min 放到最大、max 放到 0，
        // 这样第一条记录进来时一定会刷新它们
        Segment {
            min_ts: u64::MAX,
            max_ts: 0,
            vectors: Vec::new(),
        }
    }

    fn push(&mut self, id: u64, ts: u64, data: Vec<f32>) {
        if ts < self.min_ts {
            self.min_ts = ts;
        }
        if ts > self.max_ts {
            self.max_ts = ts;
        }
        self.vectors.push((id, ts, data));
    }

    fn len(&self) -> usize {
        self.vectors.len()
    }

    // 本段和时间窗口 [start, end) 有没有交集？
    // 窗口是"左闭右开"：包含 start，不包含 end。
    fn overlaps(&self, start: u64, end: u64) -> bool {
        // 不重叠只有两种情况：整段在窗口左边，或整段在窗口右边。
        // 取反就是"有交集"。
        !(self.max_ts < start || self.min_ts >= end)
    }
}

// ---------- 迷你 Varve 引擎 ----------
struct MiniVarve {
    capacity: usize, // 每段最多装多少条
    segments: Vec<Segment>,
}

impl MiniVarve {
    fn new(capacity: usize) -> MiniVarve {
        MiniVarve {
            capacity: capacity,
            segments: Vec::new(),
        }
    }

    // 写入一条记录。我们约定时间戳单调递增（新消息总是更晚），
    // 所以永远往最后一段追加；最后一段满了就切新段。
    fn write(&mut self, id: u64, ts: u64, data: Vec<f32>) {
        // 先只读地看一眼：要不要开新段？
        let need_new = match self.segments.last() {
            None => true,                          // 一段都还没有
            Some(seg) => seg.len() >= self.capacity, // 最后一段满了
        };
        if need_new {
            self.segments.push(Segment::new());
        }
        // last_mut 拿最后一段的可变借用；上面保证了至少有一段，所以 unwrap 安全
        let seg = self.segments.last_mut().unwrap();
        seg.push(id, ts, data);
    }

    // 查询：先剪枝，再对候选段做暴力 KNN。
    // 返回 (结果列表, 总段数, 跳过段数, 实际距离计算次数)。
    fn query(
        &self,
        start: u64,
        end: u64,
        q: &[f32],
        top_k: usize,
    ) -> (Vec<(u64, f32)>, usize, usize, usize) {
        let total = self.segments.len();
        let mut skipped = 0;
        let mut computed = 0;
        let mut scores: Vec<(u64, f32)> = Vec::new();

        // 第一步：物理剪枝，整段跳过
        for seg in &self.segments {
            if !seg.overlaps(start, end) {
                skipped += 1;
                continue; // 这一段一次距离都不用算
            }
            // 第二步：候选段内暴力扫描
            for item in &seg.vectors {
                // 段有交集不代表每条都在窗口里，逐条再看一眼
                if item.1 < start || item.1 >= end {
                    continue;
                }
                scores.push((item.0, cosine_similarity(&item.2, q)));
                computed += 1;
            }
        }

        scores.sort_by(|x, y| y.1.partial_cmp(&x.1).unwrap());
        scores.truncate(top_k);
        (scores, total, skipped, computed)
    }
}

// ---------- 造数据：1000 条记录，每天 10 条，共 100 天 ----------
// 返回 (id, ts, data) 的列表，时间戳严格递增
fn gen_records(n: usize, dim: usize, seed: u64) -> Vec<(u64, u64, Vec<f32>)> {
    let mut state = seed;
    let mut records = Vec::new();
    for i in 0..n {
        let day = (i / 10) as u64; // 每 10 条算一天
        let ts = day * 86400 + ((i % 10) as u64) * 3600; // 一天 86400 秒，每小时一条
        let mut data = Vec::new();
        for _ in 0..dim {
            data.push(next_f32(&mut state));
        }
        records.push((i as u64, ts, data));
    }
    records
}

fn main() {
    let records = gen_records(1000, 128, 42);

    let mut engine = MiniVarve::new(100); // 每段最多 100 条，也就是 10 天
    for r in &records {
        // r.2 是向量；write 要拿走所有权，所以 clone 一份给它
        engine.write(r.0, r.1, r.2.clone());
    }

    println!("写入 {} 条记录，共切成 {} 段", records.len(), engine.segments.len());
    for (i, seg) in engine.segments.iter().enumerate() {
        println!("段{}: [{} , {}]，共 {} 条", i, seg.min_ts, seg.max_ts, seg.len());
    }

    // 查询"最近 7 天"：第 93 天凌晨到第 100 天凌晨
    let day: u64 = 86400;
    let start = 93 * day;
    let end = 100 * day;

    // 用 id=995 的向量当查询向量（它是第 99 天的记录，在窗口里），
    // 所以第一名一定是它自己，分数 1.0000
    let q = records[995].2.clone();

    let (results, total, skipped, computed) = engine.query(start, end, &q, 5);
    println!("查询窗口: [{} , {})", start, end);
    println!("共 {} 段，跳过 {} 段，实际计算 {} 次距离", total, skipped, computed);
    println!("窗口内最相似的 5 条：");
    for (rank, item) in results.iter().enumerate() {
        println!("top{}: id={}, score={:.4}", rank + 1, item.0, item.1);
    }
}

cargo run

写入 1000 条记录，共切成 10 段
段0: [0 , 810000]，共 100 条
段1: [864000 , 1674000]，共 100 条
段2: [1728000 , 2538000]，共 100 条
段3: [2592000 , 3402000]，共 100 条
段4: [3456000 , 4266000]，共 100 条
段5: [4320000 , 5130000]，共 100 条
段6: [5184000 , 5994000]，共 100 条
段7: [6048000 , 6858000]，共 100 条
段8: [6912000 , 7722000]，共 100 条
段9: [7776000 , 8586000]，共 100 条
查询窗口: [8035200 , 8640000)
共 10 段，跳过 9 段，实际计算 70 次距离
窗口内最相似的 5 条：
top1: id=995, score=1.0000
top2: id=945, score=0.3663
top3: id=987, score=0.1876
top4: id=970, score=0.1588
top5: id=965, score=0.1420

cd ~
cargo new m4_benchmark
cd m4_benchmark

// M4：性能对比实验 —— 简历素材
// 灌入 100000 条 128 维向量（每天 1000 条，共 100 天），
// 对比两种查询方案在三档时间窗口下的耗时：
//   方案A 逻辑过滤：全量算距离，再用 if 筛时间（传统做法）
//   方案B 物理剪枝：先按段的时间范围整段跳过，再算距离（Varve 的做法）
// 注意：本实验必须用 cargo run --release 跑，否则慢 10 倍以上！

use std::time::Instant;

// ---------- 随机数（LCG，和前面一样） ----------
fn next_f32(state: &mut u64) -> f32 {
    *state = (*state * 1103515245 + 12345) % 2147483648;
    let v = (*state >> 16) as u32;
    v as f32 / 32768.0 * 2.0 - 1.0
}

// ---------- 余弦相似度 ----------
fn cosine_similarity(a: &[f32], b: &[f32]) -> f32 {
    let mut dot = 0.0f32;
    let mut norm_a = 0.0f32;
    let mut norm_b = 0.0f32;
    for i in 0..a.len() {
        dot += a[i] * b[i];
        norm_a += a[i] * a[i];
        norm_b += b[i] * b[i];
    }
    dot / (norm_a.sqrt() * norm_b.sqrt())
}

// ---------- 段和引擎（和 M3 一样） ----------
struct Segment {
    min_ts: u64,
    max_ts: u64,
    vectors: Vec<(u64, u64, Vec<f32>)>,
}

impl Segment {
    fn new() -> Segment {
        Segment {
            min_ts: u64::MAX,
            max_ts: 0,
            vectors: Vec::new(),
        }
    }
    fn push(&mut self, id: u64, ts: u64, data: Vec<f32>) {
        if ts < self.min_ts {
            self.min_ts = ts;
        }
        if ts > self.max_ts {
            self.max_ts = ts;
        }
        self.vectors.push((id, ts, data));
    }
    fn len(&self) -> usize {
        self.vectors.len()
    }
    fn overlaps(&self, start: u64, end: u64) -> bool {
        !(self.max_ts < start || self.min_ts >= end)
    }
}

struct MiniVarve {
    capacity: usize,
    segments: Vec<Segment>,
}

impl MiniVarve {
    fn new(capacity: usize) -> MiniVarve {
        MiniVarve {
            capacity: capacity,
            segments: Vec::new(),
        }
    }
    fn write(&mut self, id: u64, ts: u64, data: Vec<f32>) {
        let need_new = match self.segments.last() {
            None => true,
            Some(seg) => seg.len() >= self.capacity,
        };
        if need_new {
            self.segments.push(Segment::new());
        }
        let seg = self.segments.last_mut().unwrap();
        seg.push(id, ts, data);
    }
    // 方案B：物理剪枝查询。返回 (结果, 候选段数, 跳过段数, 距离计算次数)
    fn query(
        &self,
        start: u64,
        end: u64,
        q: &[f32],
        top_k: usize,
    ) -> (Vec<(u64, f32)>, usize, usize, usize) {
        let mut candidate = 0;
        let mut skipped = 0;
        let mut computed = 0;
        let mut scores: Vec<(u64, f32)> = Vec::new();
        for seg in &self.segments {
            if !seg.overlaps(start, end) {
                skipped += 1;
                continue;
            }
            candidate += 1;
            for item in &seg.vectors {
                if item.1 < start || item.1 >= end {
                    continue;
                }
                scores.push((item.0, cosine_similarity(&item.2, q)));
                computed += 1;
            }
        }
        scores.sort_by(|x, y| y.1.partial_cmp(&x.1).unwrap());
        scores.truncate(top_k);
        (scores, candidate, skipped, computed)
    }
}

// ---------- 方案A：逻辑过滤（传统做法） ----------
// 对全部记录算距离，再筛时间。返回 (结果, 距离计算次数)
fn query_plan_a(
    records: &[(u64, u64, Vec<f32>)],
    start: u64,
    end: u64,
    q: &[f32],
    top_k: usize,
) -> (Vec<(u64, f32)>, usize) {
    let mut computed = 0;
    let mut scores: Vec<(u64, f32)> = Vec::new();
    for r in records {
        // 先算距离：不管时间合不合，全部算一遍
        let s = cosine_similarity(&r.2, q);
        computed += 1;
        // 再筛时间：不在窗口里的白算了
        if r.1 >= start && r.1 < end {
            scores.push((r.0, s));
        }
    }
    scores.sort_by(|x, y| y.1.partial_cmp(&x.1).unwrap());
    scores.truncate(top_k);
    (scores, computed)
}

// ---------- 造数据：100000 条，每天 1000 条，共 100 天 ----------
fn gen_records(n: usize, dim: usize, seed: u64) -> Vec<(u64, u64, Vec<f32>)> {
    let mut state = seed;
    let mut records = Vec::new();
    for i in 0..n {
        let day = (i / 1000) as u64;
        let ts = day * 86400 + ((i % 1000) as u64) * 86; // 一天内每 86 秒一条
        let mut data = Vec::new();
        for _ in 0..dim {
            data.push(next_f32(&mut state));
        }
        records.push((i as u64, ts, data));
    }
    records
}

// 跑一轮对比：同一个窗口，两个方案各跑一次
fn bench_one(
    label: &str,
    start: u64,
    end: u64,
    records: &[(u64, u64, Vec<f32>)],
    engine: &MiniVarve,
    q: &[f32],
) {
    println!("== 窗口：{} [{}, {}) ==", label, start, end);

    let t0 = Instant::now();
    let (_ra, computed_a) = query_plan_a(records, start, end, q, 5);
    let ms_a = t0.elapsed().as_secs_f64() * 1000.0;
    println!(
        "方案A（逻辑过滤）：计算 {} 次距离，耗时 {:.1} ms",
        computed_a, ms_a
    );

    let t1 = Instant::now();
    let (_rb, candidate, skipped, computed_b) = engine.query(start, end, q, 5);
    let ms_b = t1.elapsed().as_secs_f64() * 1000.0;
    println!(
        "方案B（物理剪枝）：候选 {} 段，跳过 {} 段，计算 {} 次距离，耗时 {:.1} ms",
        candidate, skipped, computed_b, ms_b
    );

    let saved = (computed_a - computed_b) as f64 / computed_a as f64 * 100.0;
    println!("少算了 {:.1}% 的距离计算", saved);
    println!();
}

fn main() {
    println!("正在生成 100000 条 128 维向量（约 50 MB 内存）...");
    let records = gen_records(100000, 128, 42);

    let mut engine = MiniVarve::new(200); // 每段 200 条，共 500 段
    for r in &records {
        engine.write(r.0, r.1, r.2.clone());
    }
    println!("写入完毕，共 {} 段", engine.segments.len());
    println!();

    // 查询向量随便拿一条，这里用 id=55555（第 55 天）
    let q = records[55555].2.clone();

    let day: u64 = 86400;
    bench_one("最近 7 天", 46 * day, 53 * day, &records, &engine, &q);
    bench_one("最近 30 天", 35 * day, 65 * day, &records, &engine, &q);
    bench_one("全历史", 0, 100 * day, &records, &engine, &q);

    println!("注意：全历史窗口下方案B退化为方案A —— 所有段都有交集，剪枝没有省任何东西。");
    println!("这正是真 Varve 简历上 7 天 / 90 天 / 全历史三档 benchmark 的雏形。");
}

cargo run --release

正在生成 100000 条 128 维向量（约 50 MB 内存）...
写入完毕，共 500 段

== 窗口：最近 7 天 [3974400, 4579200) ==
方案A（逻辑过滤）：计算 100000 次距离，耗时 12.5 ms
方案B（物理剪枝）：候选 35 段，跳过 465 段，计算 7000 次距离，耗时 0.9 ms
少算了 93.0% 的距离计算

== 窗口：最近 30 天 [3024000, 5616000) ==
方案A（逻辑过滤）：计算 100000 次距离，耗时 12.4 ms
方案B（物理剪枝）：候选 150 段，跳过 350 段，计算 30000 次距离，耗时 3.8 ms
少算了 70.0% 的距离计算

== 窗口：全历史 [0, 8640000) ==
方案A（逻辑过滤）：计算 100000 次距离，耗时 12.6 ms
方案B（物理剪枝）：候选 500 段，跳过 0 段，计算 100000 次距离，耗时 12.5 ms
少算了 0.0% 的距离计算

注意：全历史窗口下方案B退化为方案A —— 所有段都有交集，剪枝没有省任何东西。
这正是真 Varve 简历上 7 天 / 90 天 / 全历史三档 benchmark 的雏形。

sudo apt update
sudo apt install python3-dev python3-venv
python3 -m venv ~/venv-varve
source ~/venv-varve/bin/activate
pip install maturin

mkdir -p ~/m5_pyo3/src
cd ~/m5_pyo3

[package]
name = "mini_varve"
version = "0.1.0"
edition = "2021"

# crate-type = ["cdylib"]：编译成"动态链接库"，
# 也就是一个 Python 能直接 import 的 .so / .pyd 文件
[lib]
name = "mini_varve"
crate-type = ["cdylib"]

[dependencies]
# pyo3 是 Rust 和 Python 之间的"翻译官"
# extension-module 这个 feature 表示：我们要编译成 Python 扩展模块
pyo3 = { version = "0.22", features = ["extension-module"] }

[build-system]
requires = ["maturin>=1.5,<2.0"]
build-backend = "maturin"

[project]
name = "mini_varve"
version = "0.1.0"
description = "迷你 Varve：带时间范围的向量记忆检索（教学版）"
requires-python = ">=3.8"

// M5：把 M3 的引擎打包成 Python 库
// 这一层只做两件事：
//   1. 引擎核心（Segment / MiniVarve / cosine_similarity），和 M3 完全一样
//   2. 用 pyo3 的宏给核心"穿一件 Python 外衣"

use pyo3::prelude::*;

// ---------- 引擎核心（和 M3 一样，只是改成了库文件 lib.rs） ----------

fn cosine_similarity(a: &[f32], b: &[f32]) -> f32 {
    let mut dot = 0.0f32;
    let mut norm_a = 0.0f32;
    let mut norm_b = 0.0f32;
    for i in 0..a.len() {
        dot += a[i] * b[i];
        norm_a += a[i] * a[i];
        norm_b += b[i] * b[i];
    }
    dot / (norm_a.sqrt() * norm_b.sqrt())
}

struct Segment {
    min_ts: u64,
    max_ts: u64,
    vectors: Vec<(u64, u64, Vec<f32>)>,
}

impl Segment {
    fn new() -> Segment {
        Segment {
            min_ts: u64::MAX,
            max_ts: 0,
            vectors: Vec::new(),
        }
    }
    fn push(&mut self, id: u64, ts: u64, data: Vec<f32>) {
        if ts < self.min_ts {
            self.min_ts = ts;
        }
        if ts > self.max_ts {
            self.max_ts = ts;
        }
        self.vectors.push((id, ts, data));
    }
    fn len(&self) -> usize {
        self.vectors.len()
    }
    fn overlaps(&self, start: u64, end: u64) -> bool {
        !(self.max_ts < start || self.min_ts >= end)
    }
}

// #[pyclass]：把这个 Rust 结构体暴露给 Python，变成一个 Python 类。
// Python 那边会看到一个叫 MiniVarve 的类，可以 new、可以调方法。
#[pyclass]
struct MiniVarve {
    capacity: usize,
    segments: Vec<Segment>,
}

// 普通 impl：Rust 自己用的辅助函数，Python 看不见
impl MiniVarve {
    fn push_record(&mut self, id: u64, ts: u64, data: Vec<f32>) {
        let need_new = match self.segments.last() {
            None => true,
            Some(seg) => seg.len() >= self.capacity,
        };
        if need_new {
            self.segments.push(Segment::new());
        }
        let seg = self.segments.last_mut().unwrap();
        seg.push(id, ts, data);
    }
}

// #[pymethods]：这个 impl 块里的函数会变成 Python 类的方法
#[pymethods]
impl MiniVarve {
    // #[new]：Python 里 MiniVarve(100) 会调到这里
    #[new]
    fn new(capacity: usize) -> Self {
        MiniVarve {
            capacity: capacity,
            segments: Vec::new(),
        }
    }

    // #[staticmethod]：Python 里 MiniVarve.create(100) 也能造一个。
    // 两种写法都给你，和真 Varve 的 API 习惯保持一致。
    #[staticmethod]
    fn create(capacity: usize) -> Self {
        MiniVarve::new(capacity)
    }

    // PyResult<()>：表示"可能出错，出错就抛 Python 异常"。
    // Python 传过来的 list 会被 pyo3 自动转成 Vec<f32>。
    fn write(&mut self, id: u64, ts: u64, vector: Vec<f32>) -> PyResult<()> {
        self.push_record(id, ts, vector);
        Ok(())
    }

    // 查询：返回 (id, 分数) 的列表，Python 那边看到的是 list of tuple
    fn query(
        &self,
        start: u64,
        end: u64,
        vector: Vec<f32>,
        top_k: usize,
    ) -> PyResult<Vec<(u64, f32)>> {
        let mut scores: Vec<(u64, f32)> = Vec::new();
        for seg in &self.segments {
            if !seg.overlaps(start, end) {
                continue;
            }
            for item in &seg.vectors {
                if item.1 < start || item.1 >= end {
                    continue;
                }
                scores.push((item.0, cosine_similarity(&item.2, &vector)));
            }
        }
        scores.sort_by(|x, y| y.1.partial_cmp(&x.1).unwrap());
        scores.truncate(top_k);
        Ok(scores)
    }

    // 顺手暴露一个小工具：看看现在切成几段了
    fn segment_count(&self) -> usize {
        self.segments.len()
    }
}

// #[pymodule]：定义 Python 模块本身。
// 函数名 mini_varve 必须和 Cargo.toml 里 [lib] 的 name 一致。
// Python 里 import mini_varve 时，就会执行这个函数完成注册。
#[pymodule]
fn mini_varve(m: &Bound<'_, PyModule>) -> PyResult<()> {
    m.add_class::<MiniVarve>()?;
    Ok(())
}

# M5 演示：在 Python 里使用我们用 Rust 写的 mini_varve 库
# 运行前确保：虚拟环境已激活，并且已经执行过 maturin develop

import random

import mini_varve

DIM = 128
DAY = 86400

# 造引擎：每段最多 100 条
engine = mini_varve.MiniVarve.create(100)

# 写入 1000 条记录：每天 10 条，共 100 天
# 向量用 Python 的 random 生成，种子固定为 42
random.seed(42)
probe = None  # 记住 id=995 的向量，待会儿拿它当查询向量
for i in range(1000):
    day = i // 10
    ts = day * DAY + (i % 10) * 3600
    vec = [random.uniform(-1.0, 1.0) for _ in range(DIM)]
    if i == 995:
        probe = vec
    engine.write(i, ts, vec)

print(f"写入 1000 条，共 {engine.segment_count()} 段")

# 查询"最近 7 天"里和 id=995 最相似的 5 条
start = 93 * DAY
end = 100 * DAY
results = engine.query(start, end, probe, 5)

print("最近 7 天里最相似的 5 条：")
for rank, (rid, score) in enumerate(results):
    print(f"top{rank + 1}: id={rid}, score={score:.4f}")

# 因为查询向量就是 id=995 自己，所以 top1 一定是 id=995，score=1.0000

cd ~/m5_pyo3
maturin develop
python demo.py

写入 1000 条，共 10 段
最近 7 天里最相似的 5 条：
top1: id=995, score=1.0000
top2: id=930, score=0.2361
top3: id=967, score=0.1992
top4: id=958, score=0.1604
top5: id=946, score=0.1603