N번째 난수 값 얻어오기

문제

---

어떤 난수생성기가 있다고 가정하자. 이 난수 생성기로부터 N번째에 있는 난수를 얻고 싶다. 어떻게 해야 할까?

 

아니 애초에 위와 같은 상황은 무엇일까?

 

당신이 랜덤한 스테이지 A,B,C,D를 만든다고 가정하자. 한 스테이지는 1000개의 난수 시퀀스를 필요로 한다.

 

어떤 난수 생성기가 생성한 1001~2000번째의 난수를 이용해 A스테이지를 만들었다. 그리고 2001에서 3000까지의 난수를 이용해 B스테이지를 만들었다. 

 

이때 B스테이지에 있던 유저가 다시 A스테이지로 돌아갔다고 하자. 아니면 4001에서 5000번째까지의 난수를 필요로 하는 D스테이지로 곧바로 들어간다면?

 

과거에 생성했던 난수 시퀀스를 어딘가에 저장해 둔다거나 혹은 0번째부터 다시 Next()를 호출하며 목표로 하는 시퀀스까지 도달하는 방법은 비효율적이다.

 

바로 갈 수는 없을까?

 

 

 

 

오답 

---

그러면 그냥 시드값을 1~5000사이로 준다음 0번째 값을 사용하면 되지 않을까?라는 의문이 있다.

 

난수 생성 클래스 인스턴스를 5000개 생성해야 한다는 점은 눈감아 준다고 치고 결과는 제대로 나올까?

 

난수를 생성한 뒤 짝수면 검정 홀수면 흰색 이미지를 생성하도록 해서 결과를 보자.

 

 

 

윽 착시

 

아, 전혀 랜덤이 아니다! 만약 위와 같은 방법으로 스테이지를 생성했다면 큰일 날 것이다.

 

참고로 1개의 난수로 순차적으로 생성한 패턴은 다음과 같다.

 

 

 

 

해법 : 해쉬 함수

---

좋은 해답 중 하나는 해쉬 함수를 사용하는 것이다. 생각해보라, 데이터들이 주어졌을 때, 해쉬 함수가 생성해 내는 해쉬 값이 겹치지 않을수록 좋은 해쉬 함수이다. 즉, 좋은 해쉬 함수라면 생성하는 값들이 충분히 랜덤이라는 것이다.

 

예를 들어 int값 두 개를 받아 하나의 int 해쉬값을 반환하는 해쉬 함수를 만든다면? 그리고 그 결과가 무작위처럼 보인다면 괜찮지 않을까? 다음과 같이 말이다.

 

그 결과는?

 

오 ~ 그럴 듯 하다.

 

 

그렇다면 본격적으로 어떤 해쉬 함수가 있을까?

 

• PcgHash : 위에서 내가 예시로 들었던 해쉬 함수이다. 구현이 매우 간단하다. 여기에서 더 자세한 내용을 확인할 수 있다. 속도도 꽤 빠르다. 그러나 생성해 내는 난수의 퀄리티가 썩 좋지는 않다.
• MD5 : 암호화로 잘 알려진 해쉬 함수이다. 이걸 쓴다면 훌륭한 퀄리티의 랜덤 값을 보장받을 수 있지만 우리가 쓰고자 하는 용도에는 조금 과한 감이 있다. 매우 느리다.
• xxHash : 암호화용도가 아닌 빠른 해쉬 함수이다. MD5보다 뛰어난 퀄리티의 난수를 얻을 수 있으며 속도도 아주 빠르다.
• 기타 : MurmurHash3, Wang(Double)Hash등이 있다. 근데 아래 참고 블로그 작성자가 테스트한 바에 따르면 xxHash가 가장 좋다.

 

 

 

사실...

---

사실 맨 처음에 낸 문제는 A,B,C,D 스테이지마다 시드를 다 다르게 한 다음 1000개의 시퀀스를 매번 생성해 내는 방법을 사용할 수 있다. 그런데 마인크래프트와 같이 스테이지가 엄청 많다면? 이런 경우에는 랜덤 해쉬 함수를 이용하여 스테이지별로 시드를 생성하고, 각 스테이지별로 평범한 난수 생성기를 돌리는 방법을 사용할 수 있다.

 

 

---

참고 : https://blog.runevision.com/2015/01/primer-on-repeatable-random-numbers.html