perl - 加速 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;