基数计数

发表于 本文字数： 277 阅读时长 ≈ 1 分钟

HyperLogLog 用于估计候选集概率的数据结构。它使得用较小的空间获得近似的准确度。无论集合包含的多少个元素，HyperLogLog 总是使用非常少的内存。

基本命令

PFADD

对给定的元素进行计数，如果计数成功，返回 true；否则，返回 false。

1
2
3
4
5
6
-- true
PFADD alphabets "a" "b" "c" "d" "e"
-- false
PFADD alphabets "a"
-- true
PFADD alphabets "f"

时间复杂度：O(n)

PFCOUNT

返回 hyper 中元素的近似个数。

hyper 不存在则返回 0.

1
2
3
4
5
6
7
8
9
-- 6
PFCOUNT alphabets
-- 0
PFCOUNT alphabets1

PFADD alphabets1 "a" "b" "c"
PFADD alphabets2  "c" "d" "e" "f"
-- 6 返回 alphabets1 和 alphabets2 并集的个数
PFCOUNT alphabets1 alphabets2

时间复杂度：O(n)

PFMERGE

将指定 hypers 计算出并集，并保存到 target hyper 中。

1
2
3
4
5
6
7
PFADD alphabets1 "a" "b" "c"
PFADD alphabets2  "c" "d" "e" "f"

-- 将 alphabets1 和 alphabets2 求并集，保存到 alphabets::merge 中
PFMERGE alphabets::merge alphabets1 alphabets2
- 6
PFCOUNT alphabets::merge

时间复杂度：O(n)

总结

  • HyperLogLog 是一个基于基数的近似计算；
  • HyperLogLog 无论保存多少个元素，只使用固定内存；
  • PFMERGE 代替 PFCOUNT，因为 PFCOUNT 内部调用 PFMERGE 命令；
  • HyperLogLog 用于计数和去重；