HyperLogLog 알고리즘 구현 속도 향상

Question

HyperLogLog algorithm을 직접 구현했습니다. 그것은 잘 작동하지만 때로는 많은 (약 10k-100k)의 HLL 구조체를 가져 와서 병합해야합니다.

나는 각각을 비트 문자열로 저장하므로 먼저 각 비트 문자열을 버킷으로 변환해야합니다. 많은 HLL이 있기 때문에 내가 원하는 것보다 더 많은 시간이 걸립니다.

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

빨리 그것을 할 수있는 방법이 있나요 :

현재 런타임의 약 80 %는 각 HLL에 대해 한 번씩 호출 코드 줄을한다?

우리가 HyperLogLog의 정의를 남겨두면 작업은 다음과 같이 설명 할 수 있습니다. $bitstring은 1024 개의 5 비트 카운터로 구성되어 있으므로 각 카운터의 값은 최대 32 개가 될 수 있으므로 1024 개의 정수 배열로 변환해야합니다. .

Answer 1

a은 임의의 제로 패딩 이진 데이터를 나타냅니다. 여기서 해당 데이터를 ASCII 텍스트로 취급하지만 1 및 0 만 포함 할 수 있습니다! a5이 5 바이트를 사용하여 끝나는 것은 비효율적입니다. 가장 쉽고 효율적인 솔루션은 각 카운터에 대해 8 비트 숫자를 저장하는 것입니다. my @buckets = unpack 'C1024', $bitstring.

카운터 당 5 비트 만 저장하려는 경우 매우 적은 메모리만으로 많은 번거 로움을 피할 수 있습니다. 왕복 전환에는 다음과 같은 미친 짓을 사용해야합니다.

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