我一直在努力尝试优化我的代码部分,我已经到了一个我认为可以使用社区智慧的领域。我实际上是在尝试合并列表中的两个元素而不移动列表中的元素(通过两个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);
}
}
我希望能够在列表中包含两个元素,将它们合并为一个伪元素,其中前两个“元素”实际上只是指向同一个新元素的指针。但是,我无法在不复制列表中的内存或结构的情况下找到这样做的方法。
我对您的要求的理解是,您需要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个或更多。