j*****n
发帖数: 1545 | 1 １个ａｒｒａｙ里面每个数对应１个ｗｅｉｇｈｔ,比如［１,２,３］的 ｗｅｉｇｈ
ｔ 分别是［１０,２０,３０］, 叫你从［１,２,３］里面按照ｗｅｉｇｈｔ产生１
个随机数， 比如这里面，产生３的概率是产生１的概率的３倍。
简单的做法就是把这些ｗｅｉｇｈｔ加起来，从［１０,２０,３０］变成［１０，３０
，６０］，然后产生１个从［０，６０］的uniform随机数，看这个数是在哪个区间，
［０，１０］，［１０,３０］还是［３０,６０］ 就知道应该返回１，２，３中间哪
个了。
问题是有没有做法可以不需要执行这个ｓｕｍ的过程，因为如果ａｒｒａｙ很大很大，
这种ｓｕｍ很可能就ｏｖｅｒｆｌｏｗ了。 |
h****e
发帖数: 928 | 2 用double存sum不行吗？
【在 j*****n 的大作中提到】
: １个ａｒｒａｙ里面每个数对应１个ｗｅｉｇｈｔ,比如［１,２,３］的 ｗｅｉｇｈ
: ｔ 分别是［１０,２０,３０］, 叫你从［１,２,３］里面按照ｗｅｉｇｈｔ产生１
: 个随机数， 比如这里面，产生３的概率是产生１的概率的３倍。
: 简单的做法就是把这些ｗｅｉｇｈｔ加起来，从［１０,２０,３０］变成［１０，３０
: ，６０］，然后产生１个从［０，６０］的uniform随机数，看这个数是在哪个区间，
: ［０，１０］，［１０,３０］还是［３０,６０］ 就知道应该返回１，２，３中间哪
: 个了。
: 问题是有没有做法可以不需要执行这个ｓｕｍ的过程，因为如果ａｒｒａｙ很大很大，
: 这种ｓｕｍ很可能就ｏｖｅｒｆｌｏｗ了。
|
l*****a
发帖数: 14598 | 3 也overflow呢？
【在 h****e 的大作中提到】
: 用double存sum不行吗？
|
h****e
发帖数: 928 | 4 那就用BigNum之类的。
【在 l*****a 的大作中提到】
: 也overflow呢？
|
k***g
发帖数: 58 | 5 把数都放到int array，size of sum，O(1)即可，也不用search了
★ Sent from iPhone App: iReader Mitbbs 7.56 - iPad Lite |
X*K
发帖数: 87 | 6 是个办法，不过sum都溢出了，这array得有多大。 |
j*****n
发帖数: 1545 | 7 就是一些海量数据的玩意， 我现在是把每个数都先scale down 一下，再加，会好一些
。 搜了一下 也没有什么好办法，都还是得加一加 |
g***s
发帖数: 3811 | 8 max_v = 0;
for i = 1 to n{
if (weight[i] > max_v) {
sum = sum * (max_v / weight[i]) ;
max_v = weight[i];
}
sum += weigh[i] / max_v;
if ( random(1) <= ( (weight[i]/max_v) / (sum) )
r = a[i];
}
return r;
max_v is alway the max value of weigh [0..i]
sum <= i
【在 j*****n 的大作中提到】
: １个ａｒｒａｙ里面每个数对应１个ｗｅｉｇｈｔ,比如［１,２,３］的 ｗｅｉｇｈ
: ｔ 分别是［１０,２０,３０］, 叫你从［１,２,３］里面按照ｗｅｉｇｈｔ产生１
: 个随机数， 比如这里面，产生３的概率是产生１的概率的３倍。
: 简单的做法就是把这些ｗｅｉｇｈｔ加起来，从［１０,２０,３０］变成［１０，３０
: ，６０］，然后产生１个从［０，６０］的uniform随机数，看这个数是在哪个区间，
: ［０，１０］，［１０,３０］还是［３０,６０］ 就知道应该返回１，２，３中间哪
: 个了。
: 问题是有没有做法可以不需要执行这个ｓｕｍ的过程，因为如果ａｒｒａｙ很大很大，
: 这种ｓｕｍ很可能就ｏｖｅｒｆｌｏｗ了。
|
j*****n
发帖数: 1545 | |
l******n
发帖数: 9344 | 10 divided by sum to turn to [0,1] and then generate a [0,1] uniform
【在 j*****n 的大作中提到】
: １个ａｒｒａｙ里面每个数对应１个ｗｅｉｇｈｔ,比如［１,２,３］的 ｗｅｉｇｈ
: ｔ 分别是［１０,２０,３０］, 叫你从［１,２,３］里面按照ｗｅｉｇｈｔ产生１
: 个随机数， 比如这里面，产生３的概率是产生１的概率的３倍。
: 简单的做法就是把这些ｗｅｉｇｈｔ加起来，从［１０,２０,３０］变成［１０，３０
: ，６０］，然后产生１个从［０，６０］的uniform随机数，看这个数是在哪个区间，
: ［０，１０］，［１０,３０］还是［３０,６０］ 就知道应该返回１，２，３中间哪
: 个了。
: 问题是有没有做法可以不需要执行这个ｓｕｍ的过程，因为如果ａｒｒａｙ很大很大，
: 这种ｓｕｍ很可能就ｏｖｅｒｆｌｏｗ了。
|
|
|
m*********e
发帖数: 13 | 11 如果数组大到让sum溢出，那么scale down也会underflow。
我想可以用Metropolis–Hastings，也就是选random pick一个数x1，再random pick一
个数x2,如果weight of x2大于weight of x1，改变状态到x1，否则以一定概率到x2。
After burning in like 10000 iterations, 后面产生的就是要的sample.
这不像是面试SDE的问题，楼主面的是什么职位可以告知么？ |
j*****n
发帖数: 1545 | 12 M-H should work, but getting a good proposal distributon is not easy.
proving detailed balance is hard.
Just a bonus question for machine learning data scientist position.
【在 m*********e 的大作中提到】
: 如果数组大到让sum溢出，那么scale down也会underflow。
: 我想可以用Metropolis–Hastings，也就是选random pick一个数x1，再random pick一
: 个数x2,如果weight of x2大于weight of x1，改变状态到x1，否则以一定概率到x2。
: After burning in like 10000 iterations, 后面产生的就是要的sample.
: 这不像是面试SDE的问题，楼主面的是什么职位可以告知么？
|
g***s
发帖数: 3811 | 13 就是一道稍微改编的 weighted reservoir sampling algorithm.
始终记录到目前数字weight的最大值。然后用它scale。不能用sum进行scale。
【在 m*********e 的大作中提到】
: 如果数组大到让sum溢出，那么scale down也会underflow。
: 我想可以用Metropolis–Hastings，也就是选random pick一个数x1，再random pick一
: 个数x2,如果weight of x2大于weight of x1，改变状态到x1，否则以一定概率到x2。
: After burning in like 10000 iterations, 后面产生的就是要的sample.
: 这不像是面试SDE的问题，楼主面的是什么职位可以告知么？
|
j*****n
发帖数: 1545 | 14 I agree, it is the best answer so far, in my mind.
【在 g***s 的大作中提到】
: 就是一道稍微改编的 weighted reservoir sampling algorithm.
: 始终记录到目前数字weight的最大值。然后用它scale。不能用sum进行scale。
|
m*********e
发帖数: 13 | 15 jet你是什么背景的？ 我也想找data scientist之类的职位，但是这种职位似乎不愿给
没有经验的fresh grad。可是找不到工作我又哪来的经验，在死循环中痛苦中。 |
Z*****Z
发帖数: 723 | 16
~~~~rrdw：这里是不是应该是<=?
【在 g***s 的大作中提到】
: max_v = 0;
: for i = 1 to n{
: if (weight[i] > max_v) {
: sum = sum * (max_v / weight[i]) ;
: max_v = weight[i];
: }
: sum += weigh[i] / max_v;
: if ( random(1) <= ( (weight[i]/max_v) / (sum) )
: r = a[i];
: }
|
g***s
发帖数: 3811 | 17 yes. typo.
【在 Z*****Z 的大作中提到】
:
: ~~~~rrdw：这里是不是应该是<=?
:
|
j*****n
发帖数: 1545 | 18 １个ａｒｒａｙ里面每个数对应１个ｗｅｉｇｈｔ,比如［１,２,３］的 ｗｅｉｇｈ
ｔ 分别是［１０,２０,３０］, 叫你从［１,２,３］里面按照ｗｅｉｇｈｔ产生１
个随机数， 比如这里面，产生３的概率是产生１的概率的３倍。
简单的做法就是把这些ｗｅｉｇｈｔ加起来，从［１０,２０,３０］变成［１０，３０
，６０］，然后产生１个从［０，６０］的uniform随机数，看这个数是在哪个区间，
［０，１０］，［１０,３０］还是［３０,６０］ 就知道应该返回１，２，３中间哪
个了。
问题是有没有做法可以不需要执行这个ｓｕｍ的过程，因为如果ａｒｒａｙ很大很大，
这种ｓｕｍ很可能就ｏｖｅｒｆｌｏｗ了。 |
h****e
发帖数: 928 | 19 用double存sum不行吗？
【在 j*****n 的大作中提到】
: １个ａｒｒａｙ里面每个数对应１个ｗｅｉｇｈｔ,比如［１,２,３］的 ｗｅｉｇｈ
: ｔ 分别是［１０,２０,３０］, 叫你从［１,２,３］里面按照ｗｅｉｇｈｔ产生１
: 个随机数， 比如这里面，产生３的概率是产生１的概率的３倍。
: 简单的做法就是把这些ｗｅｉｇｈｔ加起来，从［１０,２０,３０］变成［１０，３０
: ，６０］，然后产生１个从［０，６０］的uniform随机数，看这个数是在哪个区间，
: ［０，１０］，［１０,３０］还是［３０,６０］ 就知道应该返回１，２，３中间哪
: 个了。
: 问题是有没有做法可以不需要执行这个ｓｕｍ的过程，因为如果ａｒｒａｙ很大很大，
: 这种ｓｕｍ很可能就ｏｖｅｒｆｌｏｗ了。
|
l*****a
发帖数: 14598 | 20 也overflow呢？
【在 h****e 的大作中提到】
: 用double存sum不行吗？
|
|
|
h****e
发帖数: 928 | 21 那就用BigNum之类的。
【在 l*****a 的大作中提到】
: 也overflow呢？
|
k***g
发帖数: 58 | 22 把数都放到int array，size of sum，O(1)即可，也不用search了
★ Sent from iPhone App: iReader Mitbbs 7.56 - iPad Lite |
X*K
发帖数: 87 | 23 是个办法，不过sum都溢出了，这array得有多大。 |
j*****n
发帖数: 1545 | 24 就是一些海量数据的玩意， 我现在是把每个数都先scale down 一下，再加，会好一些
。 搜了一下 也没有什么好办法，都还是得加一加 |
g***s
发帖数: 3811 | 25 max_v = 0;
for i = 1 to n{
if (weight[i] > max_v) {
sum = sum * (max_v / weight[i]) ;
max_v = weight[i];
}
sum += weigh[i] / max_v;
if ( random(1) <= ( (weight[i]/max_v) / (sum) )
r = a[i];
}
return r;
max_v is alway the max value of weigh [0..i]
sum <= i
【在 j*****n 的大作中提到】
: １个ａｒｒａｙ里面每个数对应１个ｗｅｉｇｈｔ,比如［１,２,３］的 ｗｅｉｇｈ
: ｔ 分别是［１０,２０,３０］, 叫你从［１,２,３］里面按照ｗｅｉｇｈｔ产生１
: 个随机数， 比如这里面，产生３的概率是产生１的概率的３倍。
: 简单的做法就是把这些ｗｅｉｇｈｔ加起来，从［１０,２０,３０］变成［１０，３０
: ，６０］，然后产生１个从［０，６０］的uniform随机数，看这个数是在哪个区间，
: ［０，１０］，［１０,３０］还是［３０,６０］ 就知道应该返回１，２，３中间哪
: 个了。
: 问题是有没有做法可以不需要执行这个ｓｕｍ的过程，因为如果ａｒｒａｙ很大很大，
: 这种ｓｕｍ很可能就ｏｖｅｒｆｌｏｗ了。
|
j*****n
发帖数: 1545 | |
l******n
发帖数: 9344 | 27 divided by sum to turn to [0,1] and then generate a [0,1] uniform
【在 j*****n 的大作中提到】
: １个ａｒｒａｙ里面每个数对应１个ｗｅｉｇｈｔ,比如［１,２,３］的 ｗｅｉｇｈ
: ｔ 分别是［１０,２０,３０］, 叫你从［１,２,３］里面按照ｗｅｉｇｈｔ产生１
: 个随机数， 比如这里面，产生３的概率是产生１的概率的３倍。
: 简单的做法就是把这些ｗｅｉｇｈｔ加起来，从［１０,２０,３０］变成［１０，３０
: ，６０］，然后产生１个从［０，６０］的uniform随机数，看这个数是在哪个区间，
: ［０，１０］，［１０,３０］还是［３０,６０］ 就知道应该返回１，２，３中间哪
: 个了。
: 问题是有没有做法可以不需要执行这个ｓｕｍ的过程，因为如果ａｒｒａｙ很大很大，
: 这种ｓｕｍ很可能就ｏｖｅｒｆｌｏｗ了。
|
m*********e
发帖数: 13 | 28 如果数组大到让sum溢出，那么scale down也会underflow。
我想可以用Metropolis–Hastings，也就是选random pick一个数x1，再random pick一
个数x2,如果weight of x2大于weight of x1，改变状态到x1，否则以一定概率到x2。
After burning in like 10000 iterations, 后面产生的就是要的sample.
这不像是面试SDE的问题，楼主面的是什么职位可以告知么？ |
j*****n
发帖数: 1545 | 29 M-H should work, but getting a good proposal distributon is not easy.
proving detailed balance is hard.
Just a bonus question for machine learning data scientist position.
【在 m*********e 的大作中提到】
: 如果数组大到让sum溢出，那么scale down也会underflow。
: 我想可以用Metropolis–Hastings，也就是选random pick一个数x1，再random pick一
: 个数x2,如果weight of x2大于weight of x1，改变状态到x1，否则以一定概率到x2。
: After burning in like 10000 iterations, 后面产生的就是要的sample.
: 这不像是面试SDE的问题，楼主面的是什么职位可以告知么？
|
g***s
发帖数: 3811 | 30 就是一道稍微改编的 weighted reservoir sampling algorithm.
始终记录到目前数字weight的最大值。然后用它scale。不能用sum进行scale。
【在 m*********e 的大作中提到】
: 如果数组大到让sum溢出，那么scale down也会underflow。
: 我想可以用Metropolis–Hastings，也就是选random pick一个数x1，再random pick一
: 个数x2,如果weight of x2大于weight of x1，改变状态到x1，否则以一定概率到x2。
: After burning in like 10000 iterations, 后面产生的就是要的sample.
: 这不像是面试SDE的问题，楼主面的是什么职位可以告知么？
|
|
|
j*****n
发帖数: 1545 | 31 I agree, it is the best answer so far, in my mind.
【在 g***s 的大作中提到】
: 就是一道稍微改编的 weighted reservoir sampling algorithm.
: 始终记录到目前数字weight的最大值。然后用它scale。不能用sum进行scale。
|
m*********e
发帖数: 13 | 32 jet你是什么背景的？ 我也想找data scientist之类的职位，但是这种职位似乎不愿给
没有经验的fresh grad。可是找不到工作我又哪来的经验，在死循环中痛苦中。 |
Z*****Z
发帖数: 723 | 33
~~~~rrdw：这里是不是应该是<=?
【在 g***s 的大作中提到】
: max_v = 0;
: for i = 1 to n{
: if (weight[i] > max_v) {
: sum = sum * (max_v / weight[i]) ;
: max_v = weight[i];
: }
: sum += weigh[i] / max_v;
: if ( random(1) <= ( (weight[i]/max_v) / (sum) )
: r = a[i];
: }
|
g***s
发帖数: 3811 | 34 yes. typo.
【在 Z*****Z 的大作中提到】
:
: ~~~~rrdw：这里是不是应该是<=?
:
|
b********r
发帖数: 620 | 35 the idea is great, but just picking bone from egg, why sum<=1? do i miss
anything?
【在 g***s 的大作中提到】
: max_v = 0;
: for i = 1 to n{
: if (weight[i] > max_v) {
: sum = sum * (max_v / weight[i]) ;
: max_v = weight[i];
: }
: sum += weigh[i] / max_v;
: if ( random(1) <= ( (weight[i]/max_v) / (sum) )
: r = a[i];
: }
|
