本文是對(duì) Swift Algorithm Club 翻譯的一篇文章。
Swift Algorithm Club是 raywenderlich.com網(wǎng)站出品的用Swift實(shí)現(xiàn)算法和數(shù)據(jù)結(jié)構(gòu)的開(kāi)源項(xiàng)目，目前在GitHub上有18000+??，我初略統(tǒng)計(jì)了一下，大概有一百左右個(gè)的算法和數(shù)據(jù)結(jié)構(gòu)，基本上常見(jiàn)的都包含了，是iOSer學(xué)習(xí)算法和數(shù)據(jù)結(jié)構(gòu)不錯(cuò)的資源。
??andyRon/swift-algorithm-club-cn是我對(duì)Swift Algorithm Club，邊學(xué)習(xí)邊翻譯的項(xiàng)目。由于能力有限，如發(fā)現(xiàn)錯(cuò)誤或翻譯不妥，請(qǐng)指正，歡迎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è)非?？斓陌姹荆?/p>
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。所以我們?cè)僖膊粫?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" ]
就是這樣。 十分簡(jiǎn)單。 這個(gè)函數(shù)的性能是O(k)，因?yàn)橹灰覀冞x擇了k元素，就結(jié)束了。
下面是一種替代算法，稱為“水庫(kù)抽樣”(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ù)組。 這被稱為“水庫(kù)”。 - 用剩余池中的元素隨機(jī)替換水庫(kù)中的元素。
該算法的性能為 O(n)，因此它比第一算法慢一點(diǎn)。但是，它的最大優(yōu)點(diǎn)是它可以用于太大而無(wú)法容納在內(nèi)存中的數(shù)組，即使你不知道數(shù)組的大小是多少（在Swift中這可能類似于讀取文件元素的懶惰生成器）。
前兩種算法有一個(gè)缺點(diǎn)：它們不保留原始順序的元素。在輸入數(shù)組中，"a"出現(xiàn)在"e"之前，但現(xiàn)在卻是另一種順序。如果要順序不變，則無(wú)法使用上面的方法。
下面這種替代方法，可以保持原始順序的完整性，但需要更多空間參與：
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
}
該算法使用概率來(lái)決定是否在選擇中包括一個(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而不是更常見(jiàn)的0xffffffff。leftToExamine是我們還沒(méi)有看過(guò)的項(xiàng)數(shù)目。leftToAdd是我們?cè)谕瓿芍斑€需要選擇的項(xiàng)數(shù)。這就是魔術(shù)發(fā)生的地方。 基本上，我們正在翻轉(zhuǎn)一枚硬幣。 如果是heads，我們將當(dāng)前數(shù)組元素添加到選擇中; 如果是tails，我們就跳過(guò)。
有趣的是，即使我們使用概率，這種方法總是保證我們最終得到輸出數(shù)組中的k項(xiàng)。
讓我們?cè)俅斡懻撓嗤睦印?輸入數(shù)組是：
[ "a", "b", "c", "d", "e", "f", "g" ]
循環(huán)依次查看每個(gè)元素，因此我們從"a"開(kāi)始。 我們得到一個(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，我們跳過(guò)"a"并繼續(xù)移動(dòng)動(dòng)"b"。
再一次，我們得到一個(gè)隨機(jī)數(shù)，比方說(shuō)0.212。 現(xiàn)在只剩下6個(gè)要檢查的元素，因此公式結(jié)果是：
6 * 0.212 = 1.272
小于3，我們?cè)谶x擇中添加"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不是，所以我們跳過(guò)"d"。 只剩下三種可能性 - 我們會(huì)在耗盡元素之前選到它嗎？
隨機(jī)數(shù)為0.346。 該公式給出：
3 * 0.346 = 1.038
有點(diǎn)太高了。 我們跳過(guò)"e"。 只有兩名候選項(xiàng)了......
請(qǐng)注意，現(xiàn)在字面上我們正在處理拋硬幣：如果隨機(jī)數(shù)小于0.5，我們選擇"f"，我們就完成了。 如果它大于0.5，我們繼續(xù)最后的元素。 假設(shè)我們得到0.583：
2 * 0.583 = 1.166
我們跳過(guò)"f"并查看最后一個(gè)元素。 無(wú)論我們?cè)谶@里得到什么隨機(jī)數(shù)，它應(yīng)該總是選擇"g"或者我們不會(huì)選擇足夠的元素而算法不起作用！
假設(shè)我們的最終隨機(jī)數(shù)是0.999（記住，它永遠(yuǎn)不會(huì)是1.0或更高）。 實(shí)際上，無(wú)論我們?cè)谶@里選擇什么，公式總是會(huì)給出小于1的值：
1 * 0.999 = 0.999
因此，如果我們還沒(méi)有足夠多的選擇，那么總是會(huì)選擇最后一個(gè)元素。最后的選擇是[ "b", "c", "g" ]。請(qǐng)注意，元素仍處于原始順序，因?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ù)組末尾的元素比一開(kāi)始的元素更有可能被選中？ 不，所有元素同樣可能被選中。 （如果不相信我的話：在playground 看一下快速測(cè)試，在實(shí)踐中證明了這一點(diǎn)。）
以下是如何測(cè)試此算法的示例：
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。
