加速我的HyperLogLog算法实现

Question

加速我的HyperLogLog算法实现

perlpackunpackhyperloglog

3

我自己实现了HyperLogLog算法。它运行良好，但有时我需要获取大量（约10k-100k）的HLL结构并将它们合并。

我将每个结构存储为一个位字符串，因此首先必须将每个位字符串转换为桶。由于有很多HLL，所以它花费的时间比我想象的要长。

目前，代码的80％的运行时间都在这一行中，每个HLL调用一次： my @buckets = map { oct '0b'.$_ } unpack('(a5)1024', $bitstring); 有没有更快的方法？

如果我们抛开HyperLogLog的定义，可以将任务描述为：假设$bitstring由1024个5位计数器组成（因此每个计数器的值最多为32），我们必须将其转换为1024个整数数组。

- skaurus

你能提供一些 $bitstring 的例子吗？另外，运行需要多长时间，什么样的时间是可以接受的？ - michael501

@michael，它是一个字符串，就像“101011…”等一样。它的长度为5120个符号。 - skaurus

只是一个小提示，有一个CPAN模块可以使用：Algorithm::HyperLogLog。 - Miller

@Miller 谢谢，我不知道这个。有趣的是它通过文件进行导出和导入，与Bloom::Faster相同。因为这个原因，我不得不自己制作Bloom过滤器。他们在想什么？为什么不给我一个可以存储在任何地方的字符串？我的Blooms和HLL都使用Redis而不是文件，这非常方便，因为Redis具有位操作和Lua脚本（我知道Redis有内置的HLL，但对我来说太大了）。 - skaurus

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- amon · Accepted Answer

a代表任意的、用0填充的二进制数据。在这里，您将该数据视为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;