22

我正在使用map<MyStruct, I*> map1;. 显然，我的应用程序总时间的 9% 都花在了那里。特别是我的主要职能之一。地图不是很大（几乎总是<1k，<20 很常见）。

是否有我可能想要使用的替代实现？我想我不应该自己写，但如果我认为这是个好主意，我可以。

附加信息：我总是在添加元素之前检查。如果存在密钥，我需要报告问题。比在某一点之后，我将大量使用 map 进行查找，并且不会添加更多元素。

4

7 回答 7

56

首先，您需要了解什么是地图以及您正在执行的操作代表什么。Astd::map是平衡二叉树，查找将进行O( log N )操作，每个操作都是键的比较加上一些在大多数情况下可以忽略的额外内容（指针管理）。插入需要大致相同的时间来定位插入点，加上新节点的分配、实际插入树和重新平衡。O( log N )尽管隐藏常数更高，但复杂性再次增加。

当您尝试在插入之前确定键是否在映射中时，您将产生查找成本，如果查找不成功，则定位插入点的成本相同。std::map::insert您可以通过使用带有迭代器和布尔值的返回值来避免额外的成本，告诉您插入是否实际发生或元素已经存在。

除此之外，您需要了解比较密钥的成本有多大，这超出了问题所显示的范围（MyStruct可能只有一个int或一千个），这是您需要考虑的事情。

最后，可能 amap不是满足您需求的最有效的数据结构，您可能需要考虑使用std::unordered_map具有预期恒定时间插入（如果哈希函数不可怕）的（哈希表）或小数据集，甚至是一个普通的有序数组（或std::vector），您可以在其中使用二进制搜索来定位元素（这将减少分配的数量，但代价是插入成本更高，但如果保存的类型足够小，它可能值得）

与性能一样，衡量并尝试了解时间都花在了哪里。另请注意，在特定函数或数据结构上花费的 10% 时间可能很多或几乎没有，这取决于您的应用程序是什么。例如，如果您的应用程序只是在数据集中执行查找和插入操作，而这仅占用 10% 的 CPU，那么您在其他任何地方都需要进行大量优化！

于 2012-04-15T20:43:24.113 回答
10

可能只做一个insert并检查pair.secondis falseif key 是否已经存在会更快：

像这样

if ( myMap.insert( make_pair( MyStruct, I* ) ).second == false)
{
  // report error
}
else
  // inserted new value

...而不是find每次都打电话。

于 2012-04-15T20:27:16.733 回答
7

map您可以尝试unordered_map使用散列键而不是树来查找元素，而不是尝试。这个答案给出了一些提示，何时更unordered_map喜欢map。

于 2012-04-15T20:34:51.333 回答
5

这可能是一个长镜头，但对于小型集合，有时最关键的因素是缓存性能。

由于std::map实现了一个红黑树，它 [AFAIK] 的缓存效率不是很高 - 也许将地图实现为std::vector<pair<MyStruct,I*>>一个好主意，并在那里使用二进制搜索 [而不是地图查找]，至少它一旦你开始只查找 [停止插入元素] 应该是有效的，因为std::vector比map.

这个因素 [cpu-cache] 通常在大 O 表示法中被忽略并隐藏为常数，但对于大型集合，它可能会产生重大影响。

于 2012-04-15T20:30:53.847 回答
2

您使用地图的方式是基于MyStruct实例进行查找，并且根据您的特定实现，所需的比较可能会或可能不会很昂贵。

于 2012-04-15T20:27:48.043 回答
1

如评论中所述，没有正确的代码，几乎没有通用的答案可以给你。但是，如果MyStruct真的很大，则堆栈复制可能会很昂贵。也许存储指向MyStruct并实现自己的比较机制的指针是有意义的：

template <typename T> struct deref_cmp {
  bool operator()(std::shared_ptr<T> lhs, std::shared_ptr<T> rhs) const {
    return *lhs < *rhs;
  }
};

std::map<std::shared_ptr<MyStruct>, I*, deref_cmp<MyStruct>> mymap;

但是，这是您必须描述的内容。它可能会加快速度。

你会查找这样的元素

template <typename T> struct NullDeleter {
  void operator()(T const*) const {}
};
// needle being a MyStruct
mymap.find(std::shared_ptr<MyStruct>(&needle,NullDeleter()));

不用说，还有更多的优化潜力。

于 2012-04-15T20:45:05.633 回答
1

是否有我可能想要使用的替代实现？我想我不应该自己写，但如果我认为这是个好主意，我可以。

如果您对问题有足够的了解，您应该详细说明您的实现将如何变得更好。

map结构合适吗？如果是这样，那么您的标准库的实现可能质量很好（经过优化）。

比较可以MyStruct简化吗？

问题出在哪里——调整大小？抬头？

您是否将结构的复制和分配成本降至最低？

于 2012-04-15T20:32:42.143 回答