완벽(해보이는) 랜덤 정렬 만들기

우선 컴퓨터로 완벽한 난수를 생성할 수 없다는 것을 이해하자. 컴퓨터는 유한 오토마타이고, 랜덤 또한 랜덤처럼 보이도록 동작하는 결과를 유한하게 만들어낸다. 이를 위해 seed 값을 사용하는데, 이를 통해 만약 동일한 랜덤 함수에 동일한 seed 값을 넣으면 그 결과는 당연히 동일하다는 것이 컴퓨터로 완벽한 난수를 생성할 수 없는 이유이다.

그래서 컴퓨터는 ‘완벽해보이는’ 난수를 생성하는 방향으로 발전했다.

완벽한 정렬이라고 생각했던 알고리즘이 있다. 아래를 참고했다.

https://docs.unity3d.com/kr/2023.2/Manual/class-Random.html 중 ‘리스트 순서 섞기’ 블록 (찾아보니 이 알고리즘은 ‘피셔-예이츠 셔플(Fisher-Yates Shuffle)’ 이라고 한다)

6/7 * 5/6 * 4/5 * … 계산을 통해 어떻게 배열이 되어도 모두가 동일한 확률이라고 생각했는데 현실에서는 그렇지 않을 수도 있겠다는 생각이 문득 들었다. 랜덤 함수의 연산 결과가 어떤 N의 배수라면 어떤 순간엔 완전한 랜덤이 아닌 특정한 것들만 뽑을 수 있겠다는 생각이 들었다. 랜덤 함수의 결과에 따라 잘못된 영향을 미칠 수 있다.

→ 랜덤을 만들어내는 난수생성기의 성능에 좌우될 수 있다.

→ 이 알고리즘 자체는 이론적으로는 완벽하지만, 실제 구현은 난수생성기의 성능에 따라 깨질 수 있다는 것이다.

해시를 예로 들면, 해시에서 bucket 사이즈를 소수로 만드는 게 유리하다. 이유는 서로소를 이용하겠다는 것인데, 다음 문제를 보자. 만약 bucket 사이즈는 10인데, bucket을 채우는 해시 함수가 12의 배수만 리턴하면 bucket 사이즈로 모듈러를 하면 그 값은 0, 2, 4, 6, 8로 전체 bucket의 절반에만 접근하는 결과를 만든다.

→ 잘못된 해시 함수로 인해 해시 효율이 반토막이 났다.

해시 함수가 잘못되었다고 하더라도 만약 bucket 사이즈가 소수(a)이고, 해시 함수의 결과가 a의 배수를 리턴하는 게 아니라면 서로소이기 때문에 해시테이블을 골고루 채우게 된다. 그러니 bucket의 사이즈는 소수로 만들자. 어쨌든 이런 문제도 해시 함수가 균일한 난수를 생성하지 못해서 발생하는 문제이다.

결국 해결 방법은 더욱 완벽한 난수생성기를 쓰는 것인데…

C++11에서 rand()의 표준으로 채택된 Mersenne-twister(MT19937) 알고리즘을 보게 되었다.

메르센 소수는 메르센 수($2^n-1$) 중에서 그 결과가 소수인 것. 결과가 메르센 소수인 n은 소수이다.
MT19937의 의미는 $n=19,937$이란 뜻이며, $2^{19,937}-1$(6,002자리 수)을 의미한다. 19,937은 소수이다.

현대의 난수생성에는 mt19937 알고리즘을 통해 성능 좋은 유사난수를 만들 수 있다고 하니 랜덤은 mt19937 알고리즘을 이용하자!

#include <iostream>
#include <random>

int main(void)
{
    std::random_device random;                                //하드웨어 리소스를 기반으로 난수를 생성
    std::mt19937 engine(random());                            //메르센 트위스터 방식으로 난수를 생성하겠다는 선언
    std::uniform_int_distribution<int> distribution(0, 100);  //난수의 범위와 자료형 정의. rand() % 100과는 다르게 100도 나올 수 있음
    auto generated = distribution(engine);
    std::cout << generated << std::endl;
}

결론

좋은 난수 생성기를 사용하면 피셔-예이츠 셔플의 과정에서 정확한 확률로 동작할 것으로 예상하니, 피셔-예이츠 알고리즘으로 이상적인 전체 정렬이 가능하다.

결론

기타