在c++中获得数组中数字频率的最快方法是什么?

Question

我的方法创建了一个std::map<int,>并通过迭代数组一次来填充它的数字和频率，但我想知道是否有一种不使用map的更快的方法。

Answer 1

std::unordered_map<int,int>也可以计数频率，但其operator[]具有复杂性(cppreference):

平均情况:常量，最坏情况:线性。

相比

容器大小的对数。

带std::map。

当最大数目很小时，您可以使用数组，并直接计数:

for (const auto& number : array) counter[number]++;

不可否认，所有这些都已经在评论中说过了，所以我还要加上这一点:你需要衡量。复杂度只与渐近运行时间有关，而对于给定的输入大小，std::map实际上可以更快。

Answer 2

注意:ValueType, DifferenceType被定义为

template <std::input_iterator I>
using ValueType = typename std::iterator_traits<I>::value_type;
template <std::input_iterator I>
using
DifferenceType = typename std::iterator_traits<I>::difference_type;

如果数组为sorted，则可以使用std::equal_range查找与x相等的元素范围。对于概念，你可以这样写:

// I2 is homomorphic to std::pair<I, unsigned>
// [first, last) is partially ordered with respect to I::value_type
// return value is d_first + |{x | x in [first, last)}|
// R is a relation over I, compare element using R
template <std::random_access_iterator I, std::forward_iterator I2,
std::relation<bool, ValueType<I>> R = std::less<ValueType<I>>>
requires(std::regular<ValueType<I>> &&
std::is_constructible_v<ValueType<I2>, I, DifferenceType<I>>)
I2 frequency_sorted(I first, I last, I2 d_first, R r = R())
{
while(first != last)
{
auto [left, right] = std::equal_range(first, last, *first, r);
*d_first = {left, std::distance(left, right)};
++d_first;
first = right;
}
return d_first;
}

如果您的资源有限，您可以截断结果，并有:

// I2 is homomorphic to std::pair<I, unsigned>
// [first, last) is partially ordered with respect to I::value_type
// return value is a pair, where the first element is 
// the starting point of subsequence [first, last) where such
// subsequence is unevaluated
// the second element is 
// - d_last if |{x | x in [first, last)}| >= d_last - d_first
// - d_first + |{x | x in [first, last)}| if otherwise
template <std::random_access_iterator I, std::forward_iterator I2,
std::relation<bool, ValueType<I>> R = std::less<ValueType<I>>>
requires(std::regular<ValueType<I>> &&
std::is_constructible_v<ValueType<I2>, I, DifferenceType<I>>)
std::pair<I, I2>
frequency_sorted_truncate(I first, I last, I2 d_first, I2 d_last, R r = R())
{
while(first != last && d_first != d_last)
{
auto [left, right] = std::equal_range(first, last, *first, r);
*d_first = {left, std::distance(left, right)};
++d_first;
first = right;
}
return {first, d_first};
}

这两个函数允许传入任何关系，默认比较使用operator<。

如果你的数组是未排序的，并且数组的大小足够大，那么对数组进行排序并使用算法可能是一个好主意。哈希可能很诱人，但它会造成缓存丢失，并且可能没有您期望的那么快。你可以尝试两种方法，并衡量哪一种更快，欢迎你告诉我结果。

我的编译器版本是g++ 11.2.11，我认为代码可以用C++ 20编译器编译。如果你没有一个，简单地用typename替换概念部分，我认为这样做你只需要一个C++ 17编译器(由于结构绑定)。

请告诉我我的代码是否可以改进。