c++ - 查找整数值计数的最快方法 (C++)

Question

我需要一个无符号整数列表中每个出现值的出现次数。 IE。如果传递序列 [ 3, 6, 9, 3, 9 ] 我想要 [ { 3, 2}, {6, 1}, {9, 2} ]。

这些值是随机的 32 位无符号整数(范围为 1 到 1,000,000,000)。结果可以存储在任何数据结构中(只要它们可以线性迭代)，虽然排序的值是理想的，但这是速度之后的次要问题。

目前我有-

T UniqueCount(std::vector<unsigned> &A)
{
    std::unordered_map<unsigned,unsigned> value_counts;

    for(unsigned val : A) {
        value_counts[val]++;
    }

    A.clear();

    ...
}

分析显示 std::unordered_map 比 std::map 更快。

有更好的方法吗？/更快的方式？值得注意的是，用例 (count > 4) 可以记录为 4。

目前这是一个瓶颈，因此虽然标准容器是首选，但如果性能提升值得额外的维护成本，则可以考虑定制容器。

Answer 1

在我的系统(Win10 x64，MSVC daily package x64 发布版本)上，使用输入 vector 中的 100,000 个随机未排序值进行测试，以下使用 std::sort + std::adjacent_find 使用 std::unordered_map 和@krzaq 答案中的代码(现在在 OP 中)在 ~10ms 与 ~27ms 之间执行:

std::vector<std::pair<unsigned, unsigned>> unique_count(std::vector<unsigned>& a) {
    auto it = begin(a);
    auto const last = end(a);

    std::vector<std::pair<unsigned, unsigned>> value_counts;
    std::sort(it, last);
    while (it != last) {
        auto const prev = it;
        it = std::adjacent_find(it, last, std::not_equal_to<unsigned>{});
        if (it != last) {
            ++it;
        }
        value_counts.emplace_back(*prev, static_cast<unsigned>(it - prev));
    }
    return value_counts;
}

Online Demo

经验教训:缓存一致性通常胜过算法的复杂性。