根据同一 Vec 的其他元素删除 Vec 元素的最佳方法

Question

我有一个集合向量，我想删除作为向量中其他集合的子集的所有集合。示例：

a = {0, 3, 5}
b = {0, 5}
c = {0, 2, 3}

在这种情况下，我想删除 b，因为它是 a 的子集。我可以使用 "dumb" n² 算法。

遗憾的是，让它与借用检查器一起工作非常棘手。我想到的最好的是 (Playground):

let mut v: Vec<HashSet<u8>> = vec![];

let mut to_delete = Vec::new();
for (i, set_a) in v.iter().enumerate().rev() {
    for set_b in &v[..i] {
        if set_a.is_subset(&set_b) {
            to_delete.push(i);
            break;
        }
    }
}

for i in to_delete {
    v.swap_remove(i);
}

(注意：上面的代码不正确！更多细节见评论)

我看到了一些缺点：

我需要一个带有额外分配的额外向量
也许有比经常调用 swap_remove 更有效的方法
如果我需要保留顺序，我不能使用 swap_remove，但必须使用 remove，它很慢

有更好的方法吗？我不只是问我的用例，而是关于标题中描述的一般情况。

Answer 1

您可以使用 while 循环代替 for：

use std::collections::HashSet;

fn main() {
    let arr: &[&[u8]] = &[
        &[3],
        &[1,2,3],
        &[1,3],
        &[1,4],
        &[2,3]
    ];

    let mut v:Vec<HashSet<u8>> = arr.iter()
        .map(|x| x.iter().cloned().collect())
        .collect();

    let mut pos = 0;
    while pos < v.len() {
        let is_sub = v[pos+1..].iter().any(|x| v[pos].is_subset(x)) 
            || v[..pos].iter().any(|x| v[pos].is_subset(x));

        if is_sub {
            v.swap_remove(pos);
        } else {
            pos+=1;
        }
    }
    println!("{:?}", v);
}

没有额外的分配。

为避免使用remove和swap_remove，您可以将向量类型更改为Vec<Option<HashSet<u8>>>:

use std::collections::HashSet;

fn main() {
    let arr: &[&[u8]] = &[
        &[3],
        &[1,2,3],
        &[1,3],
        &[1,4],
        &[2,3]
    ];

    let mut v:Vec<Option<HashSet<u8>>> = arr.iter()
        .map(|x| Some(x.iter().cloned().collect()))
        .collect();

    for pos in 0..v.len(){
        let is_sub = match v[pos].as_ref() {
            Some(chk) => 
                v[..pos].iter().flat_map(|x| x).any(|x| chk.is_subset(x)) 
                ||  v[pos+1..].iter().flat_map(|x| x).any(|x| chk.is_subset(x)),
            None => false,
        };

        if is_sub { v[pos]=None };//Replace with None instead remove

    }
    println!("{:?}", v);//[None, Some({3, 2, 1}), None, Some({1, 4}), None]
}

Answer 2

I need an additional vector with additional allocations

我不担心该分配，因为与算法的其余部分相比，该分配的内存和运行时占用空间非常小。

Maybe there are more efficient ways than calling swap_remove often.

If I need to preserve order, I can't use swap_remove, but have to use remove which is slow

我会将 to_delete 从 Vec<usize> 更改为 Vec<bool> 并标记是否应删除特定的哈希图。然后您可以使用 Vec::retain, which conditionaly removes elements while preserving order. Unfortunately, this function doesn't pass the index to the closure, so we have to create a workaround (playground):

let mut to_delete = vec![false; v.len()];
for (i, set_a) in v.iter().enumerate().rev() {
    for set_b in &v[..i] {
        if set_a.is_subset(&set_b) {
            to_delete[i] = true;
        }
    }
}

{
    // This assumes that retain checks the elements in the order.
    let mut i = 0;
    v.retain(|_| {
        let ret = !to_delete[i];
        i += 1;
        ret
    });
}

如果你的 hashmap 有一个在正常情况下永远不会出现的特殊值，你可以用它来标记一个 hashmap 为 "to delete"，然后在 retain 中检查那个条件（它需要将外部循环从基于迭代器更改为基于范围）。

旁注（如果 HashSet<u8> 不仅仅是一个玩具示例）：更有效的存储和比较小整数集的方法是使用 bitset.

Answer 3

这里有一个不进行额外分配并保留顺序的解决方案：

fn product_retain<T, F>(v: &mut Vec<T>, mut pred: F)
    where F: FnMut(&T, &T) -> bool
{
    let mut j = 0;
    for i in 0..v.len() {
        // invariants:
        // items v[0..j] will be kept
        // items v[j..i] will be removed
        if (0..j).chain(i + 1..v.len()).all(|a| pred(&v[i], &v[a])) {
            v.swap(i, j);
            j += 1;
        }
    }
    v.truncate(j);
}

fn main() {
    // test with a simpler example
    // unique elements
    let mut v = vec![1, 2, 3];
    product_retain(&mut v, |a, b| a != b);
    assert_eq!(vec![1, 2, 3], v);

    let mut v = vec![1, 3, 2, 4, 5, 1, 2, 4];
    product_retain(&mut v, |a, b| a != b);
    assert_eq!(vec![3, 5, 1, 2, 4], v);
}

这是一种分区算法。第一个分区中的元素将被保留，第二个分区中的元素将被删除。

根据同一 Vec 的其他元素删除 Vec 元素的最佳方法

Best way to remove elements of Vec depending on other elements of the same Vec

rust

borrow-checker