List내에 있는 값들중에 3개의 값만 랜덤으로 뽑는 방법을 알아보자.

서론

• 이번에 Java를 다시 학습을 목표로 미션을 만들어서 진행중에 있습니다.
• 그 첫번째 미션은 “숫자야구게임”을 현재 구현중에 있는데, 여기서 핵심적인 개념 중에 1~9까지의 숫자중에 중복되지 않는 3개의 숫자를 랜덤으로 뽑는 기능에 대해서 고민하던 중에 두가지 방법을 찾아 두가지 방법에 대해서 이야기를 해보려고 합니다.

Collections.shuffle을 사용해서 subList로 3개의 값을 추출

• Collections.shuffle() 은 리스트의 모든 요소를 랜덤으로 섞는 작업을 하는 메서드입니다.

public static void shuffle(List<?> list) {
    Random rnd = r;
    if (rnd == null)
        r = rnd = new Random(); // harmless race.
    shuffle(list, rnd);
}

public static void shuffle(List<?> list, Random rnd) {
    int size = list.size();
    if (size < SHUFFLE_THRESHOLD || list instanceof RandomAccess) {
        for (int i=size; i>1; i--)
            swap(list, i-1, rnd.nextInt(i));
    } else {
        Object[] arr = list.toArray();

        // Shuffle array
        for (int i=size; i>1; i--)
            swap(arr, i-1, rnd.nextInt(i));

        // Dump array back into list
        // instead of using a raw type here, it's possible to capture
        // the wildcard but it will require a call to a supplementary
        // private method
        ListIterator it = list.listIterator();
        for (Object e : arr) {
            it.next();
            it.set(e);
        }
    }
}

• 해당 메서드를 핵심적인 부분만 요약해서 살펴보겠습니다.
  • 이 구현은 리스트를 뒤에서부터 순회하며, 마지막 요소부터 두 번째 요소까지 랜덤으로 선택된 요소를 "현재 위치"와 반복적으로 교환합니다. 요소는 리스트의 첫 번째 요소부터 현재 위치까지의 부분에서 랜덤으로 선택됩니다. 만약 지정된 리스트가 RandomAccess 인터페이스를 구현하지 않고 SUFFLE_THRESHOLD(5)보다 Size가 크다면, 이 구현은 지정된 리스트를 배열로 덤프한 다음 셔플하고, 셔플된 배열을 다시 리스트로 덤프합니다. 이는 "순차 접근" 리스트를 제자리에서 셔플할 때 발생할 수 있는 이차 동작을 피하는 것입니다.
• Collections.shuffle()의 시간복잡도는 O(N)입니다.
• Collections.shuffle() 메서드는 사실 가변(mutable) 컬렉션에서 사용됩니다. 불변(immutable) 컬렉션은 변경할 수 없기 때문에 shuffle 메서드를 적용할 수 없습니다
• 위의 설명에 토대로 아래와 같이 작성해볼수 있을거 같습니다.

public class BaseBallNumberShuffleGenerator implements BaseBallNumberGenerator {
    private static final Set<Number> numbers = Set.of(
            new Number(1),
            new Number(2),
            new Number(3),
            new Number(4),
            new Number(5),
            new Number(6),
            new Number(7),
            new Number(8),
            new Number(9)
    );

    @Override
    public List<Number> generate() {
        List<Number> pickNumbers = new ArrayList<>(numbers);

        Collections.shuffle(pickNumbers);

        return pickNumbers.subList(0, 3);
    }
}

1. Set의 numbers는 캐싱을 위해 적용하였습니다.
2. Collections.shuffle은 List에서만 가능하며, 원본 Collection을 직접 수정하기 때문에 pickNumbers라는 List로 복사합니다.
3. Shuffle을 한 뒤에 subList를 통해 앞에서 3개를 뽑습니다.
   1. 여기서 순서는 무의미 합니다. 어차피 Shuffle을 하기 떄문에 뒤에서 3개를 뽑아도 되며, 이건 구현자의 편의성에 따르면 됩니다.

랜덤 인덱스 생성 후 직접 선택

• 필요한 만큼의 인덱스를 랜덤으로 생성해 해당 인덱스의 요소만을 선택하는 방법을 사용하면 됩니다.
• 그러나 여기서 우리는 1~9까지 중복되지 않는 3개의 수를 뽑아야 돼기 때문에 기본적으로 좀더 걸릴수 있습니다.
• 일단 해당 인덱스로 요소를 찾는데 걸리는 시간은 주로 O(1)의 시간복잡도가 있습니다.
• 이 경우에는 Collections에 요소가 많지만, 실제 랜덤으로 뽑아야 하는 값이 적은 경우에 사용하면 효과적입니다.
  • 해당 부분은 따로 밴치마킹 성능을 체크해봐야 한다고 생각합니다. 이건 각 상황에 따라 달라지기 떄문에 벤치마킹을 직접 하시는걸 추천드립니다.

public class BaseBallNumberRandomIndexGenerator implements BaseBallNumberGenerator {
    private static final Random random = new Random();
    private static final List<Number> numbers = List.of(
            new Number(1),
            new Number(2),
            new Number(3),
            new Number(4),
            new Number(5),
            new Number(6),
            new Number(7),
            new Number(8),
            new Number(9)
    );

    @Override
    public List<Number> generate() {
        Set<Number> pickNumbers = new HashSet<>();

        while (pickNumbers.size() < 3) {
            int randomIndex = random.nextInt(numbers.size());
            Number pickNumber = numbers.get(randomIndex);

            pickNumbers.add(pickNumber);
        }

        return pickNumbers.stream()
                .toList();
    }
}

• 이제 코드를 살펴보겠습니다. 중복된 숫자가 되면 안되기 떄문에, 실제 pickNumbers의 Size가 3이 될때까지 계속 while을 처리합니다. Set이 있기 때문에 중복값은 들어가지 않을것입니다.
• randomIndex를 Random 객체를 이용해 추출하며, 그 부분을 get 메서드를 통해서 가져오면 됩니다.

벤치마킹

• 여러가지를 고려해봐야 겠지만, 간단하게 얼마나 시간을 걸리는지 정도만 확인해보려고 합니다.
• 10000번을 호출했을때 총 시간이 얼마나 걸릴지 확인하는 코드는 아래와 같습니다.

public class Benchmark {

    private static final int ITERATIONS = 10000;

    public static void main(String[] args) {
        benchmarkShuffleMethod();
        benchmarkRandomIndexMethod();
    }

    private static void benchmarkShuffleMethod() {
        long startTime = System.nanoTime();
        for (int i = 0; i < ITERATIONS; i++) {
            BaseBallNumberGenerator baseBallNumberShuffleGenerator = new BaseBallNumberShuffleGenerator();
            baseBallNumberShuffleGenerator.generate();
        }
        long endTime = System.nanoTime();
        long duration = (endTime - startTime) / 1_000_000; // Convert to milliseconds
        System.out.println("Shuffle method took: " + duration + " ms");
    }

    private static void benchmarkRandomIndexMethod() {
        long startTime = System.nanoTime();
        for (int i = 0; i < ITERATIONS; i++) {
            BaseBallNumberGenerator baseBallNumberRandomIndexGenerator = new BaseBallNumberRandomIndexGenerator();
            baseBallNumberRandomIndexGenerator.generate();
        }
        long endTime = System.nanoTime();
        long duration = (endTime - startTime) / 1_000_000; // Convert to milliseconds
        System.out.println("Random index method took: " + duration + " ms");
    }
}

Shuffle method took: 5 ms
Random index method took: 11 ms

• 위에서는 Shuffle이 더 낮은 시간이 걸리는걸 확인할수 있었습니다.

결론

• 만약 리스트에서 소수의 요소만 랜덤으로 선택하려 한다면, 랜덤으로 인덱스를 생성하는 방법이 더 효율적일 수 있습니다.
• 리스트의 크기가 크고 무작위로 선택된 소수의 요소만 필요한 경우에는 **Collections.shuffle()**을 사용하는 것이 더 효율적일 수 있습니다