这道G的题怎么做？ - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>JobHunting - 待字闺中

这道G的题怎么做？

这道G的题怎么做？# JobHunting - 待字闺中

z*o2015-06-25 07:06

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*h2015-06-25 07:06

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*s2015-06-25 07:06

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*z2015-06-25 07:06

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*z2015-06-25 07:06

5 楼

应该是1 - pow(1-p, n)

【在 w*****h 的大作中提到】

: 为啥第二个出错概率是np? 不make sense

z*o2015-06-25 07:06

6 楼

有道理，
根据n，p选择多大百分比vote算通过，Binomial Probability。
都忘了。

【在 l*****z 的大作中提到】

: 取平均没有用吧。搞majority voting就行了
:
:

r*g2015-06-25 07:06

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*h2015-06-25 07:06

8 楼

学习了，多谢！

【在 l*****z 的大作中提到】

: 应该是1 - pow(1-p, n)

b*w2015-06-25 07:06

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*e2015-06-25 07:06

10 楼

算n遍校验，只有数值相等才返回，否则retry。n遍都算错的概率是1/p^n。
这个足够小了。事实上可以从公式推导算几遍就够了。

【在 z*******o 的大作中提到】

T*u2015-06-25 07:06

11 楼

时间换准确

w*a2015-06-25 07:06

12 楼

当p很小的时候，你这个就是np

【在 l*****z 的大作中提到】

: 应该是1 - pow(1-p, n)

o*u2015-06-25 07:06

13 楼

不对吧。只要错一个就是错。

【在 l*****z 的大作中提到】

: 应该是1 - pow(1-p, n)

o*u2015-06-25 07:06

14 楼

抛个砖，n*p^verify_times

p=1/10000. verfify_times最小2，最大4。
偷懒的话，用之前验证4次就可以了。

s*e2015-06-25 07:06

15 楼

应该是这样

【在 d******e 的大作中提到】

: 算n遍校验，只有数值相等才返回，否则retry。n遍都算错的概率是1/p^n。
: 这个足够小了。事实上可以从公式推导算几遍就够了。

n*s2015-06-25 07:06

16 楼

都说大数据瞎掰，这个真可以Map Reduce一把的。

【在 z*******o 的大作中提到】

d*n2015-06-25 07:06

17 楼

算compute（i）的时候多算几次，连续得到相同的K个结果就停止。
这样算错的概率就是p^k
这样total函数算错的概率就是n * p^k
当n * p^(k -1) < 1的时候
这个概率就小于p。

【在 z*******o 的大作中提到】

T*u2015-06-25 07:06

18 楼

mapreduce就是蚂蚁战术，怎么会没用。

【在 n*******s 的大作中提到】

: 都说大数据瞎掰，这个真可以Map Reduce一把的。

s*x2015-06-25 07:06

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*x2015-06-25 07:06

20 楼

请问一下，我上面的思路可行吗？

wrapper

【在 r**********g 的大作中提到】

d*n2015-06-25 07:06

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*u2015-06-25 07:06

22 楼

这个可能需要相当长时间，因为连续得到相同的k个结果是(1-p)^k这个概率可能很小很
小。

【在 d****n 的大作中提到】

: 算compute（i）的时候多算几次，连续得到相同的K个结果就停止。
: 这样算错的概率就是p^k
: 这样total函数算错的概率就是n * p^k
: 当n * p^(k -1) < 1的时候
: 这个概率就小于p。

d*n2015-06-25 07:06

23 楼

用时间换概率啊。如果p＝1/10000，如果n＝10000，k取2
就好了，如果n＝10000^2. k取3就好。这个概率还行吧。

【在 a***u 的大作中提到】

: 这个可能需要相当长时间，因为连续得到相同的k个结果是(1-p)^k这个概率可能很小很
: 小。

s*x2015-06-25 07:06

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*g2015-06-25 07:06

25 楼

第一个问题是错误分布是什么？我前面说了如果出错的结果是随机的，也就是犯两次同
样的错的概率很小，用头一次重复的结果即可。
所以这个问题问得很糟糕，重要的不是正确结果的分布而是错误结果的分布。

【在 s********x 的大作中提到】

: 想一想，你说的是有道理的。
: 随机做一次，出错的概率是p，
: 随机做很多次，从中任意选取一次，出错的概率应该还是p，不会有变化。
:
: +
: *
: -

l*z2015-06-25 07:06

26 楼

就是因为错一个就是错才这样算的，为啥不对？

【在 o******u 的大作中提到】

: 不对吧。只要错一个就是错。

w*l2015-06-25 07:06

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*z2015-06-25 07:06

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*o2015-06-25 07:06

29 楼

脑洞大开

a*n2015-06-25 07:06

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 的大作中提到】