快速'group by/count' std：：vector<std：：u16string> 变成 std：：map<u16string， int>

Question

我有一个函数，可以将~10000个单词读入一个向量，然后我想将所有单词分组到一个地图中以"计算"某个单词出现的次数。

虽然代码"有效"，但有时可能需要 2 秒钟才能重新构建地图。

注意：不幸的是，我无法更改"读取"功能，我必须使用std::u16string向量。

std::vector<std::u16string> vValues;
vValues.push_back( ... )
...
std::map<std::u16string, int> mValues;
for( auto it = vValues.begin(); it != vValues.end(); ++it )
{
if( mValues.find( *it ) == mValues.end() )
{
mValues[*it] = 1;
}
else
{
++mValues[*it];
}
}

如何在跟踪单词在向量中出现的次数的同时加快"分组依据"的速度？

Answer 1

如果您在新密钥上调用std::map::operator[]，则密钥的值将被初始化为值(对于像int这样的 POD，为 0)。因此，您的循环可以简化为：

for (auto it = vValues.begin(); it != vValues.end(); ++it)
++mValues[*it];

如果没有键*it，则默认值将为0，但随后它立即递增，变为1。

如果密钥已存在，则只需递增即可。

此外，看起来您不需要对地图进行排序，因此您可以使用std::unordered_map代替，因为插入是平均常量时间，而不是对数，这会进一步加快速度。

Answer 2

std::vector<std::u16string> vValues;
vValues.push_back( ... )
...
std::sort( vValues.begin(), vValues.end() );
struct counted {
std::u16string value;
std::size_t count;
};
std::vector<counted> result;
auto it = vValues.begin();
while (it != vValues.end()) {
auto r = std::equal_range( it, vValues.end(), *it );
result.push_back({ *it, r.second-r.first });
it = r.second;
}

完成此操作后，result将包含每个值的{value, count}并进行排序。

由于所有工作都是在连续容器中完成的，因此它应该比您的实现更快。

如果你不允许vValues突变，你可以做的一件事是从中创建一个gsl::span<char16_t>向量，然后对其进行排序，然后类似地创建result向量。 (如果你没有gsl::span，写一个，它们不难写)

如果做不到这一点，即使复制一次result也可能比原始解决方案更快。

在counted中使用gsl::span<char16_t const>也会节省一些分配(在vValues中重用存储，代价是将它们的生命周期捆绑在一起。

一个严重的问题是，如果您的字符串非常长，则确定两个字符串相等是昂贵的。 如果它们具有共同的前缀，则确定它们不同可能会很昂贵。 我们在equal_range代码中对每个不同元素进行log(n) 比较，在排序中进行 n log(n) 比较;有时，排序(字符串哈希，字符串)对可能比单独排序(字符串)更快，因为它使字符串不同易于检测。

具有 4 个不同版本的现场示例。 只需将test1更改为test2或test3或test4.

test3在我做的每个测试中都是最快的：

std::unordered_map<std::string, int> test3(std::vector<std::string> vValues)
{
std::unordered_map<std::string, int> mValues;
for( auto it = vValues.begin(); it != vValues.end(); ++it )
{
++mValues[std::move(*it)];
}
return mValues;
}

比所有其他版本。

Answer 3

这是一个替代方案。 您可以考虑存储非拥有共享指针，但如果您无法控制输入的格式，Yakk 的gsl::span建议可能会起作用。 这是来自指南支持库。

std::unordered_map<std::u16string, unsigned> hash_corpus;
// constexpr float heuristic_parameter = ?;
// hash_corpus.max_load_factor(heuristic_parameter);
/* The maximum possible number of entries in the hash table is the size of
* the input vector.
*/
hash_corpus.reserve(corpus.size());
// Paul McKenzie suggested this trick in the comments:
for ( const std::u16string& s : corpus)
++hash_corpus[s]; // If the key is not in the table, [] inserts with value 0.