基于唯一標識符的小范圍均衡隨機抽取方法

陳慶榮，陳明哲

（1.西安航空學(xué)院計算機學(xué)院，陜西西安710077；2.西安電子工程研究所陜西西安710100）

隨著信息技術(shù)的快速發(fā)展，計算機技術(shù)在各方面的應(yīng)用日趨廣泛，各類應(yīng)用系統(tǒng)在生產(chǎn)運營中起到了至關(guān)重要的作用，在這些應(yīng)用系統(tǒng)中大量存在需要對候選數(shù)據(jù)進行隨機抽取的操作。這些應(yīng)用系統(tǒng)在進行隨機抽取操作的設(shè)計時大多采用直接使用某種隨機函數(shù)對候選數(shù)據(jù)進行抽取的方法[1]，這種對候選數(shù)據(jù)隨機抽取的解決方法在候選數(shù)據(jù)量較大時基本可以保證抽取數(shù)據(jù)的均衡性，即每個候選數(shù)被抽中的次數(shù)基本相等。但是，當候選數(shù)據(jù)量較小時，使用這種方法進行候選數(shù)據(jù)的隨機抽取會導(dǎo)致數(shù)據(jù)抽取的不均衡，即在候選數(shù)較少時某些候選數(shù)被多次抽中，而其他候選數(shù)沒有被抽中或抽中次數(shù)較少的情況[2]。

本文通過對隨機抽取方法的研究和分析，在進行小范圍候選數(shù)隨機抽取問題中提出了一種基于唯一標識符的小范圍均衡抽取方法并加以實現(xiàn)，從而提高了小范圍候選數(shù)隨機抽取中抽取的均衡性并對此方法均衡性進行了分析測試。

1 基于唯一標識符的小范圍均衡隨機抽取方法

1.1 直接隨機抽取方法

方法的數(shù)理邏輯描述如下：

則f為由H到G的函數(shù)，并記作

f:H→G。

抽取方法說明：有n（n＜100）個候選數(shù)據(jù)的集合H，要隨機抽取其中的m（0＜m＜n）個數(shù)據(jù)生成結(jié)果集G，給集合H中的n個候選數(shù)據(jù)隨機生成唯一標識符nid，從中取出前m個候選數(shù)生成結(jié)果集G。

1.2 基于唯一標識符的小范圍均衡隨機抽取方法

方法的數(shù)理邏輯描述如下：

定義

候選集H={h1，h2，…，hn}，

均衡系數(shù)η（0＜η＜1），

均衡抽取數(shù)s（0＜s＜m），

抽取唯一標識符集W={＜w1，w2，…，ws＞|w1，w2，…，ws∈H}，唯一標識符抽取函數(shù)f1是由有序偶組成的集。f1的定義域 dom（f1）是集

dom（f1）=H；

函數(shù)f1的值域 ran（f1）是集

ran（f1）=W；

則f1為由H到W的函數(shù)，并記作

f1:H→W。

定義

已抽數(shù)據(jù)記錄集Y={＜y1，y2，…，yx|y1，y2，…，yx∈H}，已抽記錄集抽取函數(shù)f2是由有序偶組成的集。f2的定義域dom（f2）是集

dom（f2）=H；

函數(shù)f2的值域 ran（f2）是集

ran（f2）=Y；

則f2為由H到Y(jié)的函數(shù)，并記作

f2:H→Y。

定義

抽取中間集Z={z1，z2，…，zi|z1，z2，…，zi∈H并且z1，z2，…，zi?W}（i=m-s），抽取中間集函數(shù)f3是由有序偶組成的集。f3的定義域dom（f3）是集

dom（f3）=W-Y；

函數(shù)f3的值域 ran（f3）是集

ran（f3）=Z；

則f3為由H到Y(jié)的函數(shù)，并記作

f3:（W-H）→Z

定義

抽取結(jié)果集G={g1，g2，…，gm}，其中m＜n，則有G=W∪Z。

抽取方法說明：有n（n＜100）個候選數(shù)據(jù)的集合H，要隨機抽取其中的m（0＜m＜n）個數(shù)據(jù)生成結(jié)果集G；首先設(shè)置均衡系數(shù)η（0＜η＜1）和均衡抽取數(shù)s（0＜s＜m），給集合H中的n個候選數(shù)據(jù)隨機生成唯一標識符nid，并按此標識符排序，同時從中取出前s個候選數(shù)生成集合W，按照已抽取數(shù)據(jù)記錄集中抽取的數(shù)據(jù)已被抽取次數(shù)倒排序后生成已抽取數(shù)據(jù)記錄集Y，在集合Y中去除集合W中的所有元素并抽取前m-s個候選數(shù)生成抽取中間集合Z，最后抽取的結(jié)果集G為W∪Z。首次進行小范圍隨機抽取時只需設(shè)置均衡系數(shù)η=1，均衡收取數(shù)s=m，給集合H中的n個候選數(shù)據(jù)隨機生成唯一標識符nid，并按此標識符排倒序，同時從中取出前s個候選數(shù)即可生成抽取集合G。

2 方法測試

2.1 測試系統(tǒng)及方法

測試系統(tǒng)基于Java EE企業(yè)級開發(fā)標準設(shè)計和開發(fā)，采用面向?qū)ο蟮某绦蛟O(shè)計分別實現(xiàn)了直接隨機抽取和基于唯一標識符的小范圍均衡抽取。

為了對比在小范圍候選數(shù)中進行隨機抽取的效果，系統(tǒng)可以設(shè)置候選數(shù)個數(shù)、每次抽取候選數(shù)個數(shù)、抽取次數(shù)等信息，可以分別選用直接隨機抽取和基于唯一標識符的均衡抽取兩種抽取方法，后者抽取前系統(tǒng)還需設(shè)置均衡系數(shù)，抽取結(jié)果分別存入數(shù)據(jù)庫，并以圖表的形式統(tǒng)計顯示兩種抽取方法抽取的結(jié)果，從而可以比較直觀的對比兩種抽取方法的均衡性優(yōu)劣。

2.2 方法測試及結(jié)果分析

2.2.1 測試1

系統(tǒng)設(shè)置50個候選數(shù)，每次抽取5個，連續(xù)抽取5次，分別使用直接隨機抽取方法和基于唯一標識符的小范圍均衡抽取方法，將使用兩種方法下被抽取的候選數(shù)進行統(tǒng)計并生成對應(yīng)的統(tǒng)計圖及統(tǒng)計表，分別如圖1、表1、圖2、表2所示。

2.2.2 測試2

系統(tǒng)設(shè)置50個候選數(shù)，每次抽取10個，抽取5次，分別使用直接隨機抽取方法和基于唯一標識符的小范圍均衡抽取方法，將兩種方法下被抽取的候選數(shù)進行統(tǒng)計并生成統(tǒng)計圖及統(tǒng)計表，分別如圖3、表3、圖4、表4所示。

2.2.3 結(jié)果分析

在以上設(shè)置的兩種測試條件下，對相同測試數(shù)據(jù)按照直接隨機抽取的方法和基于唯一標識符的小范圍均衡隨機抽取的方法得到的抽取結(jié)果統(tǒng)計分析可以得到以下結(jié)果。

圖1 直接抽取結(jié)果統(tǒng)計圖

表1 直接抽取結(jié)果統(tǒng)計表

圖2 小范圍均衡隨機抽取結(jié)果統(tǒng)計圖

表2 小范圍均衡隨機抽取結(jié)果統(tǒng)計表

圖3 直接抽取結(jié)果統(tǒng)計圖

表3 直接抽取結(jié)果統(tǒng)計表

圖4 小范圍均衡隨機抽取結(jié)果統(tǒng)計圖

表4 小范圍均衡隨機抽取結(jié)果統(tǒng)計圖

測試1條件下，使用直接隨機抽取的方法，50個候選數(shù)，未被抽中的候選數(shù)占總候選數(shù)的64%，候選數(shù)被抽中的最高頻率為3。被抽中的25個候選數(shù)中，被抽取過1次的占48%，2次的占20%，3次的占4%。而基于唯一標識符的小范圍均衡隨機抽取方法，未被抽中的候選數(shù)占總候選數(shù)的54%，候選數(shù)被抽中的最高頻率為2，被抽中的25個候選數(shù)中，被抽取過1次的占84%，2次的占8%。從數(shù)據(jù)分析可以看出，直接隨機抽取方法未抽中的候選數(shù)和抽取的最高頻率要高于基于唯一標識符的小范圍均衡隨機抽取方法；而基于唯一標識符的小范圍隨機抽取方法下被抽取過1次的候選數(shù)多于直接隨機抽取方法。

測試2條件下，使用直接隨機抽取的方法，50個候選數(shù)，未被抽中的候選數(shù)占總候選數(shù)的28%，候選數(shù)被抽中的最高頻率為3，被抽中的50個候選數(shù)中，被抽取過1次的占50%，2次的占16%，3次的占6%。而基于唯一標識符的小范圍均衡隨機抽取方法，未被抽中的候選數(shù)占總候選數(shù)的2%，候選數(shù)被抽中的最高頻率為2，被抽中的50個候選數(shù)中，被抽取過1次的占96%，2次的占2%。依據(jù)數(shù)據(jù)分析，直接隨機抽取方法未抽中的候選數(shù)及抽取最高頻率均高于基于唯一標識符的小范圍均衡隨機抽取的方法；而基于唯一標識符的小范圍均衡隨機抽取方法下被抽取過1次的候選數(shù)則明顯多于直接隨機抽取方法。

通過對測試1和測試2條件下，按照設(shè)定的抽取范圍和抽取次數(shù)，使用直接隨機抽取的方法抽取結(jié)束后兩種測試情況下的數(shù)據(jù)分析均可看出候選數(shù)被抽中次數(shù)不均衡，且候選數(shù)中未被抽取到的情況較多；而通過對基于唯一標識符的小范圍均衡隨機抽取方法在兩種測試情況下數(shù)據(jù)分析，抽取結(jié)束后候選數(shù)被抽中的次數(shù)較直接隨機抽取均衡性改善很多，候選數(shù)未被抽到的情況大為減少，大部分候選數(shù)均可被抽到。

從實驗數(shù)據(jù)范圍、抽取次數(shù)及抽取結(jié)果的統(tǒng)計分析可以看出，在小范圍候選數(shù)隨機抽取時采用基于唯一標識符的均衡抽取方法得到的抽取結(jié)果的均衡性明顯優(yōu)于直接隨機抽取的方法。同時在測試中，可以依據(jù)候選數(shù)的特點設(shè)置均衡系數(shù)以達到小范圍數(shù)據(jù)隨機抽取的均衡性達到在最優(yōu)。

3 結(jié)束語

小范圍候選數(shù)隨機抽取是很多應(yīng)用系統(tǒng)功能中需要實現(xiàn)的一項功能，直接使用各類隨機數(shù)的方法直接來處理小范圍數(shù)據(jù)的隨機抽取問題，會因候選數(shù)據(jù)量較小導(dǎo)致隨機數(shù)抽取均衡性較差，即就是某些候選數(shù)被抽中的次數(shù)明顯多于其他候選數(shù)，導(dǎo)致隨機抽取失去隨機意義。通過均衡測試系統(tǒng)的驗證可以看出：基于唯一標識符的小范圍均衡隨機抽取方法，利用設(shè)置均衡系數(shù)η及相關(guān)抽取集合依照此方法進行的相應(yīng)變換，使得小范圍候選數(shù)隨機抽取的均衡性有了很大的改善，為小范圍數(shù)據(jù)隨機抽取提供了均衡性能良好的實用方法。