代码之家 › 专栏 › 技术社区 › dsimcha

最有效的计数方法是什么?

statistics data-structures language-agnostic algorithm performance

dsimcha · 技术社区 · 15 年前

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

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.

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

有没有比哈希表或“标准”排序算法更有效的智能算法来实现这一点,比如一个关联数组实现,它非常支持更新而不是插入,或者一个排序算法,当您的数据有很多关联时,它会发光?

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

3 回复 | 直到 15 年前

jkff 15 年前

请详细说明您的数据。

有多少件物品?
唯一项目与总项目的预期比率是多少?
整数的实际值的分布是什么?它们通常小到可以使用一个简单的计数数组吗?或者它们是聚在一个相当狭窄的群体里?等。

无论如何,我建议以下想法:修改mergesort以计数重复项。

也就是说,你的工作方式不是数字而是成对的(数字,频率)(你可以使用一些聪明的内存高效的表示方式,例如两个数组而不是成对的数组等)。

您可以从[(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]

通过使用一些聪明的技巧对数组进行初始缩减(获得一个值数组:比原始数组小得多的出现对,但每个“值”的“出现”之和等于原始数组中“值”的出现次数),这可能会得到很大的改进。例如,将数组拆分为连续块,其中的值相差不超过256或65536,并使用一个小数组计算每个块中的出现次数。实际上,这个技巧也可以在以后的合并阶段应用。

Alex Martelli 15 年前

另一个答案表明,哈希通常更具可伸缩性。然而,对于许多可能的分布(以及许多现实生活中的情况,其中子数组恰好经常被排序,这取决于整个数组是如何组合的)。 timsort 通常是“超自然好”(接近O(n)而不是O(n log n))——我听说它可能会成为Java中的标准/默认排序算法,在一些相当合理的未来数据中(这是Python多年来的标准排序算法)。

没有真正好的方法来解决这样的问题,除了在一些案例上做基准测试,这些案例代表了您希望体验的实际工作负载(有一个明显的风险,您可能会选择一个实际碰巧有偏见/不具代表性的样本--这不是如果您试图构建一个库,它将被许多超出您控制范围的外部用户使用,则风险很小)。

David Johnstone 15 年前

对于一个如示例中所示的整数数组,最有效的方法是 int 并使用您的值对其进行索引(就像您已经在做的那样)。

如果你做不到,我想不出比hashmap更好的选择了。你只需要一个快速的散列算法。如果你想使用你所有的数据,你不可能得到比o(n)更好的性能。是否可以只使用部分数据?

(注意,排序和计数比使用基于hashmap的解决方案(o(n))慢得多(o(n*log(n))。)