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 回答