c – 构建大型(ish)无序集合,并在开头提供所有可用数据

发布时间：2020-12-16 10:06:53 所属栏目：百科来源：网络整理

导读：我有一种情况需要优化无序集的创建.预期的元素数量约为5-25M.我的第一个想法是,我应事先准备好所有数据并做类似的事情 unordered_set s(data); 代替 for (auto elem : data) s.insert(elem); STL无序集可以使用批量加载方法并加速其创建吗？如果我在表格构造

我有一种情况需要优化无序集的创建.预期的元素数量约为5-25M.我的第一个想法是,我应事先准备好所有数据并做类似的事情

unordered_set s(data);

代替

for (auto& elem : data)
    s.insert(elem);

STL无序集可以使用批量加载方法并加速其创建吗？如果我在表格构造之前知道预期的元素数量,我该如何调整哈希表的参数(桶大小等)？

解决方法

My focus now is on whether I can use functions like rehash to notify the table for the upcoming size

假设你打电话

unordered_set s(begin(data),end(data));

虽然标准没有规定实现,但是良好的实现将能够辨别元素的数量,并相应地预先分配大小.例如,如果你查看gcc使用的源代码(由我/usr/include / c /5/tr1/hashtable.h),它会使用它

_M_bucket_count = std::max(_M_rehash_policy._M_next_bkt(__bucket_hint),_M_rehash_policy.
                _M_bkt_for_elements(__detail::
                            __distance_fw(__f,__l)));
 _M_buckets = _M_allocate_buckets(_M_bucket_count);

所以它已经根据元素的数量预先分配了大小.

但问题可能不同.如果你看一下the documentation,它说：

constructs the container with the contents of the range [first,last). Sets max_load_factor() to 1.0.

这样可以节省空间,但可能会导致冲突.为了减少碰撞,你可以使用

unordered_set s(begin(data),end(data),k * data.size());

其中k> 1是一些常数.这对应于1 / k的负载系数.因人而异.

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!