STL容器和大量数据

Question

我有一个大型的数据集合，需要读入内存 - 虽然是暂时性的，但对于系统来说是必要的。

我一直在检查std::vector和std::unordered_map的性能。对于std::vector，我使用了一个类型为struct的结构体：

struct information{
    std::string name;
    unsigned int offset;
}

“对于std::unordered_map，我使用std::string作为键，unsigned int offset作为值。如果说，有2000000个这样的数据被加载到内存中，我尝试了以下操作并得到了以下结果：使用std::vector，在随机字符串上进行操作，如果在向量上调用了reserve函数，则字符串长度通常不会超过32个字符。”

std::vector<information> vec;
vec.reserve(2500000);

插入

vec.push_back({dataName, offset});

"速度相当快。但查找数据的速度非常慢。查找是这样实现的："

auto it = std::find_if(vec.begin(), vec.end(), [&name](information &info) -> bool {return info.name == name); });

这很有道理，因为它是一个大向量，并且正确的struct是通过名称比较找到的。但性能非常差。内存使用情况良好——我认为内存增长的一部分原因是由于std::string大小调整。

我的向量实现问题是：有没有办法增加查找时间？我知道可以对向量进行排序以增加查找时间，但这样做会浪费在排序向量上的时间，尤其是在这样大小的向量上。

std::unordered_map：

插入

std::unordered_map<std::string, unsigned int> unordMap;
unordMap.reserve(2500000);
unordMap.emplace(name, offset);

需要很长时间。当事先保留空间以缩短插入时间时，会发生以下情况：

没有调用reserve时，插入完成后的内存比较大，但是仍然比vector实现多。reserve并不能真正提高插入时间。

当然查找速度非常快。我对于std::unordered_map的问题是：插入时间和内存使用能否得到改进？

如果这两个问题都无法解决，那么我的下一个问题可能很明显。是否有一种方法可以获得这两个数据结构之间的结果？哪种数据结构最适合处理大量数据？

- Jan Swart

---

你浪费在排序向量上的时间只有一次，如果你需要大量查找，排序就不会被重视。你可以后来使用二分查找进行查找。 - NetVipeC

我相信你在那里打错了 push_back()。 - Nasser Al-Shawwa

另外，虽然从您选择了“unordered_map”可以推断出来，但我还是要问一下：您是否可以有重复的字符串？ - Nasser Al-Shawwa

这个问题的一个问题是你在其中询问了5个问题... - Yakk - Adam Nevraumont

基本上，（在我看来）优化99%取决于选择正确的数据结构。那么你想用你的数据做什么？哪一部分需要快速处理？哪一部分可以稍等一下？ - IdeaHat

Answer 1

struct information{
  std::string name;
  unsigned int offset;
  information(information const&)=default;
  information(information&&)=default;
  information(std::string n, unsigned o):name(std::move(n)),offset(o),hash(std::hash<std::string>()(name)) {};
  information():information("",0) {};
  bool operator<( information const& o ) const {
    return tie() < o.tie();
  }
  std::tuple<std::size_t, std::string const&> tie() const { return std::tie(hash, name); }
private:
  std::size_t hash;
};

请使用以上结构来存储你的 std::vector。

在添加完所有数据后，进行std::sort排序。

要查找匹配 name 的内容，请执行以下操作：

struct information_searcher {
  struct helper {
    std::tuple<std::size_t, std::string const&> data;
    helper( std::string const& o ):data(std::hash<std::string>()(o), o) {};
    helper( helper const& o ) = default;
    helper( information const& o ):data(o.tie()) {}
    bool operator<( helper const& o ) const { return data < o.data; }
  };
  bool operator()( helper lhs, helper rhs ) const { return lhs < rhs; }
};

information* get_info_by_name( std::string const& name ) {
  auto range = std::equal_range( vec.begin(), vec.end(), information_searcher::helper(name), information_searcher{} );
  if (range.first == range.second) {
    return nullptr;
  } else {
    return &*range.first;
  }
}

这里做的是字符串哈希（用于快速比较），如果出现冲突则退回到std::string比较。

information_searcher是一个类，可以让我们在不必创建information（需要浪费内存）的情况下搜索数据。

get_info_by_name返回一个指针，如果未找到则返回nullptr，否则返回具有该名称的第一个元素的指针。

更改information.name是不礼貌的，并且会使hash字段不正确。

与简单的std::vector版本相比，这可能会使用略多一些的内存。

通常，如果您的工作包括“向表中添加大量内容”，然后“进行大量查找”，那么您最好构建一个std::vector，以快速的方式进行排序，然后使用equal_range进行查找。 map和unordered_map针对众多混合插入/删除等进行了优化。

这是一个几乎没有额外开销的查找。

- Yakk - Adam Nevraumont

---

这真的是一个很棒的答案！非常感谢你。 - Jan Swart

关于默认移动构造函数的说明。VS2013不会生成默认移动构造函数。 默认构造函数的类型无效 - Jan Swart

Answer 2

大向量的问题在于当你不知道想要对象的索引时查找时间很长。提高其性能的一种方法是，如您所述，保持有序向量并对其进行二进制搜索。这样，查找时间将不具有线性复杂度，而是具有对数复杂度，这可以为非常大的容器省下相当多的时间。这是std::map（有序的）中使用的查找方式。您可以使用std::lower_bound或std::equal_range在std::vector上执行类似的二进制搜索。

大型无序映射的问题完全不同：这种容器使用哈希函数和模数计算，以便将元素根据其键放置在标准数组中。因此，当您在std::unordered_map中有n个元素时，很可能您不仅需要一个长度为n的数组，因为某些索引将不会被填充。您将至少使用哈希和模数产生的最大索引。改善内存使用和插入时间的一种方法是编写自己的哈希函数。但这可能很难，具体取决于您使用的字符串类型。

- Nelfeal

---

std::hash 会产生整个 std::size_t 范围内的值，而 std::unordered_map 的桶数组中并没有那么多元素... - Yakk - Adam Nevraumont

@Yakk：谢谢，已修复。但是我不明白你的解决方案如何比直接使用lower_bound或equal_range更快地查找。你能解释一下吗（可以在这里、你的回答中或私信中）？ - Nelfeal

为什么要进行哈希？因为比较两个 std::string 很慢（你必须访问不那么近的内存（缓存未命中），然后你必须在它们不同或到达结尾时遍历它（不可预测的分支）。在数组中比较两个 std::size_t 是快速的（缓存一致性！）。你仍然会出现分支预测失败的情况（假设数据位于容器中的随机点，这是很可能的），但只有有限数量。还是你在谈论 information_searcher 吗？这样我们就不必把 std::string 复制到信息中。 - Yakk - Adam Nevraumont

@Yakk：哦，我现在明白它是如何工作的了。比较size_t比比较string确实更快。这对于特定的用途非常专业化，但我仍然学到了一些东西。关于你的information_searcher，最后一件事：它不能被像这样的tie调用替换吗？std::tie(std::hash(name), name) - Nelfeal

尝试一下 - 需要使用cast-to-tie获取信息或者在比较器上有4个重载。 - Yakk - Adam Nevraumont

Answer 3

向量通常被实现为“动态数组”，应该是最节省内存的。通过良好的保留策略，插入可以达到O(1) = 快速。搜索是O(n) = 非常差。

您可以通过对向量进行排序来帮助它（如果您首先加载，然后搜索，那么我认为这将是最好的 - std::sort + std::binary_search）。
您还可以使用std::lower_bound实现类似于插入排序的东西。插入= O(log n) = 好，搜索= O(log n) = 好

映射（有序）实际上可以完成相同的工作，但也可以使用树来实现= 内存利用率较低，访问与排序向量一样好（但可能没有重新分配，但在您的情况下，排序向量仍然是最好的）

unordered_map通常使用哈希表实现= 一些内存开销但操作快速（插入不能像未排序的向量那样快，但应该仍然很快）。散列的问题在于它可能会快甚至最快，但也可能是最糟糕的解决方案（在极端条件下）。上述结构（排序向量和map/tree）是稳定的，始终表现出相同的对数复杂度。

- firda

Answer 4

嗯，这里的最优解决方案是创建std :: map，它在插入和查找时的复杂度都是对数级别的。虽然我不明白为什么你不使用std :: vector。当使用快速排序对甚至2M个元素进行排序时，它非常快，特别是如果你只做一次。然后std :: binary_search就会非常快。如果你需要在插入之间进行大量查找，请好好考虑一下。

- Garrappachc

---

在上述情况下，std::map 以何种方式比 std::unordered_map 更快？ - Yakk - Adam Nevraumont

但是地图有很多内存开销，比向量多得多。我会研究对向量进行排序。 - Jan Swart