如何合并Rust中列表的两个元素？

Question

我一直在努力尝试优化我的代码部分，我已经到了一个我认为可以使用社区智慧的领域。我实际上是在尝试合并列表中的两个元素而不移动列表中的元素（通过两个remove和一个插入），因为据我所知，Rust这样做的向量花费O（n）时间。

看一下捕获问题本质的代码：

use std::cell::RefCell;
use std::rc::Rc;
use std::collections::BinaryHeap;

#[derive(PartialOrd, Ord, PartialEq, Eq)]
pub struct Num {
    pub num: usize
}

impl Num {
    pub fn new(num: usize) -> Num {
        Num {
            num
        }
    }
}

fn main() {
    let mut a = vec![];
    for i in 0..10 {
        a.push(Rc::new(RefCell::new(Num::new(i))));
    }
    let mut b = BinaryHeap::with_capacity(a.len());
    for i in 0..a.len() - 1 {
        b.push((i, Rc::clone(&a[i]), Rc::clone(&a[i + 1])));
    }

    drop(a);

    while !b.is_empty() {
        let c = b.pop().unwrap();
        let first = c.1;
        let next = c.2;
        println!("c: c.0: {}", c.0);
        println!("c: first.num before: {}", RefCell::borrow(&first).num);
        println!("c: next.num before: {}", RefCell::borrow(&next).num);

        // Here I want to replace the two structs referenced in first and next
        // with a single new struct that first and next both point to.
        // e.g. first -> new_num <- next

        println!("c: first.num after: {}", RefCell::borrow(&first).num);
        println!("c: next.num after: {}", RefCell::borrow(&next).num);
        assert_eq!(RefCell::borrow(&first).num, RefCell::borrow(&next).num);
    }
}

我希望能够在列表中包含两个元素，将它们合并为一个伪元素，其中前两个“元素”实际上只是指向同一个新元素的指针。但是，我无法在不复制列表中的内存或结构的情况下找到这样做的方法。

Answer 1

我对您的要求的理解是，您需要Vec能够保存作为另一个项目的值或参考的项目，同时保持结构类似于您所呈现的结构。

我们可以通过将您的项目类型更改为enum来建模，

pub enum Num {
    Raw(usize),
    Ref(Rc<RefCell<Num>>),
}

可以包含值或对另一个项目的引用：

impl Num {
    pub fn new(num: usize) -> Num {
        Num::Raw(num)
    }

    pub fn new_ref(other: Rc<RefCell<Num>>) -> Num {
        Num::Ref(other)    
    }

    pub fn get_num(&self) -> usize {
        match &self {
            Num::Raw(n) => *n,
            Num::Ref(r) => r.borrow().get_num()
        }
    }
}

并添加方法以包含用于构造不同变体和访问基础数值的抽象：

let new_num = Rc::new(RefCell::new(Num::new(100)));

如果您创建一个这样的新值：

*first.borrow_mut() = Num::new_ref(Rc::clone(&new_num));
*next.borrow_mut() = Num::new_ref(Rc::clone(&new_num));

您可以在其他节点中引用它，如下所示：

use std::cell::RefCell;
use std::rc::Rc;
use std::collections::BinaryHeap;

#[derive(PartialOrd, Ord, PartialEq, Eq)]
pub enum Num {
    Raw(usize),
    Ref(Rc<RefCell<Num>>),
}

impl Num {
    pub fn new(num: usize) -> Num {
        Num::Raw(num)
    }

    pub fn new_ref(other: Rc<RefCell<Num>>) -> Num {
        Num::Ref(other)    
    }

    pub fn get_num(&self) -> usize {
        match &self {
            Num::Raw(n) => *n,
            Num::Ref(r) => r.borrow().get_num()
        }
    }
}

fn main() {
    let mut a = vec![];
    for i in 0..10 {
        a.push(Rc::new(RefCell::new(Num::new(i))));
    }
    let mut b = BinaryHeap::with_capacity(a.len());
    for i in 0..a.len() - 1 {
        b.push((i, Rc::clone(&a[i]), Rc::clone(&a[i + 1])));
    }

    drop(a);

    let new_num = Rc::new(RefCell::new(Num::new(100)));

    while !b.is_empty() {
        let c = b.pop().unwrap();
        let first = c.1;
        let next = c.2;
        println!("c: c.0: {}", c.0);
        println!("c: first.num before: {}", RefCell::borrow(&first).get_num());
        println!("c: next.num before: {}", RefCell::borrow(&next).get_num());

        *first.borrow_mut() = Num::new_ref(Rc::clone(&new_num))
        *next.borrow_mut() = Num::new_ref(Rc::clone(&new_num))

        println!("c: first.num after: {}", RefCell::borrow(&first).get_num());
        println!("c: next.num after: {}", RefCell::borrow(&next).get_num());
        assert_eq!(RefCell::borrow(&first).get_num(), RefCell::borrow(&next).get_num());
    }
}

完整代码如下所示：

Vec

---

至于这是否会表现出比不同方法更好的表现，很难说。您的起点似乎相当复杂，如果您可以简化并使用不同的底层数据结构，那么您应该尝试它并进行基准测试。我经常对qazxswpoi上O（n）操作的实际速度感到惊讶，即使尺寸大约是1000个或更多。