评估 unordered_map 性能的正确方法是什么? [C++14]
在我的代码中,我以数十亿个键的顺序非常广泛地使用 std::unordered_map。出于性能的目的,我想知道 unordered_map 的行为,因为它必须重新散列多少次以及所有其他参数(有多少个桶?在重新散列之前有多少个空桶?)。我知道 STL 提供了桶的数量。但是还需要什么来分析或者您使用什么来分析?
最佳答案
像许多 std 容器一样,unordered_map 的大小必须呈指数增长。确切的速率是实现定义的;您可以检查您的实现规范或其源代码。
它如何调整大小是确定性的。如果将其包裹在垫片中,则可以通过在允许增长容器的每个操作前后检查 bucket_count 来检测这些调整大小。
您可以遍历存储桶:
template<class UnorderedMeow>
std::size_t empty_buckets( UnorderedMeow&& meow ) {
std::size_t r = 0;
auto buckets = meow.buckets_count();
for (decltype(buckets) i = 0; i < buckets; ++i)
if (meow.bucket_size(i)==0)
++r;
return r;
}
找出有多少是空的。
如果您使用基于继承的组合并仅覆盖那些您知道可以添加/删除内容的对象...
template<class Base>
struct instrumented_unordered_map:Base {
using Self = instrumented_unordered_map;
using Base::Base;
using key_type = Base::key_type; // etc
struct instrument {
Self* self;
instrument( Self* s ):self(s) {
self->start_instrument();
}
~instrument() {
self->end_instrument();
}
};
struct instrument_state {
// blah
};
instrument_state state;
void start_instrument() {
// populate state
}
void end_instrument() {
// extract from state, generate report
}
decltype(auto) operator[]( key_type const& key ) {
instrument _(this);
return Base::operator[](key);
}
// etc
};
关于c++ - 计算 unordered_map 中重新散列的次数,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/42494961/