이 글이 작성된 해는 2014년도입니다. 최근(2016년 ~) 유행하고 있는 추천서비스 등과는 관련이 없는 내용이고 개인적인 필요에 의해서 뭔가 실험하고 작성한 내용이에요. 방문자가 별로 없는 블로그이지만 검색 등을 통한 이 글로의 유입량이 많아서 혹시 오해가 있을까하여 미리 밝혀둡니다.
복수의 아이템이 들어있는 자료구조에서 추첨을 해야하는 경우가 있다. 보통 추첨을 한다하면 무작위로 선택되어야 하는데 때에 따라서는 특정 아이템의 선택 확률을 높여야 할 수도 있다.
언어에 따라 조금 차이가 있기는 하지만 보통 random number 생성에 관계된 API들은 수학과 관련된 package로 묶여 있거나 연산에 특화된 기능들끼리 모여있다. 따라서 단순 random number 생성 이외의 기능, 가중치를 고려하는 부분은 직접 구현할 수 밖에 없다. 또는 가중치 고려가 가능하게 만들어진 오픈소스 라이브러리가 있을지도 모르겠는데 그리 복잡하지 않을 것 같아 직접 구현하기로 했다.
1. 가중치를 통해 선택확률 높이기
아래의 그림을 보면 윗 부분은 가중치가 1로 동일한 상태이고 아래는 특정 아이템에 가중치를 더 높임으로써 선택될 확률을 높인 상태이다. 칸으로 구별된 bar를 다루게 될 아이템이 담겨있는 자료구조로 보자. 각 칸에는 하나의 아이템이 담겨있고 좌측을 시작으로 우측으로 갈 수록 index가 높다고 하자.
이렇게 하는 것이 어떻게 선택될 확률을 높일 수 있을까?
Java를 기준으로 random number 생성을 살펴보면 단순히 Math.random() 호출시 0과 1사이에 있는 double 값을 생성해서 돌려주게 되어있다. (정확히 0.0 이상 1.0 미만의 값) Random number의 range를 0 ~ total weight로 설정하면 위 그림의 bar 상단에서 좌측에서 우측으로 증가하는 1차원 그래프를 상상해볼 수 있다. 즉 생성된 random number 가 찍히는 점의 아래에 있는 아이템이 선택될 수 있다.
Weight가 동일한 경우는 그래프에서 차지하는 영역이 동일하기 때문에 random number가 동일한 확률로 생성된다면 아이템이 선택될 확률도 동일하다고 볼 수 있다. 반면에 특정 아이템의 weight가 높은 경우 차지하는 영역이 넓어지기 때문에 그만큼 그 영역안에서 random number가 생성될 가능성이 다른 영역에 비하면 높아진다.
2. 그렇다면 구현은 어떻게 할까?
위 그림과 그래프를 상상해보면 구현은 간단하다. 각 아이템이 갖는 가중치를 모두 더해서 Math.random() 등으로 random number를 생성할 때 0부터 가중치합 사이의 값이 생성되도록 한다. (역시 언어에 따라 다르지만 random number 생성시 seed 값을 설정할 수 있어야 random number 생성의 중복을 방지할 수 있다. Java의 경우 Math 보다는 Random class를 사용하는게 나을 것으로 판단됨) 그렇게 생성된 random number를 가지고 자료구조에서 index를 증가시키며 각각의 아이템이 가진 가중치를 뺀다. (가중치를 빼지 않고 더해서 하는 방법도 있을텐데 그 경우 random number와의 비교구문이 약간 달라져야 할 것이다) 그렇게 진행하다보면 어느 순간 random number가 0이나 음수가 되는데 그 때의 아이템이 가중치에 따라 선택된 아이템이 된다. Pseudo code로 간단하게 작성하면 아래와 같다.
[java]
List<Item> list = getItemList();
double total = getTotalWeight(list);
for(int i = 0; i < list.size(); i++) {
total -= list.get(i).getWeight();
if(total <= 0) {
selectedIndex = i;
break;
}
}
return list.get(selectedIndex);
[/java]