Как объединить два элемента списка в Rust?

Question

Я пытался оптимизировать часть своего кода и попал в область, где, как мне кажется, я мог бы использовать некоторую мудрость сообщества.По сути, я пытаюсь объединить два элемента списка, не перемещая элементы в списке (с помощью двух удалений и вставки), потому что, насколько я могу судить, в 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());
    }
}

---

Что касается того, окажется ли это лучшепроизводительность, чем другой подход, трудно сказать.Ваша отправная точка кажется довольно сложной, и если вы можете упростить это и использовать другую базовую структуру данных, то вам следует попробовать и сравнить ее.Я часто удивляюсь фактической скорости операций O (n) на Vec, даже когда размер составляет около 1000 или более элементов.