这是一个创建于 1142 天前的主题，其中的信息可能已经有所发展或是发生改变。
有没有概率比较好的朋友，想算一下 bloomfilter 的理论负载。
题目可以抽象为如下:
目前有一数组，长度为四万，内容全是 0 。每次调用一函数，随机选取其中四个值改为 1，不论该数据本来是 1 还是 0 。(单次调用中四个值一定不同，重复调用中则不影响)
调用一万次函数后，期望数组中还剩多少 0，多少 1 ？
同理，还可以引申成以下题型:
期望 0 的数量超过 90%，期望调用多少次函数？
题目可以抽象为如下:
目前有一数组，长度为四万，内容全是 0 。每次调用一函数，随机选取其中四个值改为 1，不论该数据本来是 1 还是 0 。(单次调用中四个值一定不同，重复调用中则不影响)
调用一万次函数后，期望数组中还剩多少 0，多少 1 ？
同理，还可以引申成以下题型:
期望 0 的数量超过 90%，期望调用多少次函数？
 |
1
xkeyideal 2021-03-04 17:38:17 +08:00
理论不会，写个代码跑一下，如果没写错的话，1 的个数在 21900(+-100)
|
|
2
xkeyideal 2021-03-04 17:50:26 +08:00
第二问：不超过 1210 次
|
 |
3
LeeReamond OP @xkeyideal 跑都可以跑，不需要啊(悲)
|
 |
4
xupefei 2021-03-04 18:17:21 +08:00
第一问：
调用一次一个 bit 被选中的概率: 4/40000 调用一次一个 bit 没有被选中的概率: 1-4/40000 一万次调用里一次都没被选中的概率: (1-4/40000)^10000 一万次调用后没被选中过的 bit 数量：(1-4/40000)^10000*40000 = 14714 第二问把 10000 换成 x 自己解方程。 |
|
5
LeeReamond OP @xupefei 大佬再问一题，假设调用一万次后有 14714 个 0，剩下都是 1，第 10001 次调用恰好选取全是 0 而没有 1 的概率是多少
|
Select Language