阅读中文版本

HyperLogLog CLI

A Node CLI that estimates the cardinality of a stream of lines from stdin using a HyperLogLog sketch with a configurable register count.

node --version

printf "a\nb\nc\na\nb" | node hll.mjs 12

node --test hll.test.mjs

Prints the estimated number of distinct lines from stdin, using a HyperLogLog sketch with the given precision (register count = 2^precision).

What it does

Reads lines from stdin, hashes each to a 32-bit integer, and updates a HyperLogLog register array. The register index is the top p bits of the hash, and the register value is the position of the leftmost set bit in the remaining bits. The estimate uses the harmonic mean of the registers with small-range correction.

import { createHash } from 'node:crypto';
const p = +process.argv[2] || 12;
const m = 1 << p;
const reg = new Float64Array(m);
const mask = m - 1;
for await (const line of process.stdin) {
  const h = createHash('sha256').update(line).digest().readUInt32BE(0);
  const idx = h >>> (32 - p);
  const w = (h << p) | (1 << (p - 1));
  const rho = 32 - p - Math.clz32(w) + 1;
  if (rho > reg[idx]) reg[idx] = rho;
}
const alpha = 0.7213 / (1 + 1.079 / m);
let Z = 0;
for (let i = 0; i < m; i++) Z += 2 ** -reg[i];
let E = alpha * m * m * Z;
if (E <= 2.5 * m) { const V = reg.filter(r => r === 0).length; if (V > 0) E = m * Math.log(m / V); }
console.log(Math.round(E));

Run and verify

printf "a\nb\nc\na\nb" | node hll.mjs 12

Run the test command to check the implementation: node --test hll.test.mjs.

Expected Output

For the input a, b, c, a, b there are 3 distinct lines:

3

Limitations

The estimate has a standard error of about 1.04 / sqrt(m), so with the default precision of 12 (4096 registers) the error is about 1.6%. Higher precision reduces error but uses more memory.