加快我对HyperLogLog算法的实施

Question

我自己实现了HyperLogLog algorithm.它运作良好,但有时我必须获取很多(大约10k-100k)的HLL结构并合并它们.

我将它们中的每一个存储为一个位串,所以首先我必须将每个位串转换为桶.由于有很多HLL,它需要的时间比我想要的多.

目前大约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.

如果你只想在每个计数器上存储5位,那么你最终会节省很少的内存,非常麻烦.你必须使用像这样疯狂的东西来进行往返转换:

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