最有效的方法来计数事件？

我期待在性能关键代码中计算熵和互信息很多次。作为中间步骤，我需要计算每个值的出现次数。例如：最有效的方法来计数事件？

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.

。当然，明显的方式给此要么使用关联数组或通过排序使用“标准”的排序算法等快速排序输入数组做。对于像字节这样的小整数，代码目前专门用于使用普通的旧数组。

是否有任何聪明的算法比散列表或“标准”排序算法提供的效率更高效，例如关联数组实现，该算法非常支持插入更新或排序算法，这些算法在数据存在时发光很多关系？

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

来源

2010-03-05 dsimcha

不能再想起你上面说的。对数组进行排序，然后顺序遍历它。 – 2010-03-05 04:20:49

也许你可以使用某种Hadoop或Map/Reduce来加速你的算法？除此之外，我什么都看不到。 – kgrad 2010-03-05 04:34:10

@kgrad：我已经完全通过并行化外部循环来充分利用所有内核，因此将此函数的单独执行并行化没有意义。 – dsimcha 2010-03-05 04:37:26

请详细说明您的数据。

有多少项？
独特项目与总项目的预期比率是多少？
什么是你的整数的实际值的分布？它们通常小到可以使用简单的计数阵列？还是他们聚集到合理狭窄的群体？等

在任何情况下，我建议以下想法：mergesort修改为计数重复。

也就是说，在以下方面不工作电话号码，但对（数字，频率）（可能用于一些巧妙存储器高效的表示，例如两个阵列，而不是对数组等）。

从[（x1,1），（x2,1），...]开始并照常执行mergesort，但是当合并两个以相同值开始的列表时，将该值放入输出列表和它们的总和。在您的例子：

[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]

这可能是通过使用一些巧妙的技巧，做阵列的初始减少大大改善（获得的数值数组：occurence对，比原来小很多，但总和每个'值'的'发生'等于原始数组中'值'的出现次数）。例如，将数组拆分为连续的块，其中值不超过256或65536，并使用小数组来计算每个块内的出现次数。实际上，这个技巧也可以在稍后的合并阶段应用。

来源

2010-03-05 10:24:41 jkff

对于这个例子中的整数数组，最有效的方法是使用一个数组int s并使用您的值对其进行索引（因为您似乎已经在执行此操作）。

如果你不能这样做，我想不出比hashmap更好的选择。你只需要有一个快速的哈希算法。如果您想使用所有数据，则无法比O（n）性能更好。是否只能使用您拥有的部分数据？

（注意，分类和计数是渐近较慢（O（N *的log（n）））比使用基于散列映射溶液（O（N））。）

来源

2010-03-05 04:24:17

排序渐近较慢，但在高熵情况下（并非每个值出现多次），即使对于非常大的N（以百万计），实际上排序也更快，因为它的缓存效率更高。 – dsimcha 2010-03-05 04:41:52

散列通常是更加可扩展，作为另一答案表示。但是，对于许多可能的分布（以及许多实际情况，其中子阵列恰好经常被排序，取决于整个阵列如何放在一起），timsort通常“非常好”（更接近O（N）而不是O（N log N）） - 我听说它可能会成为Java中的标准/默认排序算法，在一些相当接近的未来数据中（它已经成为Python中多年来的标准排序算法）。

解决此类问题的方法并不是真正的好方法，只能选择一些代表您预期会遇到的实际工作负载的案例进行基准测试（具有明显的风险，您可以选择实际发生的样本有偏见/没有代表性 - 如果你想建立一个图书馆，那么你的控制之外的许多外部用户会使用这个库），这不是一个小的风险。

来源

2010-03-05 04:45:02

我不知道'timsort'，看起来很有趣！ – 2010-03-05 10:12:38

最有效的方法来计数事件？

回答

相关问题