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

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

目前,大约 80% 的运行时需要为每个 HLL 调用一次这行代码:
my @buckets = map { oct '0b'.$_ } unpack('(a5)1024', $bitstring);
有没有办法更快地做到这一点?

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

最佳答案

a 表示任意的、零填充的二进制数据。在这里,您将该数据视为 ASCII 文本,但它只能包含 10 !这是低效的,因为 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;

关于perl - 加速我的 HyperLogLog 算法的实现,我们在Stack Overflow上找到一个类似的问题:https://stackoverflow.com/questions/23686647/

10-14 11:02