注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

罗维的博客

{ 关注机器学习、计算广告、自然语言处理、大规模数据处理等 }

 
 
 
 
 

日志

 
 

随机洗牌与蓄水池抽样  

2013-11-09 09:52:37|  分类: 算法设计 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

随机洗牌

问题描述:假设有一个数组,包含n个元素。现在要重新排列这些元素,要求每个元素被放到任何一个位置的概率都相等(即1/n),并且直接在数组上重排(in place),不要生成新的数组。用O(n) 时间、O(1)辅助空间。(Fisher-Yates Shuffle问题

 

Fisher和Yates在1938年提出随机洗牌问题,他们提出的方法的时间复杂度是O(n2)。

一种性能高且正确的算法(Richard Durstenfeld设计)

逆序遍历数组,对第n个元素,以1/n的概率与前n个元素中的某个元素互换位置,最后生成的序列即满足要求,1/n的概率可通过rand() % n实现

 

void Swap(int* arr, int i, int j) {

  if (i != j) {

    int temp = arr[i];

    arr[i] = arr[j];

    arr[j] = temp;

  }

}

 

void Shuffle(int* arr, int len) {

  if (len <= 0) return;

  int i = len;

  while (--i) {

    int idx = rand() % (i + 1);

    Swap(arr, i, idx);

  } // end while

}

 

上面是Richard Durstenfeld所设计的算法的标准实现。i从len – 1一直降到0。其实i从0一直升高到len – 1,也是可以的。

具体来说:顺序遍历数组,对第n个元素,以1/n的概率与前n个元素中的某个元素互换位置,最后生成的序列即满足要求,1/n的概率可通过rand() % n实现:

 

void Shuffle(int *arr, int len)

{

  for(int i = 0; i < n; i++) {

    int idx = rand() % (i + 1);

    swap(arr, i, idx);

  } // end for

}

 

使用数学归纳法证明:

1. 当n=1时,idx必为0,所以元素arr[0]在任何一个位置的概率为1/1,命题成立。

2. 假设当n=k时,命题成立,即n=k时,原数组中任何一个元素在任何一个位置的概率为1/k。则当n=k+1时,当算法执行完k次时,前k个元素在前k个位置的概率均为1/k。当执行最后一步时:

[1] 对前k个元素中任何一个元素,其被替换到第k+1位置的概率为:1/(k+1);维持位置不变的概率为(1-1/(k+1)) * 1/k = 1/(k+1)。故对前k个元素中任何一个元素,其在任意位置的概率都为1/(k+1)。

[2] 对第k+1个元素,其在原位置的概率为1/k+1,在前k个位置任何一个位置的概率为:(1-1/(k+1)) * (1/k)=1/(k+1)。所以对于第k+1个元素,其在整个数组前k+1个位置上的概率也均为1/k+1。

 

综上所述,对于任意n,只要按照方案中的方法,即可满足每个元素在任何一个位置出现的概率均为1/n。

扩展问题:蓄水池抽样

问题描述:给定一个未知长度的整数流(数目大于1000),如何从中随机选取1000个随机数。(蓄水池抽样问题)

 

解决方法:

1. 定义长度为1000的数组,对于数据流中的前1000个数,显然都要放到数组中。

2. 对于数据流中的的第n(n>1000)个数,则这个数被随机选中的概率为 1000/n。故以 1000/n 的概率用这个数去替换数组中的一个。这样就可以保证所有数都以 1000/n的概率被选中。对于后面的数都进行这样的处理,这样就可以保证数组中总是保存着1000个随机数。

 

同样可以用数学归纳法证明。

  评论这张
 
阅读(689)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017