知识卡片

普通读书笔记卡 · 3092.d

近似算法用误差换资源

理解等级:未标注

窗口内精确统计不同邻居数,可保存所有不同取值,但高势集合会占用大量空间。书中以 HyperLogLog 估计去重个数,用可量化误差换更小的寄存器;Redis 示例给出 12KB 和约 0.81% 标准误差。是否采用近似值取决于业务能否接受误差,也要计算分组数乘以每组寄存器大小的总状态成本。

这张卡片看不懂?

已有反馈 · 0 / 10 条

    还没有人提交反馈。

    原书出处

    参考来源

    - 位置:《实时流计算系统设计与实现》第4章4.4.1《一度关联》(源文件:_epub-src/OEBPS/Text/chapter64.xhtml) - 结论依据:原文比较集合精确去重的空间代价与 HyperLogLog 的估计误差、寄存器大小,还提醒高势分组需要大量寄存器。 - 原始内容:以Redis中的HyperLogLog算法实现为例,只需要用12KB的内存,就能够在0.81%的标准误差范围内,记录将近2 64 个不同值的个数。