随机抽样模型的两种算法设计与仿真

姚佳

摘要：在科学调查、质量抽检、福利彩票中需要用到随机不重复抽样算法，即抽中的单位不再放回总体，样本中的单位只能抽中一次。普通计算机程序在执行过程中，为串行计算方式，无法同时产生多个相互孤立的样本，文章设计了两种算法，在一次运行过程中，可产生多个不同样本值，并使用JAVA语言在不同应用环境下进行仿真测试，呈现算法思路，分析其复杂性和试用范围。

关键词：随机抽样；伪随机数；状态标记；数组；链表；约瑟夫问题

中图分类号：TP391.3 文献标识码：A 文章编号：1009-3044（2014）06-1299-04

Two Algorithms and Simulating of Random Sampling Model

YAO Jia

（Anhui Vocational Technical College of Posts and Telecommunications， Hefei 230000， China）

Abstract： In scientific researching， quality inspection and the welfare lottery need to use random sampling algorithm without replacement， means the sampled unit does not put back the overall， units in the sample can only been sampled one time. The implementation process of general computer program is serial computation， so can not produce more than one isolated samples. This paper designs two algorithms， can produce more than one different samples in one running process ，and does simulation test in different application environments by the JAVA language. Presents the algorithm thought， analyzes its complexity and scope of the application.

Key words： random sampling； pseudo random number； state marking； array； linked list； Issue of Joseph

随机抽样算法广泛应用于计算机系统、统计和科学应用中，用于那些不需要处理全部数据或者从时间和资源的角度考虑过于昂贵的场合[[1]]。

当调查对象数目巨大时，充分解每一个个体，非常困难。通常会让一部分样本来反映整体，由于不同个体存在差异，需要随机抽取样本，利用计算机平台进行随机抽样，可以避免各种因素的影响和人为干扰，保证调查结果的客观公正性。因此，随机抽样算法在社会调查和社会研究中应用较广泛[[2]]。

1 串行程序产生多个随机数执行过程

普通计算机程序为顺序执行，可利用java语言API 函数java.util.Random产生单个伪随机数，但无法同时产生多个互相独立的数值。如图1所示，为产生三个随机数的执行过程，每次执行相互独立，因此同一个数值会重复出现。在实际应用过程中，往往需要保证元素不会被重复抽取到，即不重复抽样，[Random1、Random2、Random3]两两不同，实现某次被抽到的元素不会被再次抽取[[3-4]]。

为实现这一目标，通常会采用的设计思路为状态标志，即定义一布尔型数组，赋值为全真或者全假，与采样元素一一对应，如采样元素被抽取，则其对应的状态标志元素发生改变，标记为已使用，在下次抽样过程中不会被重复抽取。另外一种常用的设计思路为，将已经抽取的元素从资源库中删除，实现不重复抽样。基于这两种设计思路，将分别设计论文抽检系统与彩票抽奖机，具体展示算法执行过程，并进行性能分析。

2 论文抽检系统设计

学位论文作为研究生教育的重要组成部分和研究生教育的总结性成果，集中反映了研究生的理论基础、专业知识、学术水平和创新能力。因此论文质量综合反映了研究生教育的水平和质量。论文抽检系统，如图2所示，即从学位论文资源库中随机调取一定比例的文献，进行质量评估分析，如是否存在抄袭，论文学术水准偏低等情况。利用计算机平台，可有效降低人为因素的影响和干扰，使抽样结果客观公正[[5]]。

图2 论文抽检平台系统结构

设计一包含十篇学位论文的资源库进行算法模拟，随机从中抽取三篇。对每篇文献进行状态标记，如果已经被抽取则算法重复执行，寻找未被抽取文献。

False False False False False False False False False False

"文件1"，"文件2"，"文件3"，"文件4"，"文件5"，"文件6"，"文件7"，"文件8"，"文件9"，"文件10"

第一次执行random=1，文件1被抽取

"文件1"，"文件2"，"文件3"，"文件4"，"文件5"，"文件6"，"文件7"，"文件8"，"文件9"，"文件10"

第二次执行random=7，文件7被抽取

"文件1"，"文件2"，"文件3"，"文件4"，"文件5"，"文件6"，"文件7"，"文件8"，"文件9"，"文件10"

第三次执行random=7，文件7已经被抽取，算法重复执行

"文件1"，"文件2"，"文件3"，"文件4"，"文件5"，"文件6"，"文件7"，"文件8"，"文件9"，"文件10"

第四次执行random=1，文件1已经被抽取，算法重复执行

"文件1"，"文件2"，"文件3"，"文件4"，"文件5"，"文件6"，"文件7"，"文件8"，"文件9"，"文件10"

第五次执行random=9，文件9未被抽取，算法结束，输出随机抽取三篇文献

"文件1"，"文件2"，"文件3"，"文件4"，"文件5"，"文件6"，"文件7"，"文件8"，"文件9"，"文件10"

算法的执行过程为五次操作，其中第三次和第四次为重复抽取，算法的平均时间复杂度为[O（N）]，N为系统资源总数，在此仿真过程中N为10。该算法在执行过程中，虽然进行了重复操作，但良好保持了数据库中资源的完整性与次序，每次被抽取的文献仅进行了状态标记[[1]]。

3 筛除法随机抽样模型

约瑟夫问题（Issue of Joseph），有时也称为约瑟夫斯置换，是一个出现在计算机科学和数学中的问题。其通常算法模型为建立循环链表，称约瑟夫环（structure-Joseph），每间隔特定长度就将结点元素删除，直至剩下最后一个结点。以此为基础，形成筛除法随机抽样模型。

购买彩票已经成为人们生活当中一种娱乐性投资。10选3彩票系统，即在10个数字中，随机产生3个不同数字，单次中奖概率为[C310]。以此为模型，对筛除法随机抽样过程进行仿真。如图3所示，构造一个池，将所有数字标注于球上，放入池中，每次随机抽中一个，近似于“约瑟夫问题”，池中球逐次减少，算法执行过程中，不需要进行状态标记，且不会产生重复取样[[6-7]]。

图3 使用被抽取元素构造池

如图4所示，构造链表，每个节点存储一个不同数字的字符元素，头结点为空[[8][9]]。

图4 抽样元素链表

如图5所示，第一次执行r.nextInt（11）=3，（0为起始位，产生0-10的伪随机数，0位为链表头结点），抽中字符元素“03”，执行链表删除操作，并输出抽中元素，链表长度减少；

图5 第一次抽样操作

如图6所示，因链表长度减少，第二次执行r.nextInt（10）=6，（0为起始位，产生0-9的伪随机数，0位为链表头），抽中字符元素“07”，执行链表删除操作，同时输出抽中元素，链表长度继续减少；

图6 第二次抽样操作

如图7所示，因链表长度继续减少，第三次执行r.nextInt（9）=4，（0为起始位，产生0-8的伪随机数，0位为链表头），抽中字符元素“05”，执行链表删除操作，同时输出抽中元素，程序执行结束。

图7 第三次抽样操作

算法共执行三次操作，选出“03”、“07”、“05”三个元素。该算法的平均时间复杂度为[O（M）]，M为抽取样本数，在此仿真过程中M为3[[1，10]]。

4 算法特点与性能分析

如图8所示，为状态标记法和筛除法两种随机抽样方式的计算时间复杂度对照，状态标记法的平均时间复杂性与资源库元素数量有关，与被抽样元素规模无关。筛除法的平均复杂性与被抽样元素规模相关，与资源库中样本数无关。

利用筛除法进行随机抽样，算法执行简洁，易于理解，方便编程实现，且平均时间复杂度明显优于状态标记法，但是在执行过程中，由于资源库中抽样元素被提取，资源库的完整性和数据存储次序被破坏。

5 结束语

筛除法和状态标记法是利用计算机平台实现不重复抽样的有效方式，有广泛的实际应用价值。状态标记法抽样基于数组操作，能够在抽样过程中保持数据库的原始状态，适用于文献抽查、药品质量检验、工业产品质量抽检等多种领域。筛除法抽样基于链表实现，算法结构更紧凑，降低了计算时间复杂性，该算法执行中先建立数据资源库，数据提取完成后，资源库不再被重复使用，为一次性的操作，可应用于投资分析，风险评估，通信系统仿真中各种随机复杂噪声环境的构建等。

参考文献：

[1] 王军锋，贾建，申志伟.一种改进的随机抽样算法[J].电脑与信息技术，2006（2）：63.

[2] 杨刚.简单随机抽样中几个问题的探讨[J].许昌学院学报，2012（5）：22-23.

[3] 寿涌毅.并行工程项目调度的组合随机抽样算法[J].浙江大学学报，2006（2）：345.

[4] 寿涌毅.随机抽样算法在多项目调度中的应用[J].管理工程学报，2005（3）：32.

[5] 贺相春.基于WebService的学位论文抽检系统设计与实现[J].软件导刊， 2012（11）：46-49.

[6] 罗来鹏，刘二根.基于Apriori算法的彩票预测[J].决策参考，2007（3）：48-49.

[7] 洪晶，柳炳祥，程功勋.一种基于Apriori算法的彩票数字组合数据挖掘[J].福建电脑，2005（9）：92.

[8] 严蔚敏.数据结构（C语言版）[M]. 北京：清华大学出版社，2013

[9] 欧阳桂秀.Java语言程序设计[M].北京：高等教育出版社，2008

[10] 罗玉军.随机抽样改进算法及其实现[J].电脑与信息技术，2008（6）：27-28.