合并两个Vec<(u32, Vec<u8>）>没有重复的键

Question

我有 2 个向量，其类型为

Vec(u32, Vec<u8>)

。我想合并这两个向量，并且希望结果具有唯一的键。如果密钥相同，第二个向量应覆盖第一个向量。

这是我解决这个问题的尝试：

pub fn merge(old_v: Vec<(u32, Vec<u8>)>, new_v: Vec<(u32, Vec<u8>)>) -> Vec<(u32, Vec<u8>)> {
    let mut new_map = HashMap::<u32, Vec<u8>>::from_iter(old_v);

    new_map.extend(new_v);
    new_map.into_iter().collect()
}

这可行，但问题是，这些向量携带相当大的数据，可能有 500 KB 到 1 MB 的数据，有数千个条目（尤其是

old_v

）。考虑到我在应用程序中非常频繁地调用此方法，此方法会创建相当多的内存。

有什么办法可以提高这种方法的效率吗？我可以进行就地突变。

Answer 1

如果输入已预先排序，您可以将两个输入合并为迭代器，在键上合并，并仅选择具有匹配键的最后一个输入。通过将每个元素的平均情况

O(1)

操作（具有适度的恒定开销和较差的内存局部性）替换为严格的

O(1)

操作（具有较低的恒定开销和良好的内存局部性），这可能会做得更好一点。

粗略示例使用

itertools

板条箱以避免重新发明轮子：

use itertools::Itertools; // 0.13.0

pub fn merge(old_v: Vec<(u32, Vec<u8>)>, new_v: Vec<(u32, Vec<u8>)>) -> Vec<(u32, Vec<u8>)> {
    old_v.into_iter()
        .merge_by(new_v, |(k1, _), (k2, _)| k1 <= k2)
        .coalesce(|a, b|
            if a.0 == b.0 {
                Ok(b)
            } else {
                Err((a, b))
            }
        ).collect()
}

Rust Playground 链接

就像我说的，这假设输入是按提供的键排序的，如果不是，则会出现错误行为。在完成其余工作之前，您可以将

Vec

接收为可变的，并为它们接收

.sort_by_key(|(k, _)| k)

（并且

.sort_by_key

明确指出，如果输入已经排序，则工作是线性的，而不是标准的

O(n log n) 

）。但是，如果输入未排序，则通过执行完整的

HashMap

排序，您可能会比您的

O(n log n)

解决方案做更多的工作。

假设不能假设排序输入是这种情况，那么您所得到的看起来是最佳的。您使用

IntoIterator

获得输入的所有权（在使用输入时隐式，在转换回结果时显式），因此您正在执行纯粹的移动。您的增量内存开销只是基于元组中内联存储的内容的额外内存（

u32

和一小部分指针

Vec

是根据从您构造

HashMap

时被清空来实现的）在

Vec

完全清空并释放底层存储之前的

Vec

），你没有复制任何内部的

Vec

。

我认为针对非排序输入改进它的最好方法是完全避免存储内部

Vec

，因此您只存储用于唯一性检查的键，并通过保留第一个来执行更少（诚然便宜）的移动立即看到项目，在识别后立即丢弃重复项而不移动。

itertools

在这里也有帮助，代码非常简单，但它确实隐藏了一个

HashSet

来执行唯一化，所以它确实需要some辅助内存：

use itertools::Itertools; // 0.13.0
use itertools::chain;

pub fn merge(old_v: Vec<(u32, Vec<u8>)>, new_v: Vec<(u32, Vec<u8>)>) -> Vec<(u32, Vec<u8>)> {
    // new_v comes first because first value seen is kept, and the rest are discarded
    chain!(new_v, old_v).unique_by(|(k, _)| *k).collect()
}

Rust Playground 链接