3

我想实现一个性能优化的变体,unordered_map它分几个阶段工作:

  1. 初始化:插入大约 100 个元素std::map
  2. 准备:做一些魔法,转换std::map成一个变种std::unordered_map
  3. 工作:执行大量(无限)查找;禁止插入/删除

为了使“工作”阶段尽可能快,我想选择一个对给定键集没有冲突的散列函数(在初始化阶段收集)。

我想衡量我可以从这个技巧中获得多少性能改进。所以这将是一个实验,可能会进入生产代码。

标准库是否有实现此功能的工具(例如,查找给定的碰撞次数unordered_map;或更改散列函数)?还是我应该自己实现?

4

3 回答 3

6

这是“碰撞管理”API:

size_type bucket_count() const;
size_type max_bucket_count() const;

size_type bucket_size(size_type n) const;
size_type bucket(const key_type& k) const;

local_iterator       begin(size_type n);
local_iterator       end(size_type n);
const_local_iterator begin(size_type n) const;
const_local_iterator end(size_type n) const;
const_local_iterator cbegin(size_type n) const;
const_local_iterator cend(size_type n) const;

简而言之,bucket_size(n)为您提供第 n 个存储桶的碰撞次数。您可以使用键查找存储桶,也可以使用 local_iterator 遍历存储桶。

为了更改散列函数,我将分配/构造一个新容器,从旧散列函数到新容器。

于 2011-04-11T15:13:54.880 回答
2

如果您有很多读取和较少的写入,您可以使用向量作为映射。这很常见,因为lower_bound它比内存更有效map并且使用更少的空间:

bool your_less_function( const your_type &a, const your_type &b )
{
  // based on keys
  return ( a < b );
}
...
std::vector<your_type> ordered-vector;

添加值时:

...
// First 100 values
ordered-vector.push_back(value)
...
// Finally. The vector must be sorted before read.
std::sort( ordered-vector.begin(), ordered-vector.end(), your_less_function );

询问数据时:

std::vector<your_type>::iterator iter = std::lower_bound( ordered-vector.begin(), ordered-vector.end(), value, your_less_function );
if ( ( iter == ordered-vector.end() ) || your_less_function( *iter, value ) )
  // you did not find the value
else
  // iter contains the value

不幸的是,它是订购的,但真的很快。

于 2011-04-11T14:44:58.060 回答
0

冲突的数量取决于桶的数量。根据boost 文档,使用 rehash 函数将桶数设置为 100 对您有用吗?

于 2011-04-11T14:39:27.947 回答