是否有 groupBy + count 的启发式算法？

Question

我得到了一个整数列表，我想计算每个整数在列表中出现的次数。

例如：[0,5,0,1,3,3,1,1,1] 给出 (0 -> 2), (1 -> 4), (3 -> 2), (5 -> 1)。我只需要计数，不需要值（目标是得到计数的直方图）。

一种常见的方法是按值分组，然后计算每个集合的基数。在 SQL 中：SELECT count(*) FROM myTable GROUPBY theColumnContainingIntegers.

有更快的方法吗？启发式或概率方法很好，因为我正在计算大型数据集并且为了速度而牺牲精度很好。

类似于 HyperLogLog 算法（用于计算数据集中不同元素的数量）的东西会很棒，但我没有找到类似的东西...

Answer 1

让我们把包含 9 个元素的集合 [0,5,0,1,3,3,1,1,1] 变大，但元素频率相同：

> bigarray = [0,5,0,1,3,3,1,1,1] * 200
 => [0, 5, 0, 1, 3, 3, 1, 1, 1, 0, 5, 0, 1, 3, 3, 1, ...

现在 bigarray 的大小是 1800，所以让我们尝试使用它。

取180个元素的样本（从这个集合中随机抽取180个元素）

现在计算这个随机子集的出现

{5=>19, 3=>45, 1=>76, 0=>40}

归一化：

{5=>1.0, 3=>2.3684210526315788, 1=>4.0, 0=>2.1052631578947367}

当然对于不同的随机子集结果会有所不同：

{5=>21, 3=>38, 1=>86, 0=>35}

归一化

{5=>1.0, 3=>1.8095238095238095, 1=>4.095238095238095, 0=>1.6666666666666667}

当然会有一些错误 - 这是不可避免的，您需要说明什么是可接受的错误

现在用 50% 的 0 和 50% 的 1 对双数组（大小 1000）进行相同的测试

 > bigarray = [0,1] * 500
 => [0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0,  ...

具有 100 个元素的样本：

{0=>50, 1=>50}

归一化

{0=>1.0, 1=>1.0}

第二个样本：

{0=>49, 1=>51}

归一化

{0=>1.0, 1=>1.0408163265306123}

看来我们可以很容易地减少我们的子集，Sampling来了。

特别是 Reservoir Sampling - 如果在您的情况下数据已填充 'live' 或设置太大而无法一次处理所有值，这可能非常有用。

编辑

关于评论：当然，如果您的集合很大，并且某些元素出现在那里非常罕见，那么您可能已经丢失了它，出现次数将等于 0。

然后你可以使用某种平滑函数（检查additive smoothing）。假设每个可能的元素比它实际出现的次数多 1 次。

例如，假设我们设置了：

1000 elements 1
100 elements 2
10 elements 3
1 elements 4

假设我们的子集包含 {1=>100,2=>10,3=>1, 4=>0}

平滑参数 = 0.05 所以我们在每次出现时加 0.05

{1=>100.05,2=>10.05,3=>1.05,4=>0.05}

当然，这是假设您知道集合中甚至可能存在哪些值。

Is there a heuristic algorithm for groupBy + count?