Weighted Random Shuffling Algorithms

가중치 랜덤 셔플링 알고리즘(WRS)

• Buzzvil의 광고 서버 'BuzzAd'에서 최적화된 광고 및 콘텐츠 제공을 위해 사용.
• CTR 기반 정렬의 문제점: 시간에 따른 CTR 변화, 콜드 스타트 문제 발생.
• WRS의 개념: 항목을 가중치에 따라 순열하는 방법. $latex P_i = w_i\ /\ (W_A\ -\ W_S) $ 확률로 항목 선택.

WRS 구현 방법

• Naive 접근 방식: 가중치 배열을 주사위 던지기로 비유, $latex O(n^2)$의 시간 복잡도.
• Binary Search Tree(BST) 활용: 검색 및 업데이트를 $latex O(logN)$으로 최적화, 전체 복잡도를 $latex O(NlogN)$으로 감소.
• 트리 구성: 배열을 사용하여 이진 트리를 표현, 각 노드는 (weight, subtree_weight) 튜플 저장.
• 탐색 및 업데이트: 루트에서 시작, 가중치 비교 후 하위 트리로 이동, 노드 i를 찾으면 가중치를 0으로 업데이트하고 부모 노드 업데이트.

최적화 팁

• 가중치 내림차순으로 정렬하여 큰 가중치 노드를 루트 근처에 배치, 평균 실행 시간 개선.
• 배치 업데이트를 통해 트리 구성 부분을 캐싱.
• '복원 추출'의 경우 선형 시간 전처리 후 상수 시간 탐색/업데이트 알고리즘(alias method) 활용.