이 글을 쓰게 된 이유
회사에서 소켓서버를 전담하게 되어 기존에 있던 코드를 전달 받게 되었는데 기존 코드에서 아래의 함수를 발견하게 되었다.
function shuffle(array) {
array.sort(() => Math.random() - 0.5);
}해당 함수를 뜯어보면 sort와 Math.random() - 0.5 가 합쳐져 있는 코드이다.
sort는 리턴값이 음수이면 a와 b의 자리를 바꾸고 양수라면 바꾸지 않는 메서드,
Math.random()은 0보다 크고 1보다 작은 난수를 랜덤하게 생성한다.
즉 0.xxxxxx 이런식으로 나오는 것인데 거기에서 0.5를 빼니 양수나 음수를 랜덤으로 뱉게 되는 것이다.
양수나 음수를 랜덤으로 뱉으니 자리가 랜덤으로 바뀌게 되는 것이고 배열의 셔플이 가능해지게 된다.
겉보기에는 문제가 없이 작동이 될 것 같은 함수이다.
실제로 셔플에는 문제가 없기도 하다. 다만, 결과값이 한쪽으로 편향되게 나온다는 문제가 있다.
function shuffle(array) {
array.sort(() => Math.random() - 0.5);
}
let count = {
123: 0,
132: 0,
213: 0,
231: 0,
321: 0,
312: 0,
};
for (let i = 0; i < 1000000; i++) {
let array = [1, 2, 3];
shuffle(array);
count[array.join("")]++;
}
console.log(count);sort와 Math.random() - 0.5를 이용한 셔플 함수의 결과값을 세는 로직이고 아래는 코드를 돌렸을 때의 결과 값이다.
123과 321이 지나치게 많이 나오는 것을 볼 수가 있다.
랜덤으로 셔플을 하지만 운이 아닐수도 있는 이상한 상황이 생길 수 있는 것이다.
문제점을 찾아보자
왜 이러한 상황이 발생하는지에 대해서 찾아보기전에 가설을 세워보았다.
Math.random()의 문제가 아닐까? 라는 가설이다.
이러한 가설을 세우게 된 배경은 다음과 같다.
1. 해당 함수는 sort와 Math.random() - 0.5를 섞은 함수이다.
2. 그렇다면 sort에 문제가 있거나 Math.random() - 0.5에 문제가 있거나 둘을 합쳤을 때 문제가 발생하는 것이 아닐까?
3. sort는 리턴값이 음수인지 양수인지에 따라서 위치를 배치하는 단순명료한 함수이다.
4. 그럼 음수나 양수를 리턴하는 Math.random() - 0.5가 일정한 패턴으로 규칙적이게 나오는 것이 아닐까?
5.Math.random() - 0.5에서 어떤 값이 나오는지 불확실한 것은 -0.5가 아닌 Math.random() 이니까 여기에 문제가 있을 수도 있겠다
Math.random()의 문제점
Math.random()에 초점을 맞추고 알아보다 보니 MDN에 이러한 내용이 있었다.
// Note: Math.random() does not provide cryptographically secure random numbers. Do not use them for anything related to security. Use the Web Crypto API instead, and more precisely the window.crypto.getRandomValues() method.
참고: Math.random()은 암호학적으로 안전한 난수를 제공하지 않습니다. 보안과 관련된 어떤 용도로도 사용하지 마세요. 대신 Web Crypto API, 더 정확하게는 window.crypto.getRandomValues() 메서드를 사용하세요.
원인은 다음과 같다.
1. 균일한 분포 내에서 랜덤 정수를 생성하는데 사용되는 로직이 부적절하고 일반적으로 편향되어 있음
2. 사용해야할 임의의 비트/바이트 수가 브라우저 별로 일치 하지 않음
3. 무작위 결과값은 항상 일관되게 다시 생성하기 어려우므로, 이는 본질적으로 비결정적이고 불규칙함
4. 빌트인 시드가 변조될 수 있으므로 무결성 측면에서 부적합
출처: https://yceffort.kr/2021/09/javascript-random-number
결국 랜덤으로 정수를 생성하는 Math.random()이 일반적으로 편향된다는 문제가 있는 것이다.
해결법
내가 선택한 해결법은 셔플에 관한 로직을 직접 구성하는 것이다.
피셔-예이츠 셔플이라는 알고리즘인데
배열의 맨 끝에서부터 앞으로 전진하면서 배열의 랜덤한 인덱스와 자리를 바꾸는 방식이다.
function shuffle(array) {
for (let i = array.length - 1; i > 0; i--) {
let j = Math.floor(Math.random() * (i + 1));
[array[i], array[j]] = [array[j], array[i]];
}
}해당 셔플 함수를 100만번 돌린 후 그 결과값들의 분포를 알아보았다.
보다시피 결과값이 고르게 잘 나오는 것을 볼 수 있다.
여담
해당 문제를 해결하던 과정에서 문득 node에서의 arr.sort() 메서드는 어떤식으로 작동이 되는지가 궁금해졌다.
여기서 node라고 특정을한 이유는 사용하는 엔진에 따라서 알고리즘이 다를 수 있다는 얘기를 들은 적이 있기 때문이다.
들은 얘기일 뿐 검증을 해본것은 아니기 때문에 만약 아니라면 말씀해주시면 감사하겠습니다.
여러 글들을 참고해도 node가 sort() 메서드를 사용할 때 어떤 알고리즘으로 작동하는지를 적은 글을 찾을 수 없어서
Github에서 V8 레포에 들어간 뒤 sort를 검색해 보았더니 arr-sort 파일을 찾았고 해당 내용을 찾을 수 있었다.
// This file implements a stable, adapative merge sort variant called TimSort.
이 파일은 TimSort라는 안정적이고 적응적인 병합 정렬 변형을 구현합니다.
TimSort란 이진 삽입과 병합 정렬을 섞은 정렬 알고리즘이다.
해당 내용에 대해서는 추후에 다시 정리해볼 예정이라서 해당 글에서는 다루지 않겠지만 TimSort가 어떤 식으로 작동하는지 잘 나타낸 이미지가 있어서 공유한 뒤 이 글을 끝내보려고 한다.
