如何在一次通过中近似计算数组中不同值的计数

Question

我有几个巨大的数组(数百万++成员).所有这些都是数字数组,它们没有排序(我不能这样做).有些是uint8_t,有些uint16_t/32/64.我想估计这些数组中不同值的计数.条件如下:

1. 速度非常重要,我需要在一次通过数组时执行此操作,我必须按顺序执行它(不能来回跳转)(我在C++中这样做,如果这很重要)
2. 我不需要精确的计数.我想知道的是,如果它是一个uint32_t数组,如果有10或20个不同的数字,或者有数千或数百万.
3. 我可以使用相当多的内存,但使用的越少越好
4. 数组数据类型越小,我需要越准确
5. 我不介意STL,但如果我能做到没有它那将是伟大的(虽然没有BOOST,对不起)
6. 如果方法可以很容易地并行化,那将很酷(但它不是强制条件)

完美输出的例子:

ArrayA [uint32_t, 3M members]: ~128 distinct values
ArrayB [uint32_t, 9M members]: 100000+ distinct values
ArrayC [uint8_t, 50K members]: 2-5 distinct values
ArrayD [uint8_t, 700K members]: 64+ distinct values

我知道有些限制可能看起来不合逻辑,但就是这样.作为旁注,我也想要最常用的X(3或10)和最少使用的值,但这样做要容易得多,我可以自己做.但是,如果有人也有这样的想法,请随时分享!

编辑:关于STL的一些澄清.如果您有使用它的解决方案,请发布它.不使用STL对我们来说只是一个奖励,我们不太喜欢它.但是,如果它是一个很好的解决方案,它将被使用!

Answer 1

对于8位和16位值,您只需创建每个值的计数表; 每次写入之前为零的表条目时,都会找到不同的值.

对于较大的值,如果您对100000以上的计数不感兴趣std::map,如果它足够快,则是合适的.如果这对你来说太慢了,你可以编写自己的B树.

Answer 2

我很确定你能做到:

1. 创建Bloom过滤器
2. 运行数组将每个元素插入到过滤器中(这是一个"慢"O(n),因为它需要计算每个值的几个独立的正确哈希值)
3. 计算布隆过滤器中设置的位数
4. 从过滤器的密度计算回到不同值的数量的估计.我不知道我头脑中的计算,但对Bloom过滤器理论的任何处理都会涉及到这一点,因为它对于过滤器在查找中产生误报的可能性至关重要.

假设您同时计算前10个最常见的值,那么如果少于10个不同的值,您将确切地知道它们是什么,并且您不需要估计.

我认为"最常用"的问题很难(很好,耗费内存).假设您只需要最常用的前1个值.进一步假设您在阵列中有1000万个条目,并且在第一个990万个之后,到目前为止您看到的数字都没有出现超过100k次.那么你到目前为止看到的任何值都可能是最常用的值,因为它们中的任何一个都可以在最后运行100k值.更糟糕的是,他们中的任何两个最终都会有50k的运行,在这种情况下,前990万条目的计数是它们之间的平局.因此,为了在最常用的单次通过中进行计算,我认为您需要知道出现在990万中的每个值的确切计数.你必须为过去的10万个中两个值之间的近似关系做准备,因为如果发生这种情况,你不能再倒带并再次检查两个相关值.最终你可以开始剔除值 - 如果有一个5​​000的值,只剩下4000个条目要检查,那么你可以剔除任何数量为1000或更少的东西.但这并没有多大帮助.

所以我可能错过了一些东西,但我认为在最坏的情况下,"最常用"的问题要求你为你看到的每个值保持一个计数,直到几乎结束阵列.所以你不妨使用那些计数集来计算出有多少不同的值.