根据同一Vec中的其他元素，移除Vec元素的最佳方法

Question

我有一个集合向量，需要移除其中所有是其他集合子集的集合。例如：

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

在这种情况下，我想删除b，因为它是a的子集。我可以使用一个“愚蠢”的n²算法，但是很不幸，用借用检查器使其正常工作非常棘手。我能想到的最好方法是（示例代码）：

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。

是否有更好的方法来解决这个问题？ 我不仅仅询问我的用例，还涉及到标题描述的一般情况。

- Lukas Kalbertodt

---

这个算法不正确，它只删除向量中更早的集合的子集。示例：https://play.rust-lang.org/?gist=88e20f4386f3d5df3fe57fe3a1372dfa&version=stable&backtrace=0 - Chris Emerson

注意：通过构建临时数组（并按顺序推入元素），然后将其与原始数组交换，可以实现保留顺序并避免重新分配内存。不过目前还不清楚什么是临界点。 - Matthieu M.

这里需要保持顺序吗？如果不需要，我会先按大小对向量进行排序，这样就可以避免双向子集检查（并删除右侧的检查）。 - Chris Emerson

@ChrisEmerson 谢谢！我不会在问题中修复我的代码，而是添加一条注释说明它是不正确的。但你提出的修改的想法很好:) - Lukas Kalbertodt

Answer 1

以下是一种不需要进行额外分配并且保留顺序的解决方案：

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);
}

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

- malbarbo

---

如果谓词是交换的，那么内部循环可以从 j 开始，对吗？如果是这样，我们能否将其编码到 Rust 的类型系统中，以便在适当时自动选择更高效的实现方式？ - michael_j_ward

Answer 2

您可以使用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]
}

- aSpex

Answer 3

我需要一个额外的向量来进行额外的分配。

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

也许有比频繁调用 swap_remove 更有效的方法。

如果我需要保留顺序，我不能使用 swap_remove，而必须使用 remove ，但这很慢。

我会把to_delete从Vec<usize>改为Vec<bool>，并标记应该删除哪个特定的哈希表。然后，您可以使用Vec::retain，它可以有条件地删除元素同时保留顺序。不幸的是，这个函数不会将索引传递给闭包，所以我们必须创建一个解决方法(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
    });
}

如果您的哈希表有一个在正常情况下永远不会出现的特殊值，您可以使用它来标记哈希表为“待删除”，然后在retain中检查该条件（这将需要将外部循环从基于迭代器改为基于范围）。

---

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

- krdln

---

相信保留遍历元素的顺序并不是一个真正的选择 :/ 第二个想法是将对象设置为向量中的特殊值，并使用基于范围的循环进行迭代，这是有趣的。另外，顺便说一下：是的，这不仅仅是一个玩具示例（实际上非常关键），我已经在使用 BitSet :) 谢谢！ - Lukas Kalbertodt

@LukasKalbertodt retain方法：此方法在原地操作并保留所保留元素的顺序。 我认为不允许更改。 - Shepmaster

在我的理解中，那句话是关于保留后的顺序，而不是访问元素的顺序。然而，我无法想象出一种有效的实现方式，可以按不同的顺序检查元素。 - krdln