performance - 计算出现次数的最有效方法？

Question

我希望在性能关键型代码中多次计算熵和互信息。作为中间步骤，我需要计算每个值出现的次数。例如:

uint[] myArray = [1,1,2,1,4,5,2];
uint[] occurrences = countOccurrences(myArray);
// Occurrences == [3, 2, 1, 1] or some permutation of that.
// 3 occurrences of 1, 2 occurrences of 2, one each of 4 and 5.

当然，最明显的方法是使用关联数组或使用“标准”排序算法(如快速排序)对输入数组进行排序。对于像字节这样的小整数，代码目前专门用于使用普通的旧数组。

有没有比哈希表或“标准”排序算法更有效地执行此操作的智能算法？很多关系？

注意:非稀疏整数只是一种可能的数据类型的一个例子。我希望在这里实现一个合理的通用解决方案，但由于整数和仅包含整数的结构是常见的情况，如果它们非常有效，我会对特定于这些的解决方案感兴趣。

Answer 1

如另一个答案所示，散列通常更具可扩展性。然而，对于许多可能的分布(以及许多现实生活中的情况，子数组恰好经常排序，这取决于整个数组的组合方式)，timsort通常是“非常好的”(更接近 O(N) 而不是 O(N log N))——我听说它可能会在一些相当接近的 future 数据中成为 Java 中的标准/默认排序算法(它一直是标准多年来一直使用 Python 进行排序算法)。

没有真正解决此类问题的好方法，只能以代表您预期会遇到的现实生活工作量的一系列案例为基准(存在明显的风险，即您可能会选择实际恰好是有偏见/不具有代表性——如果您尝试构建一个将由您无法控制的许多外部用户使用的库，那将是一个不小的风险。