加快HyperLogLog算法的实现

Question

我自己实现了HyperLogLog algorithm。它工作得很好，但有时我需要获取大量的HLL结构(大约10k-100 k)，并将它们合并。

我将它们存储为位字符串，所以首先必须将每个位字符串转换为桶。因为有很多HLL's，所以比我想的要花更多的时间。

目前，大约80%的运行时为每个HLL接受这一行调用一次的代码：

my @buckets = map { oct '0b'.$_ } unpack('(a5)1024', $bitstring);

有什么办法能更快地做到吗？

如果我们忽略了HyperLogLog的定义，任务可以这样解释:考虑到$bitstring由1024个5位计数器组成(因此每个计数器的值最多可达32)，我们必须将其转换为由1024个整数组成的数组。

Answer 1

a表示任意的零填充二进制数据.在这里，您将该数据视为ASCII文本，但它只能包含1和0！这是低效的，因为a5最终使用了五个字节。最简单和最有效的解决方案是为每个计数器存储一个8位数字，然后是：my @buckets = unpack 'C1024', $bitstring。

如果您只想每个计数器存储五位，那么您最终只会为非常麻烦的问题节省很少的内存。你得用这种疯狂的东西来进行往返转换：

my $bitstring = pack "(b5)1024", map { sprintf "%b", $_ } @buckets;
@buckets = map { oct "0b$_" } unpack "(b5)1024", $bitstring;