유저 대상 설문조사 기능을 개발하면서, 질문에 대한 응답 선택지를 무작위로 섞는 기능이 요구사항에 있었다.
이왕이면 팀원들도 나중에 사용하도록 유틸로 개발하기 위해서 해당 기능을 개발하기 위해서 무작위 알고리즘에 대해 공부하게 되었다.
설문조사의 선택지들은 배열 형태이고, 이를 무작위의 순서로 보여주기 위해서는 각 선택지(원소)의 순서를 재배치했다.
이와 같은 문제에서 사용하는 무작위 알고리즘은 대표적으로 다음과 같은 것들이 있다.
1. Fisher-Yates Shuffle
2. Knuth Shuffle
3. Sattlo Shuffle
O(n^2)
이다.O(n)
O(n)
O(n)
O(n)
이 된다.// golang
func SliceShuffle[T any](slice []T) {
for i := len(slice) - 1; i > 0; i-- {
j := rand.Intn(i + 1) // 0 <= j <= i
slice[i], slice[j] = slice[j], slice[i]
}
}
//golang
func SliceShuffle[T any](slice []T){
for i := len(slice) - 1; i > 0; i -- {
j := rand.Intn(i) // 0 <= j < i
slice[i], slice[j] = slice[j] , slice[i]
}
}
Knuth Shuffle 이나 Sattlo Shuffle은 거의 같은거 같고, 제자리를 배제해야 하는 필요가 있을때 Sattlo Shuffle을 사용하면 될 것 같다고 생각하고 함수를 만든 순간...
go rand 패키지 안에 rand.Shuffle 이라는 함수가 있는걸 알았다...😂
내장 패키지부터 살펴보자... 🙏🙏