一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 925|回复: 11
收起左侧

[算法题] 看到一道随机数生成的算法题

[复制链接] |试试Instant~ |关注本帖
windream1991 发表于 2015-2-27 07:38:27 | 显示全部楼层 |阅读模式

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去instant注册!

x
看到一道随机数生成的算法题,大意是给你一堆频率分布,根据这个分布生成随机数
比如,有三种类型,频率分别为0.2,0.3,0.5,要求根据这些频率分布随机抽取一种类型
不知道怎么弄,发到地里来问问大家?
 楼主| windream1991 发表于 2015-2-27 11:08:45 | 显示全部楼层
宝贝忆彼岸 发表于 2015-2-27 11:04
感觉是不是这个样子的?

public Type choose(){

差不多是这样,但是这个是hardcode的,能不能有个general的方法?
回复 支持 1 反对 0

使用道具 举报

宝贝忆彼岸 发表于 2015-2-27 11:04:20 | 显示全部楼层
感觉是不是这个样子的?

public Type choose(){
Random random = new Random();
int n = random.nextInt(10);
if(n >= 0 && n < 2){
  return type1;
}
else if(n >= 2 && n < 5){
  return type2;
}
else{
  return type3;
}
}
欢迎指正。。。
回复 支持 反对

使用道具 举报

stellari 发表于 2015-2-27 23:48:51 | 显示全部楼层
可以这样。先求出给定分布的“累积分布”,即cumDistribution = [0.2, 0.5, 1]
然后产生一个0~1的随机数p。然后看p落在cumDistribution中的哪个区间当中,那么就抽取该区间对应的类型:
for (i =0; i < cumDistribution.size(); i++)
{
   if (p < cumDistribution[i])
      return i;
}
return一定会被执行到。因为p小于1,而cumDistribution的最后一个数肯定为1。

一般地,如果现在让你产生一组概率分布为q(x)的变量,那么你可以先求出q(x)的累积分布函数Q(x), 再求出Q的反函数Q^-1(x)。然后生成一组0~1之间的均匀随机数k,此时Q^-1(k)就是满足q(x)分布的随机变量。上面的那段代码其实就是这个意思,只是因为是离散情况,所以使用循环去找Q^-1(k)的位置了。如果能知道Q^-1(k)的表达式的话,是可以直接计算的。
回复 支持 反对

使用道具 举报

 楼主| windream1991 发表于 2015-2-28 00:38:14 | 显示全部楼层
stellari 发表于 2015-2-27 23:48
可以这样。先求出给定分布的“累积分布”,即cumDistribution = [0.2, 0.5, 1]
然后产生一个0~1的随机数p ...

那就是说对于这种离散的情况最好的时间复杂度就是o(n)了吗?这样的话不放回抽取k个球最好的时间复杂度似乎就是o(nk)了。。。。
不知道还有没有更好的时间复杂度?
回复 支持 反对

使用道具 举报

stellari 发表于 2015-2-28 09:31:13 | 显示全部楼层
windream1991 发表于 2015-2-28 00:38
那就是说对于这种离散的情况最好的时间复杂度就是o(n)了吗?这样的话不放回抽取k个球最好的时间复杂度似 ...

cumDistribution是单调递增的,所以你可以用Binary Search,这样复杂度是O(logn)。面试的话,我觉得做到这一步就可以了。如果你真的想深入了解的话,你可以去看看一个叫Alias Method的方法。这种方法需要预处理概率分布函数,建立查找表,产生过程则是O(1)的:

http://en.wikipedia.org/wiki/Alias_method

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

stellari 发表于 2015-2-28 09:32:25 | 显示全部楼层
本帖最后由 stellari 于 2015-2-28 12:49 编辑
windream1991 发表于 2015-2-28 00:38
那就是说对于这种离散的情况最好的时间复杂度就是o(n)了吗?这样的话不放回抽取k个球最好的时间复杂度似 ...


另外,下面这个wiki页面应该会有帮助:

http://en.wikipedia.org/wiki/Pse ... crete_distributions
回复 支持 反对

使用道具 举报

 楼主| windream1991 发表于 2015-3-2 01:28:57 | 显示全部楼层
stellari 发表于 2015-2-28 09:31
cumDistribution是单调递增的,所以你可以用Binary Search,这样复杂度是O(logn)。面试的话,我觉得做到 ...

你这两个链接非常有用,不过我后来又想了一下,如果做不放回抽取的话涉及到一个问题就是每次抽取完都要更新cumDistribution,更新的时间是o(n),所以不管是用binary search还是alias method最后的时间复杂度都是o(nk)
回复 支持 反对

使用道具 举报

stellari 发表于 2015-3-2 11:00:47 | 显示全部楼层
windream1991 发表于 2015-3-2 01:28
你这两个链接非常有用,不过我后来又想了一下,如果做不放回抽取的话涉及到一个问题就是每次抽取完都要更 ...

那么你究竟需要的是“产生满足概率分布为{0.5, 0.3, 0.2}的一组样本”,还是“模拟一个从n个总体(其中三种样本的个数分别为0.5n, 0.3n和 0.2n)中抽取一组样本的抽样过程”呢?” 事实上,进行后者的目的就是得到前者,因为在进行简单不放回随机抽样前,一般是不知道{0.5, 0.3, 0.2}这个概率分布的。我们就是为了估计出这个概率分布才不得不抽样。但是,既然现在你已经知道了这个概率分布,那么就有其他的方法产生出一组满足这个分布的随机事件(比如上面的那些算法),不必非得去模拟当初那个随机抽样的过程。而且简单不放回抽样的样本比例是总体比例(即0.5, 0.3和0.2)的无偏估计,所以这两者得到的结果从数学期望的角度来说是一样的。
回复 支持 反对

使用道具 举报

 楼主| windream1991 发表于 2015-3-2 14:08:36 | 显示全部楼层
stellari 发表于 2015-3-2 11:00
那么你究竟需要的是“产生满足概率分布为{0.5, 0.3, 0.2}的一组样本”,还是“模拟一个从n个总体(其中三 ...

就输出而言,这两者似乎没什么差别。我觉得原题的意思就是,输入为一组频率分布以及要抽取的个数k,输出一种可能的抽取结果,应该是更倾向于根据给定的频率分布模拟这个随机抽取k个数的过程吧
回复 支持 反对

使用道具 举报

stellari 发表于 2015-3-2 14:49:29 | 显示全部楼层
windream1991 发表于 2015-3-2 14:08
就输出而言,这两者似乎没什么差别。我觉得原题的意思就是,输入为一组频率分布以及要抽取的个数k,输出 ...

就你的描述来看,应该不是。原题的意思应当是让你“产生一组分布满足{0.5, 0.3, 0.2}的随机变量”。换句话说,无论用什么手段,只要达到这个目的即可。“模拟不放回随机抽样的过程”只是达到这个效果的一种方法而已。日常生活中常常使用不放回抽样,因为在日常生活中这样做便于实现。但是对于我们这个算法来说,反而是“放回抽样”实现起来简单。所以,为什么不模拟“放回抽样”呢?

除非是另外一种题,就比如说reservior sampling问题。确实给定了你一个数组,让你从其中随机抽出一个指定长度的subset。这种情况下,“放回”和“不放回”的区别才变得非常关键。在我们这个问题中,“放回”和“不放回”最后会产生同等的效果,只是后者更麻烦而已。

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

 楼主| windream1991 发表于 2015-3-3 00:16:16 | 显示全部楼层
stellari 发表于 2015-3-2 14:49
就你的描述来看,应该不是。原题的意思应当是让你“产生一组分布满足{0.5, 0.3, 0.2}的随机变量”。换句 ...

有道理,放回确实要比不放回简单
回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-5 13:12

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表