本文是對 Swift Algorithm Club 翻譯的一篇文章惧浴。
Swift Algorithm Club是 raywenderlich.com網(wǎng)站出品的用Swift實(shí)現(xiàn)算法和數(shù)據(jù)結(jié)構(gòu)的開源項(xiàng)目，目前在GitHub上有18000+??佛南，我初略統(tǒng)計(jì)了一下餐屎，大概有一百左右個(gè)的算法和數(shù)據(jù)結(jié)構(gòu)费变，基本上常見的都包含了煤禽，是iOSer學(xué)習(xí)算法和數(shù)據(jù)結(jié)構(gòu)不錯(cuò)的資源墨坚。
??andyRon/swift-algorithm-club-cn是我對Swift Algorithm Club键兜，邊學(xué)習(xí)邊翻譯的項(xiàng)目凤类。由于能力有限，如發(fā)現(xiàn)錯(cuò)誤或翻譯不妥普气，請指正谜疤，歡迎pull request。也歡迎有興趣棋电、有時(shí)間的小伙伴一起參與翻譯和學(xué)習(xí)??茎截。當(dāng)然也歡迎加??，??????????赶盔。
本文的翻譯原文和代碼可以查看??swift-algorithm-club-cn/Selection Sampling
選取樣本（Selection Sampling）
目標(biāo)：從n個(gè)項(xiàng)的集合中隨機(jī)選擇k個(gè)項(xiàng)企锌。
假設(shè)你有一副52張牌，你需要隨機(jī)抽取10張牌于未。 這個(gè)算法可以讓你達(dá)成撕攒。
這是一個(gè)非扯妇椋快的版本：
func select<T>(from a: [T], count k: Int) -> [T] {
var a = a
for i in 0..<k {
let r = random(min: i, max: a.count - 1)
if i != r {
swap(&a[i], &a[r])
}
}
return Array(a[0..<k])
}
正如洗牌算法經(jīng)常發(fā)生的那樣，它將數(shù)組劃分為兩個(gè)區(qū)域抖坪。 第一個(gè)區(qū)域包含所選項(xiàng); 第二個(gè)區(qū)域是所有剩余的項(xiàng)萍鲸。
一個(gè)例子。 假設(shè)一個(gè)數(shù)組是：
[ "a", "b", "c", "d", "e", "f", "g" ]
我們想選擇3個(gè)項(xiàng)目擦俐，所以k = 3脊阴。 在循環(huán)中，i最初為0蚯瞧，因此它指向"a"嘿期。
[ "a", "b", "c", "d", "e", "f", "g" ]
i
我們計(jì)算i和數(shù)組的大小a.count之間的隨機(jī)數(shù)。 假設(shè)這個(gè)隨機(jī)數(shù)是4埋合。 現(xiàn)在我們將"a"與索引為4的"e"交換备徐，然后向前移動(dòng)i：
[ "e" | "b", "c", "d", "a", "f", "g" ]
i
|欄表示兩個(gè)區(qū)域之間的分割。 "e"是我們選擇的第一個(gè)元素甚颂。 我們繼續(xù)需要關(guān)注|欄右側(cè)的所有內(nèi)容蜜猾。
再一次，我們要求i和a.count之間的隨機(jī)數(shù)振诬，但因?yàn)?code>i已經(jīng)移位蹭睡，隨機(jī)數(shù)永遠(yuǎn)不會(huì)小于1。所以我們再也不會(huì)交換"e"了赶么。
假設(shè)隨機(jī)數(shù)為6棠笑，我們將"b"與"g"交換：
[ "e" , "g" | "c", "d", "a", "f", "b" ]
i
還有一個(gè)隨機(jī)數(shù)，假設(shè)它是4禽绪。 我們將"c"與"a"交換，最終左邊已經(jīng)選擇的項(xiàng)為：
[ "e", "g", "a" | "d", "c", "f", "b" ]
就是這樣洪规。 十分簡單印屁。 這個(gè)函數(shù)的性能是O(k)，因?yàn)橹灰覀冞x擇了k元素斩例，就結(jié)束了雄人。
下面是一種替代算法，稱為“水庫抽樣”(Reservoir Sampling)：
func reservoirSample<T>(from a: [T], count k: Int) -> [T] {
precondition(a.count >= k)
var result = [T]() // 1
for i in 0..<k {
result.append(a[i])
}
for i in k..<a.count { // 2
let j = random(min: 0, max: i)
if j < k {
result[j] = a[i]
}
}
return result
}
有兩個(gè)步驟：
- 使用原始數(shù)組中的第一個(gè)
k元素填充result數(shù)組念赶。 這被稱為“水庫”础钠。 - 用剩余池中的元素隨機(jī)替換水庫中的元素。
該算法的性能為 O(n)叉谜，因此它比第一算法慢一點(diǎn)旗吁。但是，它的最大優(yōu)點(diǎn)是它可以用于太大而無法容納在內(nèi)存中的數(shù)組停局，即使你不知道數(shù)組的大小是多少（在Swift中這可能類似于讀取文件元素的懶惰生成器）很钓。
前兩種算法有一個(gè)缺點(diǎn)：它們不保留原始順序的元素香府。在輸入數(shù)組中，"a"出現(xiàn)在"e"之前码倦，但現(xiàn)在卻是另一種順序企孩。如果要順序不變，則無法使用上面的方法袁稽。
下面這種替代方法勿璃，可以保持原始順序的完整性，但需要更多空間參與：
func select<T>(from a: [T], count requested: Int) -> [T] {
var examined = 0
var selected = 0
var b = [T]()
while selected < requested { // 1
let r = Double(arc4random()) / 0x100000000 // 2
let leftToExamine = a.count - examined // 3
let leftToAdd = requested - selected
if Double(leftToExamine) * r < Double(leftToAdd) { // 4
selected += 1
b.append(a[examined])
}
examined += 1
}
return b
}
該算法使用概率來決定是否在選擇中包括一個(gè)數(shù)字推汽。
循環(huán)從頭到尾逐步完成數(shù)組补疑。 它一直持續(xù)到我們從n的集合中選擇k個(gè)項(xiàng)。 這里民泵，k是
requested而n是a.count癣丧。計(jì)算0到1之間的隨機(jī)數(shù)。我們想要
0.0 <= r < 1.0栈妆。 上限是排他性的; 我們從不希望它是1胁编。這就是為什么我們將結(jié)果從arc4random()除以0x100000000而不是更常見的0xffffffff。leftToExamine是我們還沒有看過的項(xiàng)數(shù)目鳞尔。leftToAdd是我們在完成之前還需要選擇的項(xiàng)數(shù)嬉橙。這就是魔術(shù)發(fā)生的地方。 基本上寥假，我們正在翻轉(zhuǎn)一枚硬幣市框。 如果是heads，我們將當(dāng)前數(shù)組元素添加到選擇中; 如果是tails糕韧，我們就跳過枫振。
有趣的是，即使我們使用概率萤彩，這種方法總是保證我們最終得到輸出數(shù)組中的k項(xiàng)粪滤。
讓我們再次討論相同的例子。 輸入數(shù)組是：
[ "a", "b", "c", "d", "e", "f", "g" ]
循環(huán)依次查看每個(gè)元素雀扶，因此我們從"a"開始杖小。 我們得到一個(gè)介于0和1之間的隨機(jī)數(shù)，假設(shè)它是0.841愚墓。 // 4處的公式將要檢查的項(xiàng)目數(shù)乘以此隨機(jī)數(shù)予权。 還有7個(gè)元素需要檢查，結(jié)果是：
7 * 0.841 = 5.887
我們將此與3進(jìn)行比較浪册，因?yàn)槲覀兿胍x擇3個(gè)項(xiàng)目扫腺。 由于5.887大于3，我們跳過"a"并繼續(xù)移動(dòng)動(dòng)"b"议经。
再一次斧账，我們得到一個(gè)隨機(jī)數(shù)谴返，比方說0.212。 現(xiàn)在只剩下6個(gè)要檢查的元素咧织，因此公式結(jié)果是：
6 * 0.212 = 1.272
小于3嗓袱，我們在選擇中添加"b"。 這是我們選擇的第一個(gè)項(xiàng)习绢，所以還剩下兩個(gè)渠抹。
到下一個(gè)元素，"c"闪萄。 隨機(jī)數(shù)為0.264梧却，得出結(jié)果：
5 * 0.264 = 1.32
只要再選擇2個(gè)項(xiàng)，因此這個(gè)數(shù)字必須小于2败去。它是放航，我們還在選擇中加入"c"。 總選擇是["b"圆裕，"c"]广鳍。
只要再選擇1個(gè)項(xiàng)，但仍有4個(gè)候選項(xiàng)要查看吓妆。 假設(shè)下一個(gè)隨機(jī)數(shù)是0.718赊时。 該公式現(xiàn)在給出：
4 * 0.718 = 2.872
要選擇此元素，數(shù)字必須小于1行拢，因?yàn)橹皇Ｏ?個(gè)項(xiàng)要選擇祖秒。 2.872不是，所以我們跳過"d"舟奠。 只剩下三種可能性 - 我們會(huì)在耗盡元素之前選到它嗎竭缝？
隨機(jī)數(shù)為0.346。 該公式給出：
3 * 0.346 = 1.038
有點(diǎn)太高了沼瘫。 我們跳過"e"歌馍。 只有兩名候選項(xiàng)了......
請注意，現(xiàn)在字面上我們正在處理拋硬幣：如果隨機(jī)數(shù)小于0.5晕鹊，我們選擇"f"，我們就完成了暴浦。 如果它大于0.5溅话，我們繼續(xù)最后的元素。 假設(shè)我們得到0.583：
2 * 0.583 = 1.166
我們跳過"f"并查看最后一個(gè)元素歌焦。 無論我們在這里得到什么隨機(jī)數(shù)飞几，它應(yīng)該總是選擇"g"或者我們不會(huì)選擇足夠的元素而算法不起作用！
假設(shè)我們的最終隨機(jī)數(shù)是0.999（記住独撇，它永遠(yuǎn)不會(huì)是1.0或更高）屑墨。 實(shí)際上躁锁，無論我們在這里選擇什么，公式總是會(huì)給出小于1的值：
1 * 0.999 = 0.999
因此卵史，如果我們還沒有足夠多的選擇战转，那么總是會(huì)選擇最后一個(gè)元素。最后的選擇是[ "b", "c", "g" ]以躯。請注意槐秧，元素仍處于原始順序，因?yàn)槲覀兪菑淖蟮接也樵償?shù)組忧设。
也許你還不相信......如果我們總是將0.999作為隨機(jī)值（最大可能值）刁标，那還能選擇3項(xiàng)嗎？ 好吧址晕，讓我們做數(shù)學(xué)：
7 * 0.999 = 6.993 小于3嗎? no
6 * 0.999 = 5.994 小于3嗎? no
5 * 0.999 = 4.995 小于3嗎? no
4 * 0.999 = 3.996 小于3嗎? no
3 * 0.999 = 2.997 小于3嗎? YES
2 * 0.999 = 1.998 小于2嗎? YES
1 * 0.999 = 0.999 小于1嗎? YES
它總是有效膀懈！ 但這是否意味著靠近數(shù)組末尾的元素比一開始的元素更有可能被選中？ 不谨垃，所有元素同樣可能被選中启搂。 （如果不相信我的話：在playground 看一下快速測試，在實(shí)踐中證明了這一點(diǎn)乘客。）
以下是如何測試此算法的示例：
let input = [
"there", "once", "was", "a", "man", "from", "nantucket",
"who", "kept", "all", "of", "his", "cash", "in", "a", "bucket",
"his", "daughter", "named", "nan",
"ran", "off", "with", "a", "man",
"and", "as", "for", "the", "bucket", "nan", "took", "it",
]
let output = select(from: input, count: 10)
print(output)
print(output.count)
第二種算法的性能是O(n)狐血，因?yàn)樗赡苄枰闅v整個(gè)輸入數(shù)組。
注意： 如果
k > n / 2易核，那么以相反的方式執(zhí)行它并選擇要?jiǎng)h除的a.count - k項(xiàng)更有效匈织。
代碼基于發(fā)表于1993年10月Dobb博士的雜志的Algorithm Alley。
