固定内存
为什么重要 “统计每样东西出现的次数”就是一个字典,直到东西的数量没有上限、而内存却有上限为止。一个带有保证范围的近似计数,常常比一个你负担不起的精确计数有价值得多。
一个 API 网关会标记重度用户。它能看到每一个请求,用户的数量可以是任意多,而每个网关进程只为这项工作分到一块固定的内存。这个标记只是提示人去看一看,所以少量的多算没关系;少算则可能藏起一个重度用户,所以不行。
概要结构:一个数据流的固定大小的摘要,它能近似地回答问题,并带有已知的误差范围。比如,一个 count-min sketch 会保存几行计数器,并把每一项哈希到每行中的一个计数器上;这些计数器中最小的那个永远不会低于真实的计数。
import zlib
row_index = zlib.crc32(f"{row}:{item}".encode()) % width # same on every run编写 class ApproxCounter,带有 add(item)(项是字符串)和 estimate(item)(一个整数)。
限制。在来自最多 10,000 个不同用户的 30,000 个事件之后,计数器最多只能保存 3,500 项(对计数器调用 kept())。估计值永远不能低于真实的计数,而且对于至少 95% 的用户(包括从未出现过的用户),估计值最多是真实计数加上 300(事件数的 1%)。结果必须在每次运行、每台设备上都可重复:不要使用 hash()(它每次运行都会变)或随机数;使用固定种子的 zlib.crc32 或 hashlib 是可以的。
这个练习即将开放
完成它前面的那一课,这一课就会解锁。整门课程免费,无需账号,而且你现在就可以阅读这节课。
这个浏览器屏蔽了 learn.floati.life 的 Cookie,所以你在这里完成的课程无法按顺序打开。请允许这个网站使用 Cookie,然后重新加载。