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

Question

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

4

我一直在尝试优化代码中的某一部分，但我遇到了一个需要社区智慧的地方。我实际上想要合并列表中的两个元素，而不移动列表中的元素（通过两个删除和一个插入），因为在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);
    }
}

我希望能够将列表中的两个元素合并为一个伪元素，其中前两个“元素”实际上只是指向同一个新元素的指针。但是，我正在努力寻找一种在不在列表中复制内存或结构的情况下完成此操作的方法。

- ChosunOne

1

你可能想得太多了，把它变得比必要的更加复杂了。很难确切地看出你正在寻找什么，但也许你只需要一个不同的数据结构，比如 VecDeque。 - Peter Hall

1

类似这样的东西？https://play.rust-lang.org/?version=stable&mode=debug&edition=2018&gist=76d3cc91046b742fa2877b4b46282c97 - Peter Hall

2

为什么同时涉及到Vec和BinaryHeap？当你说要编辑列表中的元素时，是指Vec还是BinaryHeap？ - michalsrb

1

这让我很困惑。在while循环中，first和next不再是任何列表的成员，因为a已经被删除并且你将它们从b中弹出了。所以...如果你想要的话，你可以重新分配它们（first = new_num; next = new_num;），测试就会通过。但是听起来你想对一些其他数据结构产生副作用，而这些数据结构没有显示出来？或者你想对堆的其他元素产生副作用？我不明白。 - trent

1

我投票关闭你的问题，因为昨天它不清楚，我不理解。请毫不犹豫地[编辑]它以澄清你的问题。 - Stargateur

显示剩余3条评论

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Peter Hall · Accepted Answer

我理解您的要求是需要 Vec 能够容纳既可以是值，又可以是对其他项的引用，同时保持与您提供的结构类似。

我们可以通过将项目类型更改为 enum 来模拟该过程，它可以容纳值或对其他项目的引用：

最初的回答：

根据您的需求，我理解您希望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()
        }
    }
}

If you create a new value like this:

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上执行O(n)操作的实际速度感到惊讶，即使大小约为1000个项目或更多。

最初的回答：

无法确定这种方法是否比其他方法更优。你的起点看起来相当复杂，如果你能简化它并使用不同的底层数据结构，那么就应该尝试并做一些基准测试。我经常对在Vec上执行O(n)操作的实际速度感到惊讶，即使大小约为1000个项目或更多。