在C++中查找整数值的最快方法

Question

我需要对一组无符号整数列表中每个出现的值进行计数。例如，如果传递序列[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更快。

有没有更好的方法？更快的方式？值得注意的是，由于使用情况（计数>4）可以记录为4。

目前这是一个瓶颈，虽然标准容器是首选，但如果性能提升超过额外的维护成本，则可以考虑使用自定义容器。

- Hector

---

PS：你可以直接将计数存储到“_vals”中，例如将循环中的所有内容替换为“_vals[*it] ++”（或“value_counts[*it] ++”或其他值，很难说），因为“operator []”会插入一个具有默认值的项（在您的情况下为0），并返回对该值的引用。 - Jason C

谢谢 - @krzaq 建议了同样的事情。我已经更新了我的代码。 - Hector

你可能想解释为什么这段代码是一个瓶颈。是否频繁重新生成一组新的随机值？如果是这样，为什么不在生成随机值的过程中同时生成计数，而不是之后再生成？此外（虽然很小），请记住unsigned不能保证能表示32位的值，因此在移植代码时可能存在正确性的潜在问题。 - Peter

A 作为非 const 引用传递 - 是否允许修改？具体来说，是否允许对其进行排序？ - ildjarn

@ildjarn没错 - 修改它是可以的。但排序将会是nlogn，而当前代码是O(N)。话虽如此，我还没有用排序进行过性能分析。 - Hector

Answer 1

如果你的值的范围是合理的（即不会因为我即将提出的建议而耗尽内存），你可以使用数组或向量，例如对于范围 [0，max_value]（未经测试但你可以理解）：

// init
vector<int> counts(max_value + 1, 0);

// increment:
counts[value] ++;

或者您可以根据需要动态调整大小：

// init
vector<int> counts;

// increment:
if (value >= counts.size())
    counts.resize(value + 1, 0);
counts[value] ++;

如果范围合理但为负数，您可以添加偏移量使所有值都为非负数，或者保留一个单独的向量用于负数，并使用它们的绝对值。

否则，哈希映射基本上是最好的选择，所以你已经达到了极限 - 你可以继续尝试使用unordered_map，但提供一个不同的哈希函数，为您典型的数据提供更均匀分布的哈希值。

其他想法：

• 并行计数-在多个线程上计算向量的块，然后要么a)在最后合并它们，要么b)使用原子增量计数器进行性能测试（例如，在Windows上使用InterlockedIncrement，但...您仍然需要线程安全的插入新值，因此可能建议选择A）。我无法告诉您哪个更快，您必须进行测试。使用线程池或其他预先创建的线程，因为您可能不想每次都启动和停止线程的全部开销。

• 如果您得到连续的相同值，或者许多短序列，您可以尝试缓存前一个值的映射迭代器。然后，如果您即将查看的值相同，则重用该迭代器，并保存哈希查找。我认为这样做不会有太大的差异，但我不确定，您需要针对特定的数据集进行尝试。

我想不出其他什么了。

- Jason C

---

谢谢。不幸的是，范围高达10亿，所以这并不可行。 - Hector

@user2036256 哦，是的，那有点太多了。你是否涵盖了所有 10 亿个值，还是在该范围内分布相对稀疏？ - Jason C

平均情况下，大约有100,000个条目，在该范围内相当随机。按目前的情况来看，不太可能超过1,000,000个条目。 - Hector

@user2036256 这些值是相当随机的顺序吗（在您的示例中是这样，但只是确认一下），还是您倾向于获得相同值的长时间运行（甚至短时间运行，但很多次）？ - Jason C

值似乎是随机的，且以随机顺序出现。尽管与真正随机序列相比，有更多重复项。 - Hector

Answer 2

在我的系统上（Win10 x64，MSVC daily package x64 发行版），使用std::sort + std::adjacent_find 对包含 100,000 个随机未排序数值的输入向量进行测试，与使用std::unordered_map 和 @krzaq 的答案中的代码（现在也在 OP 中）相比，前者的执行时间约为 10ms，后者的执行时间约为 27ms。请注意保留 HTML 标签。

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;
}

在线演示

教训：通常情况下，缓存一致性胜过算法复杂度。

- ildjarn

---

在实际基准测试中加1。您为什么要使用adjacent_find而不是upper_bound？对我来说，后者似乎是更自然的选择。 - krzaq

@krzaq：upper_bound在剩余所有输入上反复跳动，破坏了最初的缓存一致性，这正是它的本意。尽管如此，在性能上它还是相当接近——这段代码在我的系统上产生了大约13ms的结果，而adjacent_find则是约10ms。编辑：这可能更多地表明了MSVC的不尽人意的unordered_map实现，而不是其他什么。 - ildjarn

谢谢。这似乎可以在典型数据集上减少约20％。可能会尝试使用基数排序来进一步降低它，并修复如果这个规模进一步扩大的话，它的复杂度！ - Hector

@ildjarn Boost的spreadsort基于MSD基数排序，因此可能比经过良好调整的LSD基数排序慢（根据他们自己的承认）。 基数排序肯定不会逊色。 - Veedrac