查看原文

这个网站简单地介绍了 Hyperloglog 这个算法。该算法适用于非精确估计 count(distinct) 这种场景，它的优点是只用几KB内存就能处理上G的数据，而不像常规的 len(set(e for e in data)) 这样耗内存或者上 map-reduce 那样架构复杂。

• 算法
  • 添加一条记录：获得 hash(row), 将 hash 剩余的0计数，归纳进 hash 头几位标记的 bucket 中。
  • 计数：找出 bucket 中最大的数，应用上纠正算法（例如 LinearCount，即可得到估计的数值，在示例的数据集上做实验，偏离率在 2% 左右。
• Redis 实现了 pfcount 算法，即是 hyperloglog 的应用。
• Hyperloglog++ 做了一些算法上的升级使内存消耗更低，小数据集上的错误率更小。

简而言之：这个算法快猛糙，快速做估计时很有用。