probabilistic 标签归档 | 土法炼钢兴趣小组的算法知识备份

HyperLogLog：用 12KB 统计十亿基数

如何用仅仅 12KB 的内存估计十亿级别的基数？从 Flajolet-Martin 的直觉到 HyperLogLog 的数学证明，概率数据结构的精妙令人叹服。

在无限数据流中统计每个元素的出现频率，精确计数需要无限内存。Count-Min Sketch 用亚线性空间给出有理论保证的近似答案。

监控系统的 P99 延迟是怎么算出来的？t-digest 用巧妙的质心压缩在亚线性空间中给出准确的分位数估计，尤其在尾部保持高精度。

面对一个不知道有多长的数据流，如何保证每个元素被等概率选中？水塘抽样用一个优雅的不变量解决了这个看似不可能的问题。

在数十亿网页中找出近似重复的内容，逐对比较需要天文数字的计算量。MinHash 和 SimHash 用概率方法将复杂度从 O(n^2) 降到近线性。

在无限数据流中找出出现频率最高的元素，只用有限内存能做到多精确？从 Misra-Gries 的消消乐到 Space-Saving 的最优实践。

当数据以每秒百万条的速度涌来，你只能看一遍且内存有限。流式算法用亚线性空间在这个严苛约束下给出令人惊叹的近似答案。