有没有零拷贝的方法来找到任意数量的集合的交集？

Question

这是一个简单的例子，展示了我正在尝试做的事情：

use std::collections::HashSet;

fn main() {
    let mut sets: Vec<HashSet<char>> = vec![];

    let mut set = HashSet::new();
    set.insert('a');
    set.insert('b');
    set.insert('c');
    set.insert('d');
    sets.push(set);

    let mut set = HashSet::new();
    set.insert('a');
    set.insert('b');
    set.insert('d');
    set.insert('e');
    sets.push(set);

    let mut set = HashSet::new();
    set.insert('a');
    set.insert('b');
    set.insert('f');
    set.insert('g');
    sets.push(set);

    // Simple intersection of two sets
    let simple_intersection = sets[0].intersection(&sets[1]);
    println!("Intersection of 0 and 1: {:?}", simple_intersection);

    let mut iter = sets.iter();
    let base = iter.next().unwrap().clone();
    let intersection = iter.fold(base, |acc, set| acc.intersection(set).map(|x| x.clone()).collect());
    println!("Intersection of all: {:?}", intersection);
}

此解决方案使用 fold 来“累积”交集，使用第一个元素作为初始值。

Intersections 是惰性迭代器，它遍历对相关集合的引用。由于累加器必须与第一个元素具有相同的类型，因此我们必须克隆每个集合的元素。如果不克隆，我们无法从引用中创建一组拥有的数据。我想我明白了。

例如，这行不通：

let mut iter = sets.iter();
let mut base = iter.next().unwrap();
let intersection = iter.fold(base, |acc, set| acc.intersection(set).collect());
println!("Intersection of all: {:?}", intersection);

error[E0277]: a value of type `&HashSet<char>` cannot be built from an iterator over elements of type `&char`
  --> src/main.rs:41:73
   |
41 |     let intersection = iter.fold(base, |acc, set| acc.intersection(set).collect());
   |                                                                         ^^^^^^^ value of type `&HashSet<char>` cannot be built from `std::iter::Iterator<Item=&char>`
   |
   = help: the trait `FromIterator<&char>` is not implemented for `&HashSet<char>`

即使明白了这一点，我还是不想克隆数据。理论上它不应该是必要的，我有原始向量中的数据，我应该能够使用参考。那会大大加快我的算法。这是一个纯粹的学术追求，所以我有兴趣让它尽可能快。

为此，我需要在 HashSet<&char> 中累积，但我不能这样做，因为我无法将 HashSet<&char> 与 HashSet<char> 相交关闭。所以好像我被卡住了。有什么办法吗？

或者，我可以为向量中的每个集合创建一组引用，但这似乎并没有好多少。它甚至可以工作吗？我可能运行遇到同样的问题，但使用双重引用。

最后，我实际上不需要保留原始数据，所以我可以将元素移动到累加器集中。我不知道如何做到这一点，因为我必须通过 intersection 这给了我参考。

以上方案是否可行？是否还有其他一些我没有看到的零拷贝解决方案？

Answer 1

Finally, I don't actually need to retain the original data.

这真的很简单。

首先，可选择按大小对集合进行排序。那么：

let (intersection, others) = sets.split_at_mut(1);
let intersection = &mut intersection[0];
for other in others {
    intersection.retain(|e| other.contains(e));
}

Answer 2

Finally, I don't actually need to retain the original data, so I'd be okay moving the elements into the accumulator set.

retain 方法将完全满足您的要求：

fn intersection(mut sets: Vec<HashSet<char>>) -> HashSet<char> {
    if sets.is_empty() {
        return HashSet::new();
    }
    
    if sets.len() == 1 {
        return sets.pop().unwrap();
    }
    
    let mut result = sets.pop().unwrap();
    result.retain(|item| {
        sets.iter().all(|set| set.contains(item))
    });
    result
}

playground

Answer 3

您可以使用 filter and all:

以完全懒惰的方式完成

sets[0].iter().filter (move |c| sets[1..].iter().all (|s| s.contains (c)))

Playground

有没有零拷贝的方法来找到任意数量的集合的交集？

Is there a zero-copy way to find the intersection of an arbitrary number of sets?

set

set-intersection

rust