목표: n개의 아이템 컬렉션에서 k개의 아이템을 무작위로 선택한다.
예를 들어, 52장의 카드 덱에서 10장의 카드를 무작위로 뽑아야 한다고 가정하자. 이 알고리즘은 이를 가능하게 한다.
아주 빠른 버전은 다음과 같다:
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 {
a.swapAt(i, r) // README에서 수정된 라인
}
}
return Array(a[0..<k])
}이러한 알고리즘에서 자주 발생하는 것처럼, 배열을 두 영역으로 나눈다. 첫 번째 영역은 선택된 아이템을 포함하고, 두 번째 영역은 나머지 아이템을 포함한다.
예제를 살펴보자. 배열이 다음과 같다고 하자:
[ "a", "b", "c", "d", "e", "f", "g" ]
3개의 아이템을 선택하려고 하므로 k = 3이다. 루프에서 i는 초기에 0이므로 "a"를 가리킨다.
[ "a", "b", "c", "d", "e", "f", "g" ]
i
i와 배열의 크기인 a.count 사이의 난수를 계산한다. 이 값이 4라고 가정하자. 이제 "a"와 인덱스 4에 있는 "e"를 교환하고 i를 앞으로 이동시킨다:
[ "e" | "b", "c", "d", "a", "f", "g" ]
i
| 막대는 두 영역을 구분한다. "e"는 우리가 선택한 첫 번째 엘리먼트다. 막대 오른쪽의 모든 엘리먼트는 아직 살펴봐야 한다.
다시 i와 a.count 사이의 난수를 요청하지만, i가 이동했으므로 난수는 1보다 작을 수 없다. 따라서 "e"를 다시 교환할 일은 없다.
난수가 6이고 "b"와 "g"를 교환한다고 가정하자:
[ "e" , "g" | "c", "d", "a", "f", "b" ]
i
한 번 더 난수를 선택하고, 이 값이 다시 4라고 가정하자. "c"와 "a"를 교환하여 왼쪽에 최종 선택을 얻는다:
[ "e", "g", "a" | "d", "c", "f", "b" ]
이제 끝이다. 이 함수의 성능은 **O(k)**이다. k개의 엘리먼트를 선택하면 작업이 완료되기 때문이다.
다음은 "저수지 샘플링"이라는 대체 알고리즘이다:
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
}이 알고리즘은 두 단계로 작동한다:
result 배열을 원본 배열의 첫 k개 엘리먼트로 채운다. 이를 "저수지"라고 한다.이 알고리즘의 성능은 **O(n)**이므로 첫 번째 알고리즘보다 조금 느리다. 그러나 큰 장점은 메모리에 맞지 않는 큰 배열에도 사용할 수 있다는 점이다. 심지어 배열의 크기를 모르는 경우에도 사용할 수 있다(스위프트에서는 파일에서 엘리먼트를 읽는 지연 생성자와 같은 것일 수 있다).
이전 두 알고리즘의 단점은 엘리먼트의 원래 순서를 유지하지 않는다는 점이다. 입력 배열에서 "a"가 "e"보다 앞에 있었지만, 이제는 반대가 되었다. 앱에서 이 문제가 중요하다면 이 방법을 사용할 수 없다.
원래 순서를 유지하는 대체 방법이 있지만, 조금 더 복잡하다:
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
}이 알고리즘은 확률을 사용해 선택에 숫자를 포함할지 여부를 결정한다.
루프는 배열을 처음부터 끝까지 순회한다. n개의 집합에서 k개의 아이템을 선택할 때까지 계속한다. 여기서 k는 requested이고 n은 a.count이다.
0과 1 사이의 난수를 계산한다. 0.0 <= r < 1.0이 되기를 원한다. 상한은 배타적이다. 절대 정확히 1이 되지 않도록 arc4random()의 결과를 0x100000000으로 나눈다.
leftToExamine는 아직 살펴보지 않은 아이템의 수이다. leftToAdd는 작업을 완료하기 전에 선택해야 할 아이템의 수이다.
여기서 마법이 일어난다. 기본적으로 동전을 던지는 것과 같다. 앞면이면 현재 배열 엘리먼트를 선택에 추가하고, 뒷면이면 건너뛴다.
흥미롭게도 확률을 사용하지만, 이 방법은 항상 출력 배열에 정확히 k개의 아이템이 있음을 보장한다.
동일한 예제를 다시 살펴보자. 입력 배열은 다음과 같다:
[ "a", "b", "c", "d", "e", "f", "g" ]
루프는 각 엘리먼트를 순서대로 살펴보므로 "a"부터 시작한다. 0과 1 사이의 난수를 얻고, 이 값이 0.841이라고 가정하자. // 4의 공식은 살펴볼 아이템의 수에 이 난수를 곱한다. 아직 7개의 엘리먼트가 남아 있으므로 결과는 다음과 같다:
7 * 0.841 = 5.887
이 값을 3과 비교한다. 3개의 아이템을 선택하려고 했기 때문이다. 5.887이 3보다 크므로 "a"를 건너뛰고 "b"로 이동한다.
다시 난수를 얻고, 이 값이 0.212라고 가정하자. 이제 살펴볼 엘리먼트가 6개 남아 있으므로 공식은 다음과 같다:
6 * 0.212 = 1.272
이 값은 3보다 작으므로 "b"를 선택에 추가한다. 이제 선택한 첫 번째 아이템이므로 두 개가 더 남았다.
다음 엘리먼트인 "c"로 이동한다. 난수가 0.264이고, 결과는 다음과 같다:
5 * 0.264 = 1.32
선택해야 할 엘리먼트가 2개 남아 있으므로 이 숫자는 2보다 작아야 한다. 조건을 만족하므로 "c"도 선택에 추가한다. 총 선택은 [ "b", "c" ]이다.
선택해야 할 아이템이 하나 남았지만, 아직 4개의 후보가 있다. 다음 난수가 0.718이라고 가정하자. 이제 공식은 다음과 같다:
4 * 0.718 = 2.872
이 엘리먼트를 선택하려면 숫자가 1보다 작아야 한다. 그렇지 않으므로 "d"를 건너뛴다. 이제 세 가지 가능성만 남았다.
난수가 0.346이다. 공식은 다음과 같다:
3 * 0.346 = 1.038
조금 높다. "e"를 건너뛴다. 이제 두 개의 후보만 남았다.
이제 동전 던지기와 같다. 난수가 0.5보다 작으면 "f"를 선택하고 작업이 완료된다. 0.5보다 크면 마지막 엘리먼트로 이동한다. 난수가 0.583이라고 가정하자:
2 * 0.583 = 1.166
"f"를 건너뛰고 마지막 엘리먼트를 살펴본다. 여기서 어떤 난수를 얻든 항상 "g"를 선택해야 한다. 그렇지 않으면 충분한 엘리먼트를 선택하지 못하게 되고 알고리즘이 작동하지 않는다!
마지막 난수가 0.999라고 가정하자(1.0 이상이 될 수 없다는 점을 기억하자). 여기서 무엇을 선택하든 공식은 항상 1보다 작은 값을 반환한다:
1 * 0.999 = 0.999
따라서 아직 충분한 선택을 하지 못했다면 마지막 엘리먼트가 항상 선택된다. 최종 선택은 [ "b", "c", "g" ]이다. 배열을 왼쪽에서 오른쪽으로 살펴보았기 때문에 엘리먼트가 원래 순서대로 유지된다.
아직 확신이 서지 않는다면... 항상 0.999를 난수로 얻는다면(가능한 최대값), 여전히 3개의 아이템을 선택할까? 계산해 보자:
7 * 0.999 = 6.993 3보다 작은가? 아니오
6 * 0.999 = 5.994 3보다 작은가? 아니오
5 * 0.999 = 4.995 3보다 작은가? 아니오
4 * 0.999 = 3.996 3보다 작은가? 아니오
3 * 0.999 = 2.997 3보다 작은가? 예
2 * 0.999 = 1.998 2보다 작은가? 예
1 * 0.999 = 0.999 1보다 작은가? 예
항상 작동한다! 그러나 이는 배열의 끝에 가까운 엘리먼트가 처음에 있는 엘리먼트보다 선택될 확률이 더 높다는 것을 의미할까? 아니다. 모든 엘리먼트가 동일한 확률로 선택된다(직접 테스트해 보라).
이 알고리즘을 테스트하는 방법은 다음과 같다:
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)**이다. 전체 입력 배열을 한 번 순회해야 할 수 있기 때문이다.
참고:
k > n/2인 경우, 반대로a.count - k개의 아이템을 제거하는 것이 더 효율적이다.
이 코드는 Algorithm Alley, Dr. Dobb's Magazine, 1993년 10월호를 기반으로 한다.
Swift Algorithm Club의 Matthijs Hollemans가 작성함