아주 심플한 가중치 랜덤 뽑기

어떤 상자를 열면 A, B, C, D, E 다섯 개의 아이템 중 하나가 나온다.

 

그리고 이 다섯 개의 아이템이 나올 확률이 각각 다르다면 대부분은 이것을 테이블화시킬 것이다.

 

하지만 이런식으로 테이블을 만들면 문제가 생긴다.

 

한 아이템의 확률을 조정하거나, 아이템을 삭제하거나, 새 아이템을 추가하게 된다면

 

모든 아이템의 확률 총합이 100%가 되지 않게 되면서, 그때마다 나머지 아이템들의 확률도 같이 조정해야 한다.

 

 

그래서 가중치라는 게 필요하다.

 

 

 

각 아이템의 가중치를 그 아이템의 부피라고 생각할 수 있다. 그림처럼 일렬로 붙인 다음에

 

Random pivot 포인터가 왼쪽 끝에서부터 오른쪽 끝까지 왔다 갔다 한다고 가정해보자.

 

어느 순간에 포인터를 스탑 시키고, 포인터가 어디 위에서 멈췄는지 확인하는 것이 가중치 랜덤 뽑기라고 할 수 있다.

 

 

export default class WeigthedRandomPicker {
    percentageItems: Array<any>;

    private Apply<T>(weightedItems: Array<{key: T, weight: number}>) {
        // 총 가중치의 합 계산
        let totalWeight = 0;
        weightedItems.forEach(x => totalWeight += x.weight);

        // 각 아이템의 가중치를 백분율로 치환 (가중치/총 가중치)
        this.percentageItems = [];
        weightedItems.forEach(x => {
            this.percentageItems.push({key: x.key, percent: x.weight/totalWeight});
        });
    }

    GetRandomItem<T>(weightedItems: Array<{key: T, weight: number}>): T {
        this.Apply(weightedItems);

        let random = Math.random();
        let sum = 0;
        let find = null;
        this.percentageItems.forEach(x => {
            sum += x.percent;
            if (find == null && sum >= random) find = x.key;
        })
        return find;
    }
}

let weightTable = [{key: 'A', weight: 420},
                   {key: 'B', weight: 320},
                   {key: 'C', weight: 320},
                   {key: 'D', weight: 660},
                   {key: 'E', weight: 280}];
                   
let randomKey = this.randomPicker.GetRandomItem<string>(weightTable);

A 아이템의 가중치가 총가중치의 합계에서 몇 퍼센트를 차지하는지 구한 뒤 새로운 배열 percentageItems로 저장한다.

 

그리고 percentageItems를 순회하면서 값을 누적하고, 그때마다 0.0 ~ 1.0 사이의 난수와 크기를 비교한다.

 

누적 값이 생성한 난수 이상이 되면 그 때의 percentageItems 인덱스가 랜덤 뽑기에 걸린 인덱스가 된다.

 

 

 

- GetRandomItem으로 아이템을 뽑을 때마다 새 테이블을 참조하도록 했다.

 

WeigthedRandomPicker 클래스가 테이블을 캐싱하고 있으면

 

이 테이블에 대한 관리(아이템 추가, 삭제 등) 기능도 요구되기 때문에 그러한 기능은 추가하지 않았다.

 

 

- 참조하는 테이블의 구조를 Map이 아닌 Array<{key, value}> 구조를 선택했다.

 

이 자료구조는 Map 형태의 데이터를 배열처럼 쓸 수 있어서 편하지만, for 반복문으로 순회할 수 없다.

 

그렇기 때문에 배열을 순회 중에 누적값이 난수 이상이 됐을 때

 

for문이었다면 break를 통해서 빠져나와야 하는데 forEach에선 불가능해서,

 

뽑기 값을 찾았는지에 대한 여부(find)를 확인하는 코드로 대체했다.