姚佳

摘要：在科學(xué)調(diào)查、質(zhì)量抽檢、福利彩票中需要用到隨機不重復(fù)抽樣算法，即抽中的單位不再放回總體，樣本中的單位只能抽中一次。普通計算機程序在執(zhí)行過程中，為串行計算方式，無法同時產(chǎn)生多個相互孤立的樣本，文章設(shè)計了兩種算法，在一次運行過程中，可產(chǎn)生多個不同樣本值，并使用JAVA語言在不同應(yīng)用環(huán)境下進行仿真測試，呈現(xiàn)算法思路，分析其復(fù)雜性和試用范圍。

關(guān)鍵詞：隨機抽樣；偽隨機數(shù)；狀態(tài)標記；數(shù)組；鏈表；約瑟夫問題

中圖分類號：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

隨機抽樣算法廣泛應(yīng)用于計算機系統(tǒng)、統(tǒng)計和科學(xué)應(yīng)用中，用于那些不需要處理全部數(shù)據(jù)或者從時間和資源的角度考慮過于昂貴的場合[[1]]。

當(dāng)調(diào)查對象數(shù)目巨大時，充分解每一個個體，非常困難。通常會讓一部分樣本來反映整體，由于不同個體存在差異，需要隨機抽取樣本，利用計算機平臺進行隨機抽樣，可以避免各種因素的影響和人為干擾，保證調(diào)查結(jié)果的客觀公正性。因此，隨機抽樣算法在社會調(diào)查和社會研究中應(yīng)用較廣泛[[2]]。

1 串行程序產(chǎn)生多個隨機數(shù)執(zhí)行過程

普通計算機程序為順序執(zhí)行，可利用java語言API 函數(shù)java.util.Random產(chǎn)生單個偽隨機數(shù)，但無法同時產(chǎn)生多個互相獨立的數(shù)值。如圖1所示，為產(chǎn)生三個隨機數(shù)的執(zhí)行過程，每次執(zhí)行相互獨立，因此同一個數(shù)值會重復(fù)出現(xiàn)。在實際應(yīng)用過程中，往往需要保證元素不會被重復(fù)抽取到，即不重復(fù)抽樣，[Random1、Random2、Random3]兩兩不同，實現(xiàn)某次被抽到的元素不會被再次抽取[[3-4]]。

為實現(xiàn)這一目標，通常會采用的設(shè)計思路為狀態(tài)標志，即定義一布爾型數(shù)組，賦值為全真或者全假，與采樣元素一一對應(yīng)，如采樣元素被抽取，則其對應(yīng)的狀態(tài)標志元素發(fā)生改變，標記為已使用，在下次抽樣過程中不會被重復(fù)抽取。另外一種常用的設(shè)計思路為，將已經(jīng)抽取的元素從資源庫中刪除，實現(xiàn)不重復(fù)抽樣。基于這兩種設(shè)計思路，將分別設(shè)計論文抽檢系統(tǒng)與彩票抽獎機，具體展示算法執(zhí)行過程，并進行性能分析。

2 論文抽檢系統(tǒng)設(shè)計

學(xué)位論文作為研究生教育的重要組成部分和研究生教育的總結(jié)性成果，集中反映了研究生的理論基礎(chǔ)、專業(yè)知識、學(xué)術(shù)水平和創(chuàng)新能力。因此論文質(zhì)量綜合反映了研究生教育的水平和質(zhì)量。論文抽檢系統(tǒng)，如圖2所示，即從學(xué)位論文資源庫中隨機調(diào)取一定比例的文獻，進行質(zhì)量評估分析，如是否存在抄襲，論文學(xué)術(shù)水準偏低等情況。利用計算機平臺，可有效降低人為因素的影響和干擾，使抽樣結(jié)果客觀公正[[5]]。

圖2 論文抽檢平臺系統(tǒng)結(jié)構(gòu)

設(shè)計一包含十篇學(xué)位論文的資源庫進行算法模擬，隨機從中抽取三篇。對每篇文獻進行狀態(tài)標記，如果已經(jīng)被抽取則算法重復(fù)執(zhí)行，尋找未被抽取文獻。

False False False False False False False False False False

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

第一次執(zhí)行random=1，文件1被抽取

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

第二次執(zhí)行random=7，文件7被抽取

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

第三次執(zhí)行random=7，文件7已經(jīng)被抽取，算法重復(fù)執(zhí)行

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

第四次執(zhí)行random=1，文件1已經(jīng)被抽取，算法重復(fù)執(zhí)行

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

第五次執(zhí)行random=9，文件9未被抽取，算法結(jié)束，輸出隨機抽取三篇文獻

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

算法的執(zhí)行過程為五次操作，其中第三次和第四次為重復(fù)抽取，算法的平均時間復(fù)雜度為[O（N）]，N為系統(tǒng)資源總數(shù)，在此仿真過程中N為10。該算法在執(zhí)行過程中，雖然進行了重復(fù)操作，但良好保持了數(shù)據(jù)庫中資源的完整性與次序，每次被抽取的文獻僅進行了狀態(tài)標記[[1]]。

3 篩除法隨機抽樣模型

約瑟夫問題（Issue of Joseph），有時也稱為約瑟夫斯置換，是一個出現(xiàn)在計算機科學(xué)和數(shù)學(xué)中的問題。其通常算法模型為建立循環(huán)鏈表，稱約瑟夫環(huán)（structure-Joseph），每間隔特定長度就將結(jié)點元素刪除，直至剩下最后一個結(jié)點。以此為基礎(chǔ)，形成篩除法隨機抽樣模型。

購買彩票已經(jīng)成為人們生活當(dāng)中一種娛樂性投資。10選3彩票系統(tǒng)，即在10個數(shù)字中，隨機產(chǎn)生3個不同數(shù)字，單次中獎概率為[C310]。以此為模型，對篩除法隨機抽樣過程進行仿真。如圖3所示，構(gòu)造一個池，將所有數(shù)字標注于球上，放入池中，每次隨機抽中一個，近似于“約瑟夫問題”，池中球逐次減少，算法執(zhí)行過程中，不需要進行狀態(tài)標記，且不會產(chǎn)生重復(fù)取樣[[6-7]]。

圖3 使用被抽取元素構(gòu)造池

如圖4所示，構(gòu)造鏈表，每個節(jié)點存儲一個不同數(shù)字的字符元素，頭結(jié)點為空[[8][9]]。

圖4 抽樣元素鏈表

如圖5所示，第一次執(zhí)行r.nextInt（11）=3，（0為起始位，產(chǎn)生0-10的偽隨機數(shù)，0位為鏈表頭結(jié)點），抽中字符元素“03”，執(zhí)行鏈表刪除操作，并輸出抽中元素，鏈表長度減少；

圖5 第一次抽樣操作

如圖6所示，因鏈表長度減少，第二次執(zhí)行r.nextInt（10）=6，（0為起始位，產(chǎn)生0-9的偽隨機數(shù)，0位為鏈表頭），抽中字符元素“07”，執(zhí)行鏈表刪除操作，同時輸出抽中元素，鏈表長度繼續(xù)減少；

圖6 第二次抽樣操作

如圖7所示，因鏈表長度繼續(xù)減少，第三次執(zhí)行r.nextInt（9）=4，（0為起始位，產(chǎn)生0-8的偽隨機數(shù)，0位為鏈表頭），抽中字符元素“05”，執(zhí)行鏈表刪除操作，同時輸出抽中元素，程序執(zhí)行結(jié)束。

圖7 第三次抽樣操作

算法共執(zhí)行三次操作，選出“03”、“07”、“05”三個元素。該算法的平均時間復(fù)雜度為[O（M）]，M為抽取樣本數(shù)，在此仿真過程中M為3[[1，10]]。

4 算法特點與性能分析

如圖8所示，為狀態(tài)標記法和篩除法兩種隨機抽樣方式的計算時間復(fù)雜度對照，狀態(tài)標記法的平均時間復(fù)雜性與資源庫元素數(shù)量有關(guān)，與被抽樣元素規(guī)模無關(guān)。篩除法的平均復(fù)雜性與被抽樣元素規(guī)模相關(guān)，與資源庫中樣本數(shù)無關(guān)。

利用篩除法進行隨機抽樣，算法執(zhí)行簡潔，易于理解，方便編程實現(xiàn)，且平均時間復(fù)雜度明顯優(yōu)于狀態(tài)標記法，但是在執(zhí)行過程中，由于資源庫中抽樣元素被提取，資源庫的完整性和數(shù)據(jù)存儲次序被破壞。

5 結(jié)束語

篩除法和狀態(tài)標記法是利用計算機平臺實現(xiàn)不重復(fù)抽樣的有效方式，有廣泛的實際應(yīng)用價值。狀態(tài)標記法抽樣基于數(shù)組操作，能夠在抽樣過程中保持數(shù)據(jù)庫的原始狀態(tài)，適用于文獻抽查、藥品質(zhì)量檢驗、工業(yè)產(chǎn)品質(zhì)量抽檢等多種領(lǐng)域。篩除法抽樣基于鏈表實現(xiàn)，算法結(jié)構(gòu)更緊湊，降低了計算時間復(fù)雜性，該算法執(zhí)行中先建立數(shù)據(jù)資源庫，數(shù)據(jù)提取完成后，資源庫不再被重復(fù)使用，為一次性的操作，可應(yīng)用于投資分析，風(fēng)險評估，通信系統(tǒng)仿真中各種隨機復(fù)雜噪聲環(huán)境的構(gòu)建等。

參考文獻：

[1] 王軍鋒，賈建，申志偉.一種改進的隨機抽樣算法[J].電腦與信息技術(shù)，2006（2）：63.

[2] 楊剛.簡單隨機抽樣中幾個問題的探討[J].許昌學(xué)院學(xué)報，2012（5）：22-23.

[3] 壽涌毅.并行工程項目調(diào)度的組合隨機抽樣算法[J].浙江大學(xué)學(xué)報，2006（2）：345.

[4] 壽涌毅.隨機抽樣算法在多項目調(diào)度中的應(yīng)用[J].管理工程學(xué)報，2005（3）：32.

[5] 賀相春.基于WebService的學(xué)位論文抽檢系統(tǒng)設(shè)計與實現(xiàn)[J].軟件導(dǎo)刊， 2012（11）：46-49.

[6] 羅來鵬，劉二根.基于Apriori算法的彩票預(yù)測[J].決策參考，2007（3）：48-49.

[7] 洪晶，柳炳祥，程功勛.一種基于Apriori算法的彩票數(shù)字組合數(shù)據(jù)挖掘[J].福建電腦，2005（9）：92.

[8] 嚴蔚敏.數(shù)據(jù)結(jié)構(gòu)（C語言版）[M]. 北京：清華大學(xué)出版社，2013

[9] 歐陽桂秀.Java語言程序設(shè)計[M].北京：高等教育出版社，2008

[10] 羅玉軍.隨機抽樣改進算法及其實現(xiàn)[J].電腦與信息技術(shù)，2008（6）：27-28.