performance - HashMap 和 Vec 之间的内存高效转换

Question

我正在尝试转换一个大 HashMap<K, V>至 Vec<(K, V)> .通常的做法是这样的:

// initialize HashMap
let cap = 50000000;
let mut hm: HashMap<usize, usize> = HashMap::new();
for i in 0..cap {
    hm.insert(i, i);
}
// convert HashMap to Vec
let vec = hm.into_iter().collect::<Vec<(usize, usize)>>();

如果 HashMap，此代码将无法正常工作足够大 - 在调用 collect() 的开始, 原文HashMap仍将在内存中并且Vec将分配取自 Iterator 的较小尺寸提示的容量.这会导致非常大的内存不足 panic HashMap s，即使我应该能够在这两种类型之间进行转换，而额外的内存开销却很少。到目前为止，我想出了以下解决方案:

// create small vector
let mut vec: Vec<(usize, usize)> = Vec::with_capacity(100);
for i in hm.into_iter() {
    vec.push(i);
    // reserve few megabytes
    if vec.capacity() - vec.len() < 10 {
        vec.reserve_exact(1000000);
    }
}

是否有更好(更有效或更惯用)的方法来解决这个问题？我愿意用unsafe如果要提高性能，请编写代码。

编辑正如所指出的into_iter不会在迭代期间取消分配，因此建议的解决方案无法按预期工作。除了转储之外，还有其他方法可以转换这些集合吗 HashMap到文件，然后将该文件读入 Vec ？

Answer 1

预先分配所需的确切数量是内存和时间高效的解决方案。

假设您要创建一个包含 100 个项目的向量。如果你要为 50 个项目分配空间，当你去添加第 51 个项目时，存在两种可能性:

1. 可以原地延长分配，您可以继续您的快乐之路。
2. 无法就地扩展分配，因此进行了新的更大的分配。所有的数据都需要从之前的分配中复制过来；可能是 O(n) 操作。在此复制期间，两个分配都处于事件状态，占用 50 + 100 个槽，比原始分配大小合适时更多空间。

不可能知道会发生哪种情况，因此您必须假设最坏的情况。

这就是 Iterator 具有 size_hint 方法的原因之一:知道要分配多少项会更有效率。

另一方面，HashMap 可能将数据存储在一个大的分配中，因为它更有效。这意味着不可能(或者可能不容易/有效)移出一个项目然后减少分配。即使您可以这样做，在副本的开头，您也会分配整个 HashMap 和 Vec。

我认为有两种可能可以改善这种情况:

1. 如果 HashMap 将数据内部存储在 Vec 中，则可以向 HashMap 添加一个返回该 Vec 的方法 经过最后一刻的 sanitizer 。
2. 完全避免存储 HashMap 和/或 Vec。例如，如果你需要遍历数据，你不需要先collect到一个Vec；只是迭代它。