z*******o
发帖数: 4773 | 1 有一个函数
long compute(int i) {
return …;
}
返回值有可能出错概率是 p=1/10000。
还有一个函数
long total(int n) {
long s = 0;
for (int i =0; i < n; i++) {
s += compute(i);
}
return s;
}
这样出错概率就是 np;
问： 如何改第二个函数，让他的出错概率小于p? |
w*****h
发帖数: 423 | 2 为啥第二个出错概率是np? 不make sense
【在 z*******o 的大作中提到】
: 有一个函数
: long compute(int i) {
: return …;
: }
: 返回值有可能出错概率是 p=1/10000。
: 还有一个函数
: long total(int n) {
: long s = 0;
: for (int i =0; i < n; i++) {
: s += compute(i);
|
l******s
发帖数: 3045 | 3 抛个砖
for (int i =0; i < n; i++) {
int tmp1 = 0, tmp2 = 0;
for(int j = 0; j < n; j))
tmp1 += compute(i);
for(int j = 0; j < n; j))
tmp2 += compute(i);
int tmp = (tmp1 + tmp2)/2n;
s += tmp;
} |
l*****z
发帖数: 3022 | 4 取平均没有用吧。搞majority voting就行了
【在 l******s 的大作中提到】
: 抛个砖
: for (int i =0; i < n; i++) {
: int tmp1 = 0, tmp2 = 0;
: for(int j = 0; j < n; j))
: tmp1 += compute(i);
: for(int j = 0; j < n; j))
: tmp2 += compute(i);
: int tmp = (tmp1 + tmp2)/2n;
: s += tmp;
: }
|
l*****z
发帖数: 3022 | 5 应该是1 - pow(1-p, n)
【在 w*****h 的大作中提到】
: 为啥第二个出错概率是np? 不make sense
|
z*******o
发帖数: 4773 | 6 有道理，
根据n，p选择多大百分比vote算通过，Binomial Probability。
都忘了。
【在 l*****z 的大作中提到】
: 取平均没有用吧。搞majority voting就行了
:
:
|
r**********g
发帖数: 22734 | 7 If the error is random, then we can have an almost certainly correct wrapper
over compute(): Create a set, return the first duplicate number
generated by compute. If error is not random then need majority |
i*****h
发帖数: 1534 | 8 学习了，多谢！
【在 l*****z 的大作中提到】
: 应该是1 - pow(1-p, n)
|
b*******w
发帖数: 56 | 9
wrapper
Cool. Could you elaborate on the majority voting? Choosing the value of more
than halve?
【在 r**********g 的大作中提到】
: If the error is random, then we can have an almost certainly correct wrapper
: over compute(): Create a set, return the first duplicate number
: generated by compute. If error is not random then need majority
|
d******e
发帖数: 2265 | 10 算n遍校验，只有数值相等才返回，否则retry。n遍都算错的概率是1/p^n。
这个足够小了。事实上可以从公式推导算几遍就够了。
【在 z*******o 的大作中提到】
: 有一个函数
: long compute(int i) {
: return …;
: }
: 返回值有可能出错概率是 p=1/10000。
: 还有一个函数
: long total(int n) {
: long s = 0;
: for (int i =0; i < n; i++) {
: s += compute(i);
|
|
|
T*****u
发帖数: 7103 | |
w*********a
发帖数: 9279 | 12 当p很小的时候， 你这个就是np
【在 l*****z 的大作中提到】
: 应该是1 - pow(1-p, n)
|
o******u
发帖数: 630 | 13 不对吧。只要错一个就是错。
【在 l*****z 的大作中提到】
: 应该是1 - pow(1-p, n)
|
o******u
发帖数: 630 | 14 抛个砖，n*p^verify_times
p=1/10000. verfify_times最小2，最大4。
偷懒的话，用之前验证4次就可以了。 |
s*******e
发帖数: 1002 | 15 应该是这样
【在 d******e 的大作中提到】
: 算n遍校验，只有数值相等才返回，否则retry。n遍都算错的概率是1/p^n。
: 这个足够小了。事实上可以从公式推导算几遍就够了。
|
n*******s
发帖数: 17267 | 16 都说大数据瞎掰， 这个真可以Map Reduce一把的。
【在 z*******o 的大作中提到】
: 有一个函数
: long compute(int i) {
: return …;
: }
: 返回值有可能出错概率是 p=1/10000。
: 还有一个函数
: long total(int n) {
: long s = 0;
: for (int i =0; i < n; i++) {
: s += compute(i);
|
d****n
发帖数: 397 | 17 算compute（i）的时候多算几次，连续得到相同的K个结果就停止。
这样算错的概率就是p^k
这样total函数算错的概率就是n * p^k
当n * p^(k -1) < 1的时候
这个概率就小于p。
【在 z*******o 的大作中提到】
: 有一个函数
: long compute(int i) {
: return …;
: }
: 返回值有可能出错概率是 p=1/10000。
: 还有一个函数
: long total(int n) {
: long s = 0;
: for (int i =0; i < n; i++) {
: s += compute(i);
|
T*****u
发帖数: 7103 | 18 mapreduce就是蚂蚁战术，怎么会没用。
【在 n*******s 的大作中提到】
: 都说大数据瞎掰， 这个真可以Map Reduce一把的。
|
s********x
发帖数: 81 | 19 这是谁家的地方题目哈？好像我的想法和大家的还不一样。
我认为不需要voting。
long compute(int i) 出错的概率是p，如果我们运行m次，得到m个结果，并且从m个结
果中任意选取一个，出错的概率是q
q = m/m * C_m^m + (m-1)/m * C_m^(m-1) + ... + 0 * C_m^0
m/m * C_m^m ->
C_m^m 是指m次结果全出错的概率，m/m是从这m个结果中，抽出一个数字，且这个数字
出错的概率。
(m-1)/m * C_m^(m-1) ->
C_m^(m-1) 是指m次结果中，m-1个出错的概率，(m-1)/m是从这m个结果中，抽出一个数
字，且这个数字出错的概率。
以此类推
通过这种方式，可以缩小每次运行long compute(int i)出错的概率。
long total(int n)出错的概率是 1 - pow(1-q, n)
1 - pow(1-q, n) > p
通过这个方式算出m |
s********x
发帖数: 81 | 20 请问一下，我上面的思路可行吗？
wrapper
【在 r**********g 的大作中提到】
: If the error is random, then we can have an almost certainly correct wrapper
: over compute(): Create a set, return the first duplicate number
: generated by compute. If error is not random then need majority
|
|
|
d****n
发帖数: 397 | 21 q = m/ m * C(m, m) * p^m + (m - 1) / m * C(m , m -1) * p ^ (m - 1) * (1-p) +
... + (m - k) / m* C(m, m - k) * p^(m - k) * (1-p)^k + ... = C(m-1, m -1) *
p ^ m + ... + C(m - 1, m - k - 1) * p ^(m - k) * p ^k) + ... = p ( p + 1 -
p)^ (m - 1) = p
也就是说你的q = p不论你做多少次，如果用你这个方法。
所以最后还是np。
麻烦下次论证一下先。
【在 s********x 的大作中提到】
: 这是谁家的地方题目哈？好像我的想法和大家的还不一样。
: 我认为不需要voting。
: long compute(int i) 出错的概率是p，如果我们运行m次，得到m个结果，并且从m个结
: 果中任意选取一个，出错的概率是q
: q = m/m * C_m^m + (m-1)/m * C_m^(m-1) + ... + 0 * C_m^0
: m/m * C_m^m ->
: C_m^m 是指m次结果全出错的概率，m/m是从这m个结果中，抽出一个数字，且这个数字
: 出错的概率。
: (m-1)/m * C_m^(m-1) ->
: C_m^(m-1) 是指m次结果中，m-1个出错的概率，(m-1)/m是从这m个结果中，抽出一个数
|
a***u
发帖数: 383 | 22 这个可能需要相当长时间，因为连续得到相同的k个结果是(1-p)^k这个概率可能很小很
小。
【在 d****n 的大作中提到】
: 算compute（i）的时候多算几次，连续得到相同的K个结果就停止。
: 这样算错的概率就是p^k
: 这样total函数算错的概率就是n * p^k
: 当n * p^(k -1) < 1的时候
: 这个概率就小于p。
|
d****n
发帖数: 397 | 23 用时间换概率啊。如果p＝1/10000，如果n＝10000，k取2
就好了，如果n＝10000^2. k取3就好。这个概率还行吧。
【在 a***u 的大作中提到】
: 这个可能需要相当长时间，因为连续得到相同的k个结果是(1-p)^k这个概率可能很小很
: 小。
|
s********x
发帖数: 81 | 24 想一想，你说的是有道理的。
随机做一次，出错的概率是p，
随机做很多次，从中任意选取一次，出错的概率应该还是p，不会有变化。
+
*
-
【在 d****n 的大作中提到】
: q = m/ m * C(m, m) * p^m + (m - 1) / m * C(m , m -1) * p ^ (m - 1) * (1-p) +
: ... + (m - k) / m* C(m, m - k) * p^(m - k) * (1-p)^k + ... = C(m-1, m -1) *
: p ^ m + ... + C(m - 1, m - k - 1) * p ^(m - k) * p ^k) + ... = p ( p + 1 -
: p)^ (m - 1) = p
: 也就是说你的q = p不论你做多少次，如果用你这个方法。
: 所以最后还是np。
: 麻烦下次论证一下先。
|
r**********g
发帖数: 22734 | 25 第一个问题是错误分布是什么？我前面说了如果出错的结果是随机的，也就是犯两次同
样的错的概率很小，用头一次重复的结果即可。
所以这个问题问得很糟糕，重要的不是正确结果的分布而是错误结果的分布。
【在 s********x 的大作中提到】
: 想一想，你说的是有道理的。
: 随机做一次，出错的概率是p，
: 随机做很多次，从中任意选取一次，出错的概率应该还是p，不会有变化。
:
: +
: *
: -
|
l*****z
发帖数: 3022 | 26 就是因为错一个就是错才这样算的，为啥不对？
【在 o******u 的大作中提到】
: 不对吧。只要错一个就是错。
|
w*********l
发帖数: 1337 | 27 绝对不make sense。假设p=0.5，加两个数一定出错？加三个数出错概率大于1了。
出错概率应该是binomial distribution。
C(n, 1) * p * (1-p)^(n-1) + C(n, 2) * p^2 * (1-p)^(n-2) + ... + p^n
【在 w*****h 的大作中提到】
: 为啥第二个出错概率是np? 不make sense
|
l*****z
发帖数: 3022 | 28 太复杂了。
全对的概率好算，1减全对就好了。我上面给了公式
【在 w*********l 的大作中提到】
: 绝对不make sense。假设p=0.5，加两个数一定出错？加三个数出错概率大于1了。
: 出错概率应该是binomial distribution。
: C(n, 1) * p * (1-p)^(n-1) + C(n, 2) * p^2 * (1-p)^(n-2) + ... + p^n
|
z*******o
发帖数: 4773 | |
a******n
发帖数: 11246 | 30 看到大伙讨论那么多概率，我作为数学+统计背景，简单说几句+纠正一些朋友的错误：
1) compute(1), compute(2), 等等是不是正确是随机的没错，但题目里没说他们之间
independent啊~ 所以sum(compute(i))的错误率，是不确定的。。。你们讨论半天sum
的错误率有毛用呀。。。
2) 有人说compute(i)的错误率如果是p，那么sum的错误率不是np（假设各个compute(i
)indenpendent）。correct and wrong。严格来说，不是np。楼上有人给公式了。但当
p非常非常小，np又不太大的情况下，np是一个近似的值（泰勒展开后二次项和更高次
项太小，可以忽略）。说对，是因为不管各个compute(i)之间相互关系如何，sum的错
误率不会超过np（当所有这些错误事件都mutually exclusive的时候）。你知道这样一
个错误率上限就行了。举个例子，假如错误率不会超过万分之一，你经过严格计算，说
错误率是万分之0.97，没啥太大的意义。
3) 面试的题目都有背景。为啥p=1/10000，而不是0.5呢。我觉得这个题目的背景就是
hadoop（p就是每个node出错率，n就是node数量）。为啥hadoop的每个node，default
都是保存3份。为什么不是4份5份。
【在 z*******o 的大作中提到】
: 有一个函数
: long compute(int i) {
: return …;
: }
: 返回值有可能出错概率是 p=1/10000。
: 还有一个函数
: long total(int n) {
: long s = 0;
: for (int i =0; i < n; i++) {
: s += compute(i);
|
|
|
l******8
发帖数: 1691 | 31 如果compute函数跟系统时间相关呢？
【在 l*****z 的大作中提到】
: 取平均没有用吧。搞majority voting就行了
:
:
|
d****n
发帖数: 397 | 32 就你聪明，没看出来p很小，大家都用taylor expansion省略高阶项了?
【在 w*********l 的大作中提到】
: 绝对不make sense。假设p=0.5，加两个数一定出错？加三个数出错概率大于1了。
: 出错概率应该是binomial distribution。
: C(n, 1) * p * (1-p)^(n-1) + C(n, 2) * p^2 * (1-p)^(n-2) + ... + p^n
|
w*********l
发帖数: 1337 | 33 多年不说这么狂的话了，比你这样的人聪明问题还是不大的。
近似也得根据我这个公式近似啊，没公式直接写结果，谁知道你过程对不对。你跟我扯
无穷小，我面试你我觉得fail你。
【在 d****n 的大作中提到】
: 就你聪明，没看出来p很小，大家都用taylor expansion省略高阶项了?
|
c*******e
发帖数: 373 | 34 long compute(int i) 出错的概率是p，如果我们运行m次，得到m个结果，并且从m个结
果中任意选取一个，出错的概率是q
你的动作都是无意义的，完全不影响那个被选中的结果的错误概率
【在 s********x 的大作中提到】
: 这是谁家的地方题目哈？好像我的想法和大家的还不一样。
: 我认为不需要voting。
: long compute(int i) 出错的概率是p，如果我们运行m次，得到m个结果，并且从m个结
: 果中任意选取一个，出错的概率是q
: q = m/m * C_m^m + (m-1)/m * C_m^(m-1) + ... + 0 * C_m^0
: m/m * C_m^m ->
: C_m^m 是指m次结果全出错的概率，m/m是从这m个结果中，抽出一个数字，且这个数字
: 出错的概率。
: (m-1)/m * C_m^(m-1) ->
: C_m^(m-1) 是指m次结果中，m-1个出错的概率，(m-1)/m是从这m个结果中，抽出一个数
|
l*****z
发帖数: 3022 | 35 啥意思？有影响吗？
【在 l******8 的大作中提到】
: 如果compute函数跟系统时间相关呢？
|
