我在 std::map 上执行大量查找、插入和删除操作。我正在考虑添加一些代码来优化速度,但我想收集一些关于当前工作负载的统计数据。具体来说,我想跟踪每次调用必须遍历多少个节点'find',这样我就可以保持运行记录。
我在想,如果我的地图中的大多数更改都发生在前面,那么在使用“查找”使用的树之前搜索前 N 个条目可能会更好。
我在 std::map 上执行大量查找、插入和删除操作。我正在考虑添加一些代码来优化速度,但我想收集一些关于当前工作负载的统计数据。具体来说,我想跟踪每次调用必须遍历多少个节点'find',这样我就可以保持运行记录。
我在想,如果我的地图中的大多数更改都发生在前面,那么在使用“查找”使用的树之前搜索前 N 个条目可能会更好。
Find 必须使用地图的比较功能来比较元素,因此您可以提供一个自定义比较功能来计算它被调用的次数,以便查看它在每次调用时做了多少工作(基本上遍历了多少节点)。
不过,在这种情况下,我看不出在调用 find() 之前搜索前 N 个条目有什么帮助。遍历映射中的条目只是按排序顺序遍历树,因此它不能比调用 find() 更有效,除非您的比较函数比检查相等性要昂贵得多。
示例代码:
#include <algorithm>
#include <iostream>
#include <map>
#include <numeric>
#include <vector>
using namespace std;
int main() {
vector<int> v(100);
iota(begin(v), end(v), 0);
vector<pair<int, int>> vp(v.size());
transform(begin(v), end(v), begin(vp), [](int i) { return make_pair(i, i); });
int compareCount = 0;
auto countingCompare = [&](int x, int y) { ++compareCount; return x < y; };
map<int, int, decltype(countingCompare)> m(begin(vp), end(vp), countingCompare);
cout << "Compares during construction: " << compareCount << "\n";
compareCount = 0;
auto pos = m.find(50);
cout << "Compares during find(): " << compareCount << "\n";
}
如果它对您的键/值结构可行,则值得考虑unordered_map
(在 C++11 或 TR1 中)作为替代方案。 std::map
,作为一棵平衡树,在这种使用情况下不太可能表现良好,并且搜索前 N 的混合方法对我来说似乎是很多工作而没有保证的回报。