知识卡片
近似算法用误差换资源
窗口内精确统计不同邻居数,可保存所有不同取值,但高势集合会占用大量空间。书中以 HyperLogLog 估计去重个数,用可量化误差换更小的寄存器;Redis 示例给出 12KB 和约 0.81% 标准误差。是否采用近似值取决于业务能否接受误差,也要计算分组数乘以每组寄存器大小的总状态成本。
这张卡片看不懂?
这张卡片的反馈已满 10 条,暂时无法继续提交。
已有反馈 · 0 / 10 条
还没有人提交反馈。
原书出处
参考来源
- 位置:《实时流计算系统设计与实现》第4章4.4.1《一度关联》(源文件:_epub-src/OEBPS/Text/chapter64.xhtml)
- 结论依据:原文比较集合精确去重的空间代价与 HyperLogLog 的估计误差、寄存器大小,还提醒高势分组需要大量寄存器。
- 原始内容:以Redis中的HyperLogLog算法实现为例,只需要用12KB的内存,就能够在0.81%的标准误差范围内,记录将近2 64 个不同值的个数。