광고 추천 시스템, 가중 무작위 셔플 알고리즘으로 성능 UP!
by DD
10년 전
조회수 4
Buzzvil의 광고 추천 시스템인 BuzzAd에서 가중 무작위 셔플(WRS) 알고리즘을 활용하여 광고 및 콘텐츠를 효율적으로 제공함
BST(Binary Search Tree)를 사용하여 O(N^2)의 시간 복잡도를 가지는 기존 방식에서 O(NlogN)으로 성능을 개선함
BST 구성 시 가중치를 기준으로 정렬하여 평균 실행 시간 단축 및 캐싱 기법을 통해 대규모 데이터 처리에 대한 최적화를 수행함
가중 무작위 셔플 알고리즘의 동작 원리
가중 무작위 셔플 알고리즘은 각 항목에 가중치를 부여하여 확률적으로 선택하는 방식이다. BST를 활용하여 O(logN)의 시간 복잡도로 탐색 및 업데이트를 수행한다. 구체적으로, 각 노드는 (weight, total_weight_of_subtree) 튜플을 가지며, 탐색 시 이진 탐색을 통해 원하는 항목을 찾는다.
Naive Approach vs BST: 성능 비교
Naive Approach는 O(n^2)의 시간 복잡도를 가지는 반면, BST 기반 구현은 O(NlogN)으로 성능을 개선한다. 따라서 대규모 데이터 환경에서 BST는 훨씬 효율적이다. 반면, BST는 구현 복잡도가 높고, 메모리 사용량이 증가할 수 있다.
실전 적용을 위한 최적화 전략
가중치 배열을 내림차순으로 정렬하여 탐색 시간 단축을 꾀한다. 또한, Redis와 같은 캐시를 활용하여 트리 구성을 캐싱함으로써 성능을 향상시킨다. 따라서, 대량의 데이터를 처리하는 환경에서 알고리즘 성능 최적화를 달성할 수 있다.
