# andyRon/swift-algorithm-club-cn

Latest commit 21e5827 Sep 2, 2019
Type Name Latest commit message Commit time
..
Failed to load latest commit information.
SelectionSampling.playground Sep 2, 2019

# 选取样本（Selection Sampling）

```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])
}```

``````[ "a", "b", "c", "d", "e", "f", "g" ]
``````

``````[ "a", "b", "c", "d", "e", "f", "g" ]
i
``````

``````[ "e" | "b", "c", "d", "a", "f", "g" ]
i
``````

`|`栏表示两个区域之间的分割。 `"e"`是我们选择的第一个元素。 我们继续需要关注`|`栏右侧的所有内容。

``````[ "e" , "g" | "c", "d", "a", "f", "b" ]
i
``````

``````[ "e", "g", "a" | "d", "c", "f", "b" ]
``````

```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
}```

1. 使用原始数组中的第一个`k`元素填充`result`数组。 这被称为“水库”。
2. 用剩余池中的元素随机替换水库中的元素。

```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
}```

1. 循环从头到尾逐步完成数组。 它一直持续到我们从n的集合中选择k个项。 这里，k`requested`n`a.count`

2. 计算0到1之间的随机数。我们想要`0.0 <= r < 1.0`。 上限是排他性的; 我们从不希望它是1。这就是为什么我们将结果从`arc4random()`除以`0x100000000`而不是更常见的`0xffffffff`

3. `leftToExamine`是我们还没有看过的项数目。 `leftToAdd`是我们在完成之前还需要选择的项数。

``````[ "a", "b", "c", "d", "e", "f", "g" ]
``````

``````7 * 0.841 = 5.887
``````

``````6 * 0.212 = 1.272
``````

``````5 * 0.264 = 1.32
``````

``````4 * 0.718 = 2.872
``````

``````3 * 0.346 = 1.038
``````

``````2 * 0.583 = 1.166
``````

``````1 * 0.999 = 0.999
``````

``````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
``````

```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)```

You can’t perform that action at this time.