Rust

2025年10月04日更新 8 人订阅
原价: ¥ 6 限时优惠
专栏简介 Rust编程语言之错误处理 Rust 语言之 flod Rust编程语言之Cargo、Crates.io详解 Rust编程语言之枚举与模式匹配 Rust语言 - 接口设计的建议之受约束(Constrained) Rust编程语言之无畏并发 Rust语言 - 接口设计的建议之灵活(flexible) Rust语言 - 接口设计的建议之显而易见(Obvious) Rust语言 - 接口设计的建议之不意外(unsurprising) Rust 实战:构建实用的 CLI 工具 HTTPie Rust编程语言学习之高级特性 Rust内存管理揭秘:深度剖析指针与智能指针 解决Rust中数组和切片的编译时大小问题 《Rust编程之道》学习笔记一 Rust Async 异步编程 简易教程 使用 Async Rust 构建简单的 P2P 节点 Rust编程语言入门之模式匹配 Rust async 编程 Rust编程语言之编写自动化测试 Rust编程语言之函数式语言特性:迭代器和闭包 《Rust编程之道》学习笔记二 Rust Tips 比较数值 使用 Rust 开发一个微型游戏 Rust编程初探:深入理解Struct结构体 深入理解Rust中的内存管理:栈、堆与静态内存详解 深入理解 Rust 结构体:经典结构体、元组结构体和单元结构体的实现 深入掌握 Rust 结构体:从模板到实例化的完整指南 深入理解Rust中的结构体:逻辑与数据结合的实战示例 深入理解 Rust 枚举:从基础到实践 掌握Rust字符串的精髓:String与&str的最佳实践 全面解析 Rust 模块系统:实战案例与应用技巧 Rust 中的 HashMap 实战指南:理解与优化技巧 掌握Rust模式匹配:从基础语法到实际应用 Rust 中的面向对象编程:特性与实现指南 深入理解 Rust 的 Pin 和 Unpin:理论与实践解析 Rust Trait 与 Go Interface:从设计到实战的深度对比 从零开始:用 Rust 和 Axum 打造高效 Web 应用 Rust 错误处理详解:掌握 anyhow、thiserror 和 snafu Rust 如何优雅实现冒泡排序 链表倒数 K 节点怎么删?Python/Go/Rust 实战 用 Rust 玩转数据存储:JSON 文件持久化实战 Rust实战:打造高效字符串分割函数 如何高效学习一门技术:从知到行的飞轮效应 Rust 编程入门:Struct 让代码更优雅 Rust 编程:零基础入门高性能开发 用 Rust 写个猜数游戏,编程小白也能上手! Rust 入门教程:变量到数据类型,轻松掌握! 深入浅出 Rust:函数、控制流与所有权核心特性解析 从零开始:用 Rust 和 Axum 打造高效 Web 服务 Rust 集合类型解析:Vector、String、HashMap 深入浅出Rust:泛型、Trait与生命周期的硬核指南 Rust实战:博物馆门票限流系统设计与实现 用 Rust 打造高性能图片处理服务器:从零开始实现类似 Thumbor 的功能 Rust 编程入门实战:从零开始抓取网页并转换为 Markdown 深入浅出 Rust:高效处理二进制数据的 Bytes 与 BytesMut 实战 Rust智能指针:解锁内存管理的进阶之道 用 Rust 打造命令行利器:从零到一实现 mini-grep 解锁Rust代码组织:轻松掌握Package、Crate与Module Rust 所有权:从内存管理到生产力释放 深入解析 Rust 的面向对象编程:特性、实现与设计模式 Rust + Protobuf:从零打造高效键值存储项目 bacon 点燃 Rust:比 cargo-watch 更爽的开发体验 用 Rust 打造微型游戏:从零开始的 Flappy Dragon 开发之旅 函数式编程的Rust之旅:闭包与迭代器的深入解析与实践 探索Rust编程之道:从设计哲学到内存安全的学习笔记 精读《Rust编程之道》:吃透语言精要,彻底搞懂所有权与借用 Rust 避坑指南:搞定数值比较,别再让 0.1 + 0.2 != 0.3 困扰你! 告别 Vec!掌握 Rust bytes 库,解锁零拷贝的真正威力 告别竞态条件:基于 Axum 和 Serde 的 Rust 并发状态管理最佳实践 Rust 异步编程实践:从 Tokio 基础到阻塞任务处理模式 Rust 网络编程实战:用 Tokio 手写一个迷你 TCP 反向代理 (minginx) 保姆级教程:Zsh + Oh My Zsh 终极配置,让你的 Ubuntu 终端效率倍增 不止于后端:Rust 在 Web 开发中的崛起之路 (2024数据解读) Rust核心利器:枚举(Enum)与模式匹配(Match),告别空指针,写出优雅健壮的代码 Rust 错误处理终极指南:从 panic! 到 Result 的优雅之道 想用 Rust 开发游戏?这份超详细的入门教程请收好! 用 Rust 实现 HTTPie:一个现代 CLI 工具的构建过程 Rust 异步实战:从0到1,用 Tokio 打造一个高性能并发聊天室 深入 Rust 核心:彻底搞懂指针、引用与智能指针 Rust 生产级后端实战:用 Axum + sqlx 打造高性能短链接服务 深入 Rust 内存模型:栈、堆、所有权与底层原理 Rust 核心概念解析:引用、借用与内部可变性 掌握 Rust 核心:生命周期与借用检查全解析 Rust 内存布局深度解析:从对齐、填充到 repr 属性 Rust Trait 分派机制:静态与动态的抉择与权衡 Rust Thread::Builder 用法详解:线程命名与栈大小设置 Rust 泛型 Trait:关联类型与泛型参数的核心区别 Rust Scoped Threads 实战:更安全、更简洁的并发编程 Rust 核心设计:孤儿规则与代码一致性解析 Rust 实战:从零构建一个多线程 Web 服务器 Rust Web 开发实战:构建教师管理 API 硬核实战:从零到一,用 Rust 和 Axum 构建高性能聊天服务后端 Rust Web 开发实战:使用 SQLx 连接 PostgreSQL 数据库 硬核入门:从零开始,用 Actix Web 构建你的第一个 Rust REST API (推荐 🔥) Rust 并发编程:详解线程间数据共享的几种核心方法 Rust并发安全基石:Mutex与RwLock深度解析 Rust Web实战:构建优雅的 Actix Web 统一错误处理 煮咖啡里的大学问:用 Rust Async/Await 告诉你如何边烧水边磨豆 深入浅出:Rust 原子类型与多线程编程实践 Rust 并发编程利器:OnceCell 与 OnceLock 深度解析 Rust 懒人编程:LazyCell 与 LazyLock 的惰性哲学 Rust 入门精髓:详解 Enum 的三种魔法,从模式匹配到状态管理 Rust 字符串魔法:String 与 &str 的深度解析与实践 Rust 模块化编程:驾驭代码结构与可见性的三大法则 Rust 实用进阶:深度剖析 Rust 生命周期的奥秘 Rust 智能指针大揭秘:Box、Rc、Arc、Cow 深度剖析与应用实践 Rust 并发编程三步曲:Join、Arc<Mutex> 与 mpsc 通道同步实战 Rust 声明宏实战进阶:从基础定义到 #[macro_export] 与多规则重载 Rust 类型转换实战:利用 From/Into Trait 实现带 Default 容错的安全转换 Rust 实战:实现 FromStr Trait,定制化字符串 parse() 与精确错误报告 Rust 实战:TryFrom Trait——如何在类型转换中强制执行业务逻辑检查 Rust 泛型编程基石:AsRef 和 AsMut 的核心作用与实战应用 揭秘 Rust Unsafe 编程:程序员接管内存安全的契约与实践 Rust FFI 入门:extern、ABI 与底层符号链接解析 Rust性能优化:零内存拷贝的链表合并技术实战

Rust性能优化:零内存拷贝的链表合并技术实战

Rust性能优化:零内存拷贝的链表合并技术实战Rust以其内存安全和零成本抽象著称,但在实现如链表合并这类底层数据结构和算法时,为追求极致性能,我们必须深入unsafe领域。本文将实战一种基于裸指针(NonNull)的单向有序链表合并技术。该技术巧妙地绕过Rust的所有权系统,实现

Rust性能优化:零内存拷贝的链表合并技术实战

Rust 以其内存安全和零成本抽象著称,但在实现如链表合并这类底层数据结构和算法时,为追求极致性能,我们必须深入 unsafe 领域。本文将实战一种基于 裸指针 (NonNull) 的单向有序链表合并技术。该技术巧妙地绕过 Rust 的所有权系统,实现了零内存拷贝O(N+M) 合并算法,性能媲美 C 语言。同时,我们将重点展示如何通过正确实现 Drop trait,来确保我们在获得高性能的同时,依然能兑现 Rust 对内存安全的承诺

💻 实战代码清单:

基于 NonNull 的高性能链表实现

/*
    single linked list merge
*/

use std::fmt::{self, Display, Formatter};
use std::ptr::NonNull;
use std::vec::*;

#[derive(Debug)]
struct Node&lt;T> {
    val: T,
    next: Option&lt;NonNull&lt;Node&lt;T>>>,
}

impl&lt;T> Node&lt;T> {
    fn new(t: T) -> Node&lt;T> {
        Node { val: t, next: None }
    }
}
#[derive(Debug)]
struct LinkedList&lt;T> {
    length: u32,
    start: Option&lt;NonNull&lt;Node&lt;T>>>,
    end: Option&lt;NonNull&lt;Node&lt;T>>>,
}

impl&lt;T> Default for LinkedList&lt;T> {
    fn default() -> Self {
        Self::new()
    }
}

impl&lt;T> LinkedList&lt;T> {
    pub fn new() -> Self {
        Self {
            length: 0,
            start: None,
            end: None,
        }
    }

    pub fn add(&mut self, obj: T) {
        let mut node = Box::new(Node::new(obj));
        node.next = None;
        let node_ptr = Some(unsafe { NonNull::new_unchecked(Box::into_raw(node)) });
        match self.end {
            None => self.start = node_ptr,
            Some(end_ptr) => unsafe { (*end_ptr.as_ptr()).next = node_ptr },
        }
        self.end = node_ptr;
        self.length += 1;
    }

    pub fn get(&mut self, index: i32) -> Option&lt;&T> {
        self.get_ith_node(self.start, index)
    }

    fn get_ith_node(&mut self, node: Option&lt;NonNull&lt;Node&lt;T>>>, index: i32) -> Option&lt;&T> {
        match node {
            None => None,
            Some(next_ptr) => match index {
                0 => Some(unsafe { &(*next_ptr.as_ptr()).val }),
                _ => self.get_ith_node(unsafe { (*next_ptr.as_ptr()).next }, index - 1),
            },
        }
    }
    pub fn merge(list_a: LinkedList&lt;T>, list_b: LinkedList&lt;T>) -> Self
    where
        T: PartialOrd,
    {
        unsafe {
            let mut current_a = list_a.start;
            let mut current_b = list_b.start;
            let mut result = Self::new();
            result.length = list_a.length + list_b.length;

            // current_merged_ptr 始终指向已合并部分的最后一个节点。
            let mut current_merged_ptr: Option&lt;NonNull&lt;Node&lt;T>>> = None;

            // --- 1. 确定合并链表的起始节点 ---
            let initial_choice = loop {
                match (current_a, current_b) {
                    (Some(a_ptr), Some(b_ptr)) => {
                        let a_val = &(*a_ptr.as_ptr()).val;
                        let b_val = &(*b_ptr.as_ptr()).val;

                        // 比较值并选择较小的节点
                        if a_val &lt;= b_val {
                            current_a = (*a_ptr.as_ptr()).next; // 推进 A 的指针
                            break Some(a_ptr);
                        } else {
                            current_b = (*b_ptr.as_ptr()).next; // 推进 B 的指针
                            break Some(b_ptr);
                        }
                    }
                    // 如果其中一个链表为空,则起始节点是另一个链表的头
                    (Some(a_ptr), None) => break Some(a_ptr),
                    (None, Some(b_ptr)) => break Some(b_ptr),
                    (None, None) => break None, // 两个链表都为空
                }
            };

            if initial_choice.is_none() {
                return Self::new(); // 返回空链表
            }

            // 设置结果链表的 start 和初始 merged_ptr
            result.start = initial_choice;
            current_merged_ptr = initial_choice;

            // --- 2. 循环合并剩余的节点 ---
            while current_a.is_some() && current_b.is_some() {
                let next_node_to_link: NonNull&lt;Node&lt;T>>;
                let a_ptr = current_a.unwrap();
                let b_ptr = current_b.unwrap();

                let a_val = &(*a_ptr.as_ptr()).val;
                let b_val = &(*b_ptr.as_ptr()).val;

                if a_val &lt;= b_val {
                    next_node_to_link = a_ptr;
                    current_a = (*a_ptr.as_ptr()).next; // 推进 A
                } else {
                    next_node_to_link = b_ptr;
                    current_b = (*b_ptr.as_ptr()).next; // 推进 B
                }

                // 将已合并节点的 next 指针指向新选中的节点
                (*current_merged_ptr.unwrap().as_ptr()).next = Some(next_node_to_link);

                // 推进 current_merged_ptr
                current_merged_ptr = Some(next_node_to_link);
            }

            // --- 3. 连接剩余部分 (其中一个链表已耗尽) ---
            let remainder = current_a.or(current_b);

            if let Some(end_ptr) = current_merged_ptr {
                // 将 merged 链表的末尾连接到剩余部分的起始
                (*end_ptr.as_ptr()).next = remainder;
            }

            // --- 4. 确定最终的 end 指针 ---
            result.end = if remainder.is_some() {
                // 如果有剩余部分,则 end 是原链表的 end
                if current_a.is_some() {
                    list_a.end
                } else {
                    // current_b 必须是 Some
                    list_b.end
                }
            } else {
                // 如果没有剩余,则 end 是最后连接的节点
                current_merged_ptr
            };

            result
        }
    }
}

// ----------------------------------------------------
// ✅ 内存安全保障:实现 Drop Trait
// ----------------------------------------------------
impl&lt;T> Drop for LinkedList&lt;T> {
    fn drop(&mut self) {
        // 从链表头开始,依次将裸指针转换回 Box,触发 Box 的析构函数,从而安全释放内存。
        let mut current = self.start.take();

        while let Some(node_ptr) = current {
            // SAFETY: 
            // 1. 我们正在 Drop 链表,保证了对该内存的所有权唯一性。
            // 2. 将 NonNull&lt;T> 转换回 Box,以便 Rust 能够释放内存。
            let node_ptr_raw = node_ptr.as_ptr() as *mut Node&lt;T>;
            let node = unsafe { Box::from_raw(node_ptr_raw) };

            // 移动到下一个节点,当前节点 (node) 在作用域结束时被安全释放。
            current = node.next.take();
        }
    }
}
// ----------------------------------------------------

impl&lt;T> Display for LinkedList&lt;T>
where
    T: Display,
{
    fn fmt(&self, f: &mut Formatter) -> fmt::Result {
        match self.start {
            Some(node) => write!(f, "{}", unsafe { node.as_ref() }),
            None => Ok(()),
        }
    }
}

impl&lt;T> Display for Node&lt;T>
where
    T: Display,
{
    fn fmt(&self, f: &mut Formatter) -> fmt::Result {
        match self.next {
            Some(node) => write!(f, "{}, {}", self.val, unsafe { node.as_ref() }),
            None => write!(f, "{}", self.val),
        }
    }
}

#[cfg(test)]
mod tests {
    use super::LinkedList;

    #[test]
    fn create_numeric_list() {
        let mut list = LinkedList::&lt;i32>::new();
        list.add(1);
        list.add(2);
        list.add(3);
        println!("Linked List is {}", list);
        assert_eq!(3, list.length);
    }

    #[test]
    fn create_string_list() {
        let mut list_str = LinkedList::&lt;String>::new();
        list_str.add("A".to_string());
        list_str.add("B".to_string());
        list_str.add("C".to_string());
        println!("Linked List is {}", list_str);
        assert_eq!(3, list_str.length);
    }

    #[test]
    fn test_merge_linked_list_1() {
        let mut list_a = LinkedList::&lt;i32>::new();
        let mut list_b = LinkedList::&lt;i32>::new();
        let vec_a = vec![1, 3, 5, 7];
        let vec_b = vec![2, 4, 6, 8];
        let target_vec = vec![1, 2, 3, 4, 5, 6, 7, 8];

        for i in 0..vec_a.len() {
            list_a.add(vec_a[i]);
        }
        for i in 0..vec_b.len() {
            list_b.add(vec_b[i]);
        }
        println!("list a {} list b {}", list_a, list_b);
        let mut list_c = LinkedList::&lt;i32>::merge(list_a, list_b);
        println!("merged List is {}", list_c);
        for i in 0..target_vec.len() {
            assert_eq!(target_vec[i], *list_c.get(i as i32).unwrap());
        }
    }
    #[test]
    fn test_merge_linked_list_2() {
        let mut list_a = LinkedList::&lt;i32>::new();
        let mut list_b = LinkedList::&lt;i32>::new();
        let vec_a = vec![11, 33, 44, 88, 89, 90, 100];
        let vec_b = vec![1, 22, 30, 45];
        let target_vec = vec![1, 11, 22, 30, 33, 44, 45, 88, 89, 90, 100];

        for i in 0..vec_a.len() {
            list_a.add(vec_a[i]);
        }
        for i in 0..vec_b.len() {
            list_b.add(vec_b[i]);
        }
        println!("list a {} list b {}", list_a, list_b);
        let mut list_c = LinkedList::&lt;i32>::merge(list_a, list_b);
        println!("merged List is {}", list_c);
        for i in 0..target_vec.len() {
            assert_eq!(target_vec[i], *list_c.get(i as i32).unwrap());
        }
    }
}

Rust unsafe 单链表实现

及零拷贝合并算法详解

这段 Rust 代码实现了一个高性能的单向链表 (LinkedList&lt;T>),它通过使用 裸指针 (std::ptr::NonNull) 绕过 Rust 的所有权系统,从而能够构建链表这种自引用的数据结构。这种实现方式能够提供与 C/C++ 媲美的性能,因为操作的是原始内存地址,而其最关键之处在于正确实现了 Drop trait,确保了在高性能的同时依然能保持 Rust 的内存安全承诺。

核心结构与内存管理

链表的核心由 Node&lt;T>LinkedList&lt;T> 两个结构体构成。Node&lt;T> 包含数据 val 和指向下一个节点的指针 next。这个 next 字段被定义为 Option&lt;NonNull&lt;Node&lt;T>>>NonNull 是一个非空裸指针,它的使用是绕开 Rust 所有权检查、构建链表的唯一途径。LinkedList&lt;T> 则作为链表的容器,维护着 length、链表头部 start 和链表尾部 end 的裸指针。end 指针是关键优化,它确保了 add 方法(在链表尾部添加元素)的时间复杂度为 O(1)。

节点添加 (add) 与所有权交接

add 方法是手动内存管理的关键。它首先使用 Box::new() 在堆上安全地创建新节点,并由 Box 拥有所有权。随后,它调用 Box::into_raw(node),这是一个所有权交接的仪式Box 放弃了对堆内存的所有权,并返回一个 \*mut Node&lt;T> 原始指针。一旦使用了 into_raw,Rust 就停止自动管理这块内存,程序员必须负责其生命周期。接下来的代码在 unsafe 块中执行:它将原始指针封装成 NonNull,然后通过解引用旧的 end 指针,修改其 next 字段,将新节点链接到链表的末尾。

访问元素 (get) 与安全封装

get 方法提供了按索引访问元素的功能。它通过递归的 get_ith_node 方法遍历链表查找目标节点。其核心在于 *`unsafe { &(next_ptr.as_ptr()).val }**,它在unsafe块内进行裸指针的解引用,访问节点数据,但最终返回给调用者的是一个**安全的、不可变的 Rust 引用 (&T)**。这种模式是将底层的不安全操作封装起来,向外部暴露一个安全的 API。值得注意的是,get方法的签名使用了&mut self,尽管它只是只读操作,更规范的 Rust 做法应该是使用&self`。

核心算法:零拷贝有序合并 (merge)

merge 方法是这段代码的精华,它实现了两个已排序链表的高效合并。该函数以的形式接收 list_alist_b,从而获得了两个链表中所有节点的独占所有权。算法的核心在于其零内存拷贝策略,时间复杂度为 O(N + M),性能极高。

  1. 确定起点: 算法首先比较两个链表的头节点,选择值较小的一个作为新合并链表的起点。
  2. 主循环重链接: 在 while 循环中,它不断比较 list_alist_b 的当前节点,选择值较小的节点。零拷贝是通过 *`(current_merged_ptr.unwrap().as_ptr()).next = Some(next_node_to_link)** 实现的——直接在unsafe块中修改已合并链表尾部节点的next` 裸指针,将其指向新选中的节点,不涉及任何数据复制或内存分配
  3. 连接剩余部分: 当其中一个链表遍历完后,另一个链表剩余的已排序部分(remainder)会通过一个 O(1) 的操作被整体嫁接到新链表的末尾,避免了逐个节点遍历和链接的开销。
  4. 尾部维护: 最后,根据是否有剩余部分被连接,正确设置新链表的 result.end 指针。

内存安全保障 (Drop Trait)

由于 add 中使用了 Box::into_raw 放弃了所有权,Drop trait 的实现是保证内存安全的关键Drop::drop 方法通过遍历链表,对每个 NonNull 裸指针调用 unsafe { Box::from_raw(ptr) }。这一操作将裸指针恢复为 Box&lt;Node&lt;T>>,重新建立 Rust 所有权。当这个临时的 Box 离开作用域时,Rust 的析构系统会自动触发 Box 的内存释放,安全地回收了所有堆内存,从而避免了内存泄漏。正是这一机制,使得这段 unsafe 链表代码成为了一个在性能和安全之间取得平衡的健壮实现。

总结

本次实战成功展示了在 Rust 中利用 unsafe 裸指针实现一个极高性能、零内存拷贝的有序链表合并算法。该算法的关键在于直接操作指针进行链表重链接,避免了数据复制,从而将时间复杂度优化到 O(N+M) 的理论最优水平。最重要的是,我们通过 Drop trait 机制,利用 Box::from_raw 恢复了对裸指针指向内存的所有权并触发了自动析构,有效防止了内存泄漏。这一实现是 Rust 开发者在追求极致性能时,如何将 性能与内存安全 结合的最佳范例。

参考

点赞 0
收藏 0
分享
本文参与登链社区写作激励计划 ,好文好收益,欢迎正在阅读的你也加入。

0 条评论

请先 登录 后评论