7

我最近才开始研究 boost 和它的容器，我在网上和 stackoverflow 上阅读了几篇文章，认为 boost::unordered_map 是大型集合中性能最快的容器。所以，我有这个类状态，它在容器中必须是唯一的（没有重复），容器中将有数百万甚至数十亿的状态。因此，我一直在尝试将其优化为小尺寸和尽可能少的计算。我之前使用过 boost::ptr_vector，但正如我在 stackoverflow 上所读到的，只要其中没有那么多对象，向量才是好的。在我的例子中，状态描述了来自机器人的感觉运动信息，因此可能存在大量状态，因此快速查找是重中之重。遵循boost 文档对于 unordered_map，我意识到我可以做两件事来加快速度：使用 hash_function，并使用相等运算符根据它们的 hash_function 比较状态。因此，我实现了一个私有 hash() 函数，它接收状态信息并使用 boost::hash_combine 创建一个 std::size_t 哈希值。operator== 基本上比较状态的哈希值。所以：

  • std::size_t 是否足以涵盖数十亿可能的 hash_function 组合？为了避免重复状态，我打算使用它们的 hash_values。

  • 创建 state_map 时，我应该使用 State* 还是哈希值作为键？即：boost::unordered_map<State*,std::size_t> state_map; 或 boost::unordered_map<std::size_t,State*> state_map;

  • boost::unordered_map::iterator = state_map.find() 的查找时间是否比通过 boost::ptr_vector 并比较每个迭代器的键值更快？

  • 最后，任何关于如何优化这种无序地图以实现速度和快速查找的提示或技巧将不胜感激。

编辑：我已经看到了很多答案，一个是不使用 boost 但 C++0X，另一个不使用 unordered_set，但老实说，我仍然想看看 boost::unordered_set 如何与散列函数一起使用. 我遵循了boost的文档并实现了，但我仍然无法弄清楚如何将boost的散列函数与有序集一起使用。

4

3 回答 3

4

这有点糊涂了。

  • 你所说的不是“你可以做些什么来加快速度”；相反，它们是您的类型的强制性要求，才有资格作为无序映射的元素类型，也适用于无序集（您可能更想要）。

  • 您需要提供一个比较对象的相等运算符，而不是哈希值。相等的全部意义在于区分具有相同散列的元素。

  • size_t是无符号整数类型，在 x86 上为 32 位，在 x64 上为 64 位。由于您想要“数十亿个元素”，这意味着许多 GB 的数据，我假设您无论如何都有一台可靠的 x64 机器。

  • 关键是你的散列函数是好的，即很少有冲突。

  • 你想要一个集合，而不是地图。将对象直接放入集合中：std::unordered_set<State>. 如果您要映射到某物，例如将状态映射到其他某物，请使用地图。哦，如果可以的话，使用 C++0x，而不是 boost。

  • 使用hash_combine是好的。

宝贝示例：

struct State
{
  inline bool operator==(const State &) const;
  /* Stuff */
};

namespace std
{
  template <> struct hash<State>
  {
    inline std::size_t operator()(const State & s) const
    {
      /* your hash algorithm here */
    }
  };
}

std::size_t Foo(const State & s) { /* some code */ }

int main()
{
  std::unordered_set<State> states; // no extra data needed
  std::unordered_set<State, Foo> states; // another hash function
}
于 2011-07-14T00:30:52.320 回答
2

unordered_map 是一个哈希表。您不存储哈希值；它作为存储和查找方法在内部完成。

鉴于您的要求， unordered_set 可能更合适，因为您的对象是唯一要存储的项目。

不过，您有点困惑——相等运算符和散列函数并不是真正的性能项目，而是容器正常工作的重要对象所必需的。一个好的散列函数会将您的节点均匀地分布在桶中，并且相等运算符将用于消除基于散列函数的匹配的任何歧义。

std::size_t 适用于散列函数。请记住，没有散列是完美的；会有碰撞，这些碰撞项存储在该桶位置的链表中。

因此， .find() 在最佳情况下为 O(1)，在平均情况下非常接近 O(1)（在最坏情况下为 O(N)，但体面的散列函数可以避免这种情况。）

您没有提及您的平台或架构；在数十亿个条目中，您可能仍然需要担心内存不足的情况，具体取决于这些情况和 State 对象的大小。

于 2011-07-14T00:28:56.220 回答
2

忘记哈希；没有任何东西（至少从你的问题来看）表明你有一个有意义的钥匙；

让我们退后一步，重新表述您的实际绩效目标：

  • 您想快速验证任何 State 对象都不存在重复项

如果我需要添加其他人，请发表评论。

从上述目标和您的评论来看，我建议您实际上使用ordered_set而不是unordered_map。是的，有序搜索使用二进制搜索 O(log (n))，而无序使用查找 O(1)。

但是，不同之处在于，使用这种方法，您只需要ordered_set 来检查在您即将创建新状态时（即在状态创建时间）是否已经不存在类似状态。

在所有其他查找中，您实际上不需要查看ordered_set！因为你已经有了钥匙；State*，key 可以通过魔术解引用操作符访问值：*key

因此，使用这种方法，您仅使用ordered_set 作为索引来仅在创建时间验证状态。在所有其他情况下，您可以使用指针值键的解引用运算符访问您的状态。

如果以上所有内容都不足以说服您，那么这里是使用哈希快速确定相等性的想法的最后一颗钉子；哈希函数发生碰撞的概率很小，但随着状态数量的增加，该概率将变得完全确定。因此，根据您的容错能力，您将处理状态冲突（从您的问题和您期望处理的状态数量来看，您似乎会处理很多）

为此，您显然需要比较谓词来测试您的状态的所有内部属性（陀螺仪、推进器、加速度计、质子射线等）

于 2011-07-14T01:03:05.083 回答