计算事件的最有效方法？

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

请详细说明您的数据。

• 有多少件物品？
• 独特项目与总项目的预期比例是多少？
• 整数的实际值的分布是什么？它们通常足够小以使用简单的计数数组吗？或者他们是否聚集成相当狭窄的群体？ETC。

无论如何，我建议以下想法：修改合并排序以计算重复项。

也就是说，您使用的不是数字而是对（数字、频率）（您可以使用一些巧妙的内存高效表示，例如两个数组而不是对数组等）。

您从 [(x1,1), (x2,1), ...] 开始并像往常一样进行合并排序，但是当您合并以相同值开头的两个列表时，您会将值及其值放入输出列表中发生次数的总和。以你的例子为例：

[1:1,1:1,2:1,1:1,4:1,5:1,2:1]
Split into [1:1, 1:1, 2:1] and [1:1, 4:1, 5:1, 2:1]
Recursively process them; you get [1:2, 2:1] and [1:1, 2:1, 4:1, 5:1]
Merge them: (first / second / output)
[1:2, 2:1] / [1:1, 2:1, 4:1, 5:1] / [] - we add up 1:2 and 1:1 and get 1:3
[2:1] / [2:1, 4:1, 5:1] / [1:3] - we add up 2:1 and 2:1 and get 2:2
[] / [4:1, 5:1] / [1:3, 2:2]
[1:3, 2:2, 4:1, 5:1]

通过使用一些巧妙的技巧来对数组进行初始缩减（获得一个值数组：比原始值小得多的出现对，但每个“值”的“出现”总和等于原始数组中“value”出现的次数）。例如，将数组分割成连续的块，其中值的差异不超过 256 或 65536，并使用一个小数组来计算每个块内的出现次数。实际上这个技巧也可以应用在后期的合并阶段。