英文:
Rust sets that can create a clone in O(1) and can be updated separately
问题
我有一组数字，set1 = {1,2,3,4,5}，我想在O(1)时间内创建set1的克隆（副本）。
我知道可以使用Rc和Box来实现这一点。
假设这个副本称为set2。
我还想分别更新set1和set2。
例如，
set1.insert(10);
set2.insert(6);
所以最终，我将会有
set1 = {1,2,3,4,5,10}
set2 = {1,2,3,4,5,6}
集合中的元素不会被移除或更新，
我尝试过很多方法，但似乎在某些时候会有一个O(n)的操作来克隆所有元素。
英文:
I have a set of numbers, set1 = {1,2,3,4,5}
and I want to create a clone (copy) of set1 in O(1).
I know I can do this using Rc, Box.
Assume this copy is set2.
I also want to update set1 and set2 separately.
For example
set1.insert(10);
set2.insert(6);
so at the end of the day, I will have
set1 = {1,2,3,4,5,10}
set2 = {1,2,3,4,5,6}
Elements in the set will not be removed or updated,
I've tried a lot of methods, but it seems at some point there will be an O(n) operation that clone all elements.
答案1
得分: 4
为了克隆一个包含n个元素的数据结构，使新的数据结构拥有原始元素的副本，至少需要O(n)的时间复杂度。即使克隆只是复制一块连续的内存块，它仍然是O(n)。
由于您的需求不涉及更新“克隆”的数据，您可以使用Rc或Arc来共享它：
use std::{collections::HashSet, hash::Hash, cmp::Eq, rc::Rc};
pub struct PartiallySharedHashSet<T> {
shared: Rc<HashSet<T>>,
own: HashSet<T>,
}
impl<T: Hash + Eq> PartiallySharedHashSet<T> {
pub fn new(shared: Rc<HashSet<T>>) -> Self {
Self {
shared,
own: HashSet::new()
}
}
pub fn insert(&mut self, item: T) -> bool {
if self.shared.contains(&item) {
false
} else {
self.own.insert(item)
}
}
pub fn contains(&self, item: &T) -> bool {
self.own.contains(item) || self.shared.contains(item)
}
}
用法：
fn main() {
let mut set = HashSet::new();
set.insert(1);
let set = Rc::new(set);
let mut set1 = PartiallySharedHashSet::new(set.clone());
set1.insert(2);
let mut set2 = PartiallySharedHashSet::new(set);
set2.insert(3);
assert!(set1.contains(&1));
assert!(set1.contains(&2));
assert!(!set1.contains(&3));
assert!(set2.contains(&1));
assert!(!set2.contains(&2));
assert!(set2.contains(&3));
}
英文:
To clone a data structure containing n elements so that the new structure has its own copy of the original elements must take at least O(n) time complexity. Even if cloning is just copying a contiguous block of memory, it's fast but it's still O(n).
Since your requirement doesn't involve updating the "cloned" data, you can instead share it using Rc or Arc:
use std::{collections::HashSet, hash::Hash, cmp::Eq, rc::Rc};
pub struct PartiallySharedHashSet<T> {
shared: Rc<HashSet<T>>,
own: HashSet<T>,
}
impl<T: Hash + Eq> PartiallySharedHashSet<T> {
pub fn new(shared: Rc<HashSet<T>>) -> Self {
Self {
shared,
own: HashSet::new()
}
}
pub fn insert(&mut self, item: T) -> bool {
if self.shared.contains(&item) {
false
} else {
self.own.insert(item)
}
}
pub fn contains(&self, item: &T) -> bool {
self.own.contains(item) || self.shared.contains(item)
}
}
Usage:
fn main() {
let mut set = HashSet::new();
set.insert(1);
let set = Rc::new(set);
let mut set1 = PartiallySharedHashSet::new(set.clone());
set1.insert(2);
let mut set2 = PartiallySharedHashSet::new(set);
set2.insert(3);
assert!(set1.contains(&1));
assert!(set1.contains(&2));
assert!(!set1.contains(&3));
assert!(set2.contains(&1));
assert!(!set2.contains(&2));
assert!(set2.contains(&3));
}
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库，让每个人都能够通过互相帮助和分享经验来进步。
评论