리팩토링(Refactoring) - 랜덤 쿠폰 뽑기 성능 개선하기

배경

새해 기념 랜덤 쿠폰 이벤트 페이지를 개발하면서 기존 랜덤 쿠폰 발급 성능을 개선했던 과정을 정리해본다.

가중치 기반 랜덤 알고리즘은 다음 글에서 정리했으니 궁금하다면 참고 바란다.

Algorithms - 가중치 랜덤 알고리즘(랜덤 쿠폰 뽑기)

 

개발 환경

• Java 8
• Spring
• IntelliJ

 

기존 로직

기존 랜덤 쿠폰 발급 로직 흐름을 살펴보자

1. 가중치 배열을 순회하며 누적 합(runningTotal)을 계산
2. 각 누적 합을 리스트(totals)에 추가 
3. 총 누적 합 범위 내에서 랜덤 값(randomWeight) 생성
4. 리스트(totals)를 순회하며 랜덤 값(randomWeight)이 어떤 구간에 속하는지 확인
5. 특정 구간에 속하는게 확인되면 해당 구간과 동일한 인덱스의 쿠폰 반환

기존 방식은 각 쿠폰의 가중치 누적 합계를 미리 계산하고, 랜덤 값과 비교하는 방식이었다.

아래 코드는 기존 알고리즘 이해를 위한 예시 코드다.

    private static int legacyWeightedChoice(int[] weights) {
    	/**
         * 1. 가중치 배열을 순회하며 누적 합(runnigTotal) 계산
         * 2. 각 누적 합을 리스트(totals)에 추가
        **/
        List<int> totals = new ArrayList<>();
        int runningTotal = 0;
        for (int weight : weights) {
            runningTotal += weight;
            totals.add(runningTotal);
        }
        /**
         * 3. 리스트(totals)를 순회하며 랜덤 값(randomWeight)이 어느 구간에 속하는지 체크
         * 4. 특정 구간에 속하는게 확인되면 해당 구간과 동일한 인덱스 반환
        **/
        int randomWeight = random.nextInt(runningTotal);
        for (int i = 0; i < weights.length; i++) {
            if (randomWeight < totals.get(i)) {
                return i;
            }
        }
        return weights.length - 1;
    }

 

문제점

기존 로직에는 다음과 같은 문제점이 있었다.

• O(n) 공간 복잡도: 가중치 누적 합계를 저장하기 위해 쿠폰 종류만큼의 별도의 리스트(totals)가 필요했다.
• 불필요한 반복: 누적 합계 생성과 검색을 위해 반복문을 두 번 실행하고 있다.
• 확장성 문제: 위와 같은 문제로 쿠폰 종류와 발급 횟수가 많아질수록 메모리와 성능 저하 문제가 발생할 수 있다.

공간 복잡도는 알고리즘을 실행하는 데 필요한 메모리 공간의 양을 나타낸다.
이는 알고리즘의 입력 크기와 처리 과정에서 사용되는 메모리 공간을 고려하여 평가된다.

 

로직 개선

위와 같은 문제를 해결하기 위해 공간 복잡도를 O(1)로 줄이고, 단일 루프로 처리하도록 재설계했다.

개선된 로직 흐름은 다음과 같다.

1. 가중치 배열을 순회하며 모든 가중치의 합(totalWeight)을 계산
2. 전체 가중치 합 범위 내에서 랜덤 값(randomWeight) 생성
3. 가중치 배열을 순회하며 랜덤 값에서 각 가중치를 차감
4. 랜덤 값이 0 미만이 되는 시점의 인덱스 반환

코드로 확인해보자

    private static int optimizedWeightedChoice(Integer[] weights) {
        /**
         * 1. 가중치 배열을 순회하며 모든 가중치의 합(totalWeight)을 계산
        **/
        int totalWeight = 0;
        for (int weight : weights) {
            totalWeight += weight;
        }
        
        /**
         * 2. 전체 가중치 합 범위 내에서 랜덤 값(randomWeight) 생성
         * 3. 가중치 배열을 순회하며 랜덤 값에서 각 가중치를 차감
         * 4. 랜덤 값이 0 미만이 되는 시점의 인덱스 반환
        **/        
        int randomWeight = random.nextInt(totalWeight);
        for (int i = 0; i < weights.length; i++) {
            randomWeight -= weights[i];
            if (randomWeight < 0) {
                return i;
            }
        }
        return weights.length - 1;
    }

기존의 누적 합계 리스트를 사용하는 방식 대신, 랜덤 값에서 각 가중치를 차감하는 방식으로 변경했다. 

이렇게 되면 누적 합계 값을 저장하기 위한 리스트를 만드는 과정이 생략되기 때문에 루프도 1회만 실행되도록 개선되었다.

이러한 변화를 통해 실행 시간을 단축하고 메모리 사용량을 줄일 수 있다. 말로만 성능이 향상되었다고 하는건 의미 없기 때문에 정말 성능 향상이 이루어졌는지 코드로 확인해보자.

🔥 잠깐!
이대로도 성능이 향상되지만 가중치 리스트를 내림차순으로 정렬 후 로직을 실행한다면 성능을 소폭 향상시킬 수 있다.
가장 큰 가중치를 먼저 처리하기 때문에 더욱 빠른 return 가능성을 높여주기 때문이다. 
이 부분도 코드를 통해 함께 확인해보자.

 

테스트

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;
import java.util.Random;

public class Main {

    private static final int COUPON_COUNT = 50;
    private static final int USER_COUNT = 1000000;
    private static final Random random = new Random();

    public static void main(String[] args) {
        Integer[] weights = generateWeights(COUPON_COUNT);

        // 기존 로직 성능 측정
        long linearStart = System.nanoTime();
        for (int i = 0; i < USER_COUNT; i++) {
            legacyWeightedChoice(weights);
        }
        long linearEnd = System.nanoTime();

        // 최적화된 로직 성능 측정
        long optimizedStart = System.nanoTime();
        for (int i = 0; i < USER_COUNT; i++) {
            optimizedWeightedChoice(weights);
        }
        long optimizedEnd = System.nanoTime();

        // 최적화된 로직 성능 측정(내림차순 정렬된 weights)
        Arrays.sort(weights, Collections.reverseOrder());
        long reverseOrderedOptimizedStart = System.nanoTime();
        for (int i = 0; i < USER_COUNT; i++) {
            optimizedWeightedChoice(weights);
        }
        long reverseOrderedOptimizedEnd = System.nanoTime();

        // 나노초를 초 단위로 변환하기 위해 1e9로 나눔 (1e9 = 10억)
        double legacyTime = (linearEnd - linearStart) / 1e9;
        double optimizedTime = (optimizedEnd - optimizedStart) / 1e9;
        double reverseOrderedOptimizedTime = (reverseOrderedOptimizedEnd - reverseOrderedOptimizedStart) / 1e9;
        double improvement = (legacyTime - optimizedTime) / legacyTime * 100;
        double reverseOrderedImprovement = (legacyTime - reverseOrderedOptimizedTime) / legacyTime * 100;

        System.out.printf("기존 로직 실행 시간: %.3f seconds%n", legacyTime);
        System.out.printf("최적화 로직 실행 시간: %.3f seconds%n", optimizedTime);
        System.out.printf("최적화 로직 실행 시간(내림차순): %.3f seconds%n", reverseOrderedOptimizedTime);
        System.out.printf("쿠폰 %d종, 발급 %d건 기준: %.2f%% 성능 향상%n", COUPON_COUNT, USER_COUNT, improvement);
        System.out.printf("쿠폰 %d종, 발급 %d건 기준(내림차순): %.2f%% 성능 향상%n", COUPON_COUNT, USER_COUNT, reverseOrderedImprovement);
    }

    // 기존 로직
    private static int legacyWeightedChoice(Integer[] weights) {
        List<Integer> totals = new ArrayList<>();
        int runningTotal = 0;
        for (int weight : weights) {
            runningTotal += weight;
            totals.add(runningTotal);
        }
        int randomWeight = random.nextInt(runningTotal);
        for (int i = 0; i < weights.length; i++) {
            if (randomWeight < totals.get(i)) {
                return i;
            }
        }
        return weights.length - 1;
    }

    // 최적화된 로직
    private static int optimizedWeightedChoice(Integer[] weights) {
        int totalWeight = 0;
        for (int weight : weights) {
            totalWeight += weight;
        }
        int randomWeight = random.nextInt(totalWeight);
        for (int i = 0; i < weights.length; i++) {
            randomWeight -= weights[i];
            if (randomWeight < 0) {
                return i;
            }
        }
        return weights.length - 1;
    }

    // 가중치 목록 생성
    private static Integer[] generateWeights(int count) {
        Integer[] weights = new Integer[count];
        for (int i = 0; i < count; i++) {
            weights[i] = random.nextInt(90) + 10; // 10 ~ 99
        }

        return weights;
    }
}

적은 수량과 발급 횟수에서는 기존 로직에서도 빠르게 처리되기 때문에 유의미한 성능 차이는 확인할 수 없지만 대규모 데이터 처리 상황에서는 꽤 유의미한 성능 차이를 확인할 수 있다. 그리고 가중치 리스트를 내림차순 정렬한 후 실행했을 때 성능이 소폭 향상된 것도 확인할 수 있다.

이번 개선을 통해 아래와 같은 성과를 얻을 수 있었다.

• 메모리 최적화: 불필요한 데이터 저장 제거
• 속도 개선: 단일 루프로 처리 속도 개선 (쿠폰 50종, 발급 100만건 기준: 92% 성능 향상)
• 확장성 확보: 대규모 데이터 처리 시에도 안정적으로 동작

 

참조

Weighted random generation in Python - Eli Bendersky's website