개요
오늘도 5천원에 헛된 희망을 구매하고 로또를 보지만 언제나 낙첨...
1등이 6개나 되는군요. 왜 나는 안될까란 의구심을 품으며 이전 회차의 1등 복권수를 훓어봤습니다.
13개... 20개... 15개... 많이도 되네요. 1/815만 이라는데 어떻게 이렇게 많을까요?
1177회에 총판매금액은 115,411,832,000원 이라고 합니다. 1000원에 1장이니까 115,411,832장이 판매되었겠네요. 나눠보면 14.1장 얼추 맞는것 같네요.
예전 기억이 떠오릅니다. JAVA를 처음배울때 로또 생성하는걸 해봤었거든요. 오랜만에 한번 구현해보았습니다.
의식의 흐름대로 만들어보는 로또 시뮬레이션 최적화
요구사항
만들기전에 간단하게 요구사항을 정해봅시다.
1. 당첨번호 6개와 보너스번호 1개를 먼저 지정합니다.
2. 숫자의 범위는 1 ~ 45까지로 합니다.
3. 지정된 수만큼 로또 번호를 생성해 각 등수의 개수를 출력합니다.
4. 시작부터 종료까지의 시간을 측정합니다.
구현
MK-1
public class Main {
static final Set<Integer> targetNumbers = Set.of(3,7,15,16,19,43);
static final int bonusNumber = 21;
static final Map<Integer, Integer> ranking = new HashMap<>();
public static void main(String[] args) {
long start = System.currentTimeMillis();
int count = 115_411_832;
for (int i = 0; i < count; i++) {
int[] numbers = generateNumbers();
int rank = evaluate(numbers);
if (rank < 6) {
ranking.put(rank, ranking.getOrDefault(rank, 0) + 1);
}
}
long end = System.currentTimeMillis();
System.out.println(end - start + "/ms 소요");
print();
}
private static void print() {
for (int i = 1; i < 6; i++) {
System.out.printf("%d등 : %d명\n", i, ranking.get(i));
}
}
private static int evaluate(int[] numbers) {
int count = 0;
boolean hasBonusNumber = false;
for (int number : numbers) {
if (targetNumbers.contains(number)) {
count++;
} else if (number == bonusNumber) {
hasBonusNumber = true;
}
}
if (count == 6) { // 다 맞으면 1등
return 1;
}
if (hasBonusNumber) { // 보너스번호 맞으면 +1
count++;
}
return switch (count) {
case 6 -> 2; // 6개 맞으면 2등
case 5 -> 3; // 5개 맞으면 3등
case 4 -> 4; // 4개 맞으면 4등
case 3 -> 5; // 3개 맞으면 5등
default -> 6; // 그 외 6등
};
}
private static int[] generateNumbers() {
return new Random()
.ints(1, 46)
.limit(6)
.distinct()
.sorted()
.toArray();
}
}
생각나는대로 만들어봤습니다. 대충 보이시죠?
- count 만큼 반복
- generateNumbers()에서 로또번호 생성
- evaluate에서 등수 반환
- 1 ~ 5등까지 ranking에 넣고 출력
// 62697/ms 소요
// 1등 : 6명
// 2등 : 53명
// 3등 : 8592명
// 4등 : 279948명
// 5등 : 3602047명근데 세상에.. 62.7초나 걸렸군요. 너무 성의 없이 만든것 같습니다. 필요 없는 부분을 덜어내야겠어요.
MK-2 추상화
public interface LotterySimulator {
void execute();
void print();
}
public class Times {
public static void timer(Runnable runnable) {
long start = System.currentTimeMillis();
runnable.run();
long end = System.currentTimeMillis();
System.out.println(end - start + "/ms 소요");
}
}
public abstract class AbstractFixedCountLotterySimulator implements LotterySimulator {
protected final int count;
protected AbstractFixedCountLotterySimulator(int count) {
this.count = count;
}
abstract protected void innerExecute();
@Override
public final void execute() {
Times.timer(this::innerExecute);
}
}먼저 지저분한 코드를 로또 시뮬레이션을 완전 추상화 했습니다.
public class LotterySimulatorMK2 extends AbstractFixedCountLotterySimulator {
private final Set<Integer> targetNumbers;
private final int bonusNumber;
private final Map<Integer, Integer> ranking = new HashMap<>();
public LotterySimulatorMK2(int count, int[] targetNumbers, int bonusNumber) {
super(count);
this.targetNumbers = Arrays.stream(targetNumbers).boxed().collect(Collectors.toSet());
this.bonusNumber = bonusNumber;
}
@Override
protected void innerExecute() {
for (int i = 0; i < count; i++) {
int[] numbers = generateNumbers();
int rank = evaluate(numbers);
if (rank < 6) {
ranking.put(rank, ranking.getOrDefault(rank, 0) + 1);
}
}
}
private int[] generateNumbers() {
return new Random()
.ints(1, 46)
.limit(6)
.distinct()
.sorted()
.toArray();
}
private int evaluate(int[] numbers) {
int count = 0;
boolean hasBonusNumber = false;
for (int number : numbers) {
if (targetNumbers.contains(number)) {
count++;
} else if (number == bonusNumber) {
hasBonusNumber = true;
}
}
if (count == 6) { // 다 맞으면 1등
return 1;
}
if (hasBonusNumber) { // 보너스번호 맞으면 +1
count++;
}
return switch (count) {
case 6 -> 2; // 6개 맞으면 2등
case 5 -> 3; // 5개 맞으면 3등
case 4 -> 4; // 4개 맞으면 4등
case 3 -> 5; // 3개 맞으면 5등
default -> 6; // 그 외 6등
};
}
@Override
public void print() {
for (int i = 1; i < 6; i++) {
System.out.printf("%d등 : %d명\n", i, ranking.get(i));
}
}
}그리고 이전 코드를 똑같이 붙혀넣었습니다.
접근제한자를 보면 아시겠지만 LotterySimulator 인터페이스로는 내부 코드를 볼수없습니다. 내부 코드가 수정되어도 외부에서는 크게 중요하지 않다는거죠.
AbstractFixedCountLotterySimulator클래스에서 execute를 Override할때 final을 붙혀줘서 더이상의 상속을 막아 시간을 재는 로직이 override할 수 없도록 막았습니다.
public class Main2 {
public static void main(String[] args) {
int count = 115_411_832;
LotterySimulator simulator = new LotterySimulatorMK2(count);
simulator.execute();
simulator.print();
}
}이제 실행해보면
// 70337/ms 소요
// 1등 : 12명
// 2등 : 62명
// 3등 : 8488명
// 4등 : 281238명
// 5등 : 3600109명추상화했다고 7초나 더 걸리네요...
62697ms -> 70337ms
MK-3 최적화(1)
로또 생성 파트부터 보겠습니다.
1. Random 객체 재사용
2. sorted() 제거
생각해보니까 Random 객체를 매 번 생성하고있었습니다. 재사용하도록 고쳐주고, 정렬하는부분도 없애겠습니다. 해시값으로 값을 확인하기때문에 정렬을 필요 없습니다.
@Override
protected void innerExecute() {
Random random = new Random();
for (int i = 0; i < count; i++) {
int[] numbers = generateNumbers(random);
int rank = evaluate(numbers);
if (rank < 6) {
ranking.put(rank, ranking.getOrDefault(rank, 0) + 1);
}
}
}
protected int[] generateNumbers(Random random) {
return random
.ints(1, 46)
.limit(6)
.distinct()
.toArray();
}
// 44373/ms 소요
62697ms -> 70337ms -> 44373ms
MK-4 최적화(2)
로또 번호를 맞추는 메소드를 다시 한 번 보겠습니다.
배열의 재사용
ints(1, 46) -> ints(45) + 1
generateNumbers 메소드가 매번 새로운 객체를 반환하는게 마음에 안듭니다.
@Override
protected void innerExecute() {
Random random = new Random();
int[] numbers = new int[6];
boolean[] used = new boolean[46];
for (int i = 0; i < count; i++) {
generateNumbers(random, numbers, used);
int rank = evaluate(numbers);
if (rank < 6) {
ranking.put(rank, ranking.getOrDefault(rank, 0) + 1);
}
}
}
private void generateNumbers(Random random, int[] numbers, boolean[] used) {
Arrays.fill(used, false);
for (int i = 0; i < 6; i++) {
int num;
do {
num = random.nextInt(45) + 1;
} while (used[num]);
used[num] = true;
numbers[i] = num;
}
}int 배열 하나와 중복확인을 위한 boolean 배열 하나를 만들어서 재사용하도록 했습니다.
Arrays.fill(used, false)로 초기화 시켜줍니다.
근데 Arrays.fill(used, false) 도 마음에 안듭니다. 한번 초기화할때마다 46칸짜리 배열을 돌아야합니다. 사용된 곳만 초기화하고싶습니다.
private void generateNumbers(Random random, int[] numbers, boolean[] used) {
// Arrays.fill(used, false);
for (int i = 0; i < 6; i++) {
int num;
do {
num = random.nextInt(45) + 1;
} while (used[num]);
used[num] = true;
numbers[i] = num;
}
for (int number : numbers) {
used[number] = false;
}
}
// 16386/ms 소요for 문 해결합니다.
62697ms -> 70337ms -> 44373ms -> 16386ms
MK-5 최적화(3)
로또 번호를 맞추는 메소드를 보겠습니다.
count 비교문 최적화
if (count == 6) { // 다 맞으면 1등
return 1;
}
if (hasBonusNumber) { // 보너스번호 맞으면 +1
count++;
}
return switch (count) {
case 6 -> 2; // 6개 맞으면 2등
case 5 -> 3; // 5개 맞으면 3등
case 4 -> 4; // 4개 맞으면 4등
case 3 -> 5; // 5개 맞으면 5등
default -> 6; // 그 외 6등
};6등이 대부분임에도 불구하고 1등부터 모두 비교하고 있습니다.
6개 -> 2등, 5개 -> 3등 ... 을보면 default를 제외하고 모두 8 - count = rank 가 성립됩니다. 이를 반영해줍시다
if (count < 2) {
return 6;
} else if (count == 6) {
return 1;
} else if (hasBonusNumber) {
count++;
}
return 8 - count;
// 16116/ms 소요
0또는 1개를 맞은사람은 보너스번호를 맞췄다해도 6등입니다. : 6등 반환
6개 모두 맞춘사람은 보너스점수를 비교할 필요가 없습니다. : 1등 반환
보너스점수를 맞췄다면 count를 1 증가시킵니다.
그리고 8 - count를 해줍니다.
62697ms -> 70337ms -> 44373ms -> 16386ms -> 16116ms
전혀 차이가 없네요.
MK-6 최적화(4)
1. 당첨번호 Set -> boolean[] 변경
2. 등수 Map -> int[] 변경
수백번도 아니고 1억번 이상의 반복문에서 Set의 contains로 매번 확인하는 건 너무 비효율적이라는 생각이 들었습니다. boolean[] 으로 확인하도록 해봅니다.
private final boolean[] targetNumbers = new boolean[46];
private final int bonusNumber;
private final Map<Integer, Integer> ranking = new HashMap<>();
public LotterySimulatorMK6(int count, int[] targetNumbers, int bonusNumber) {
super(count);
for (int target : targetNumbers) {
this.targetNumbers[target] = true;
}
this.bonusNumber = bonusNumber;
}Set에서 boolean[] 으로 변경하고 targetNumbers에 존재하는 위치만 true로 변경해줍니다.
for (int number : numbers) {
if (targetNumbers[number]) {
count++;
} else if (number == bonusNumber) {
hasBonusNumber = true;
}
}evaluate 메소드에서 targetNumbers[number] 로 변경해줍니다.
등수를 표현하는 ranking의 타입도 Map에서 int[] 로 변경해줍니다.
private final int[] ranking = new int[6];
@Override
protected void innerExecute() {
Random random = new Random();
int[] numbers = new int[6];
boolean[] used = new boolean[46];
for (int i = 0; i < count; i++) {
generateNumbers(random, numbers, used);
int rank = evaluate(numbers);
if (rank < 6) {
// ranking.put(rank, ranking.getOrDefault(rank, 0) + 1);
ranking[rank]++;
}
}
}
@Override
public void print() {
for (int i = 1; i < 6; i++) {
System.out.printf("%d등 : %d명\n", i, ranking[i]);
}
}
// 9754/ms 소요
62697ms -> 70337ms -> 44373ms -> 16386ms -> 16116ms -> 9754ms
MK-7 최적화(5) - 비트마스크
당첨번호를 boolean[] -> long으로 바꿔 bit로 관리한다
로또번호는 45개가 최대니 46개의 비트만 있으면 된다. 비트연산으로 처리해보자
private final long TARGET_MASK;
private final int bonusNumber;
private final int[] ranking = new int[6];
public LotterySimulatorMK7(int count, int[] targetNumbers, int bonusNumber) {
super(count);
this.TARGET_MASK = toBitmask(targetNumbers);
this.bonusNumber = bonusNumber;
}
private long toBitmask(int[] numbers) {
long bitmask = 0;
for (int number : numbers) {
bitmask |= 1L << number;
}
return bitmask;
}
private int evaluate(int[] numbers) {
int count = 0;
boolean hasBonusNumber = false;
for (int number : numbers) {
if ((TARGET_MASK & (1L << number)) != 0) {
// if (targetNumbers[number]) {
count++;
} else if (number == bonusNumber) {
hasBonusNumber = true;
}
}
if (count < 2) {
return 6;
} else if (count == 6) {
return 1;
} else if (hasBonusNumber) {
count++;
}
return 8 - count;
}
// 9154/ms 소요
예를들어서 로또 번호는 3개라고 가정하고 {1, 3, 5} 가 당첨번호라고 가정하면
1L << 1 과 1L << 3 과 1L << 5 라고 할 수 있다.
1L은 000...000001이기때문에 왼쪽으로 1칸 시프트는 000...000010이다.
3은 왼쪽으로 3칸 시프트이기 때문에 000...001000 이다
5는 왼쪽으로 5칸 시프트이기 때문에 000...100000 이다
{1, 3, 5} 를 OR 연산하면 000...101010 이다 이를 이용해 내 복권번호를 << 연산으로 계산해서 AND 연산해보면 값을 알 수 있다.
내 로또 번호중에 3을 검증한다고 했을때 101010 & 001000 != 0 이렇게 된다
62697ms -> 70337ms -> 44373ms -> 16386ms -> 16116ms -> 9754ms -> 9154ms
한 번 더 나아가서 generateNumbers 메소드에서 만들어진 로도번호를 비트연산해서 long 타입을 반환받고 TARGET_MASK와 한번에 AND 연산해서 1의 개수를 세면 되는거 아닐까? 한번 해보자
private final long TARGET_MASK;
private final long BONUS_TARGET_MASK;
private final int[] ranking = new int[6];
public LotterySimulatorMK7_BIT(int count, int[] targetNumbers, int bonusNumber) {
super(count);
this.TARGET_MASK = toBitmask(targetNumbers);
this.BONUS_TARGET_MASK = 1L << bonusNumber;
}
@Override
protected void innerExecute() {
Random random = new Random();
for (int i = 0; i < count; i++) {
long bitmask = generateNumbers(random);
int rank = evaluate(bitmask);
if (rank < 6) {
ranking[rank]++;
}
}
}
private long generateNumbers(Random random) {
long bitmask = 0L;
int count = 0;
while (count < 6) {
long bit = 1L << random.nextInt(45) + 1;
if ((bitmask & bit) == 0) {
bitmask |= bit;
count++;
}
}
return bitmask;
}
private int evaluate(long bitmask) {
int matchCount = Long.bitCount(TARGET_MASK & bitmask);
if (matchCount < 2) return 6;
if (matchCount == 6) return 1;
boolean hasBonusNumber = (bitmask & BONUS_TARGET_MASK) != 0;
return hasBonusNumber ? 8 - (matchCount - 1) : matchCount;
}
// 7484/ms 소요당첨번호와 보너스번호 모두 비트연산으로 바꾸었다 evaluate에서 AND 연산으로 일치하는 자리를 카운트해서 연산하도록 변경했다.
62697ms -> 70337ms -> 44373ms -> 16386ms -> 16116ms -> 9754ms -> 9154ms -> 7484ms
MK-8 최적화(6) - ThreadLocalRandom
Random 객체를 ThreadLocalRandom 객체로 변환
@Override
protected void innerExecute() {
Random random = ThreadLocalRandom.current();
for (int i = 0; i < count; i++) {
long bitmask = generateNumbers(random);
int rank = evaluate(bitmask);
if (rank < 6) {
ranking[rank]++;
}
}
}
// 3586/ms 소요
new Random() -> ThreadLocalRandom.current()로 변경한다.
ThreadLocalRandom은 Ramdom의 자식객체이기때문에 구현체만 변경해주면 된다.
왜 이렇게 빨라지는지에 대해서는 다음에 적도록 하겠습니다.
62697ms -> 70337ms -> 44373ms -> 16386ms -> 16116ms -> 9754ms -> 9154ms -> 7484ms -> 3586ms
MK-9 최적화(7) - ThreadPool
Thread를 이용한 병렬계산
앞서만든 로직을 그대로 Thread로 실행시키면 더욱빨라질겁니다.
@Override
protected void innerExecute() {
int availableThreadCount = Runtime.getRuntime().availableProcessors();
int threadLoopCount = count / availableThreadCount;
try (ExecutorService executor = Executors.newFixedThreadPool(threadLoopCount)) {
for (int t = 0; t < availableThreadCount; t++) {
executor.execute(() -> {
Random random = ThreadLocalRandom.current();
for (int i = 0; i < threadLoopCount; i++) {
long bitmask = generateNumbers(random);
int rank = evaluate(bitmask);
if (rank < 6) {
ranking[rank]++;
}
}
});
}
executor.shutdown();
executor.awaitTermination(Long.MAX_VALUE, TimeUnit.MICROSECONDS);
} catch (Exception e) {
e.printStackTrace();
}
}
// 986/ms 소요
62697ms -> 70337ms -> 44373ms -> 16386ms -> 16116ms -> 9754ms -> 9154ms -> 7484ms -> 3586ms -> 986ms
availableThreadCount 는 현재 가능한 스레드의 수
threadLoopCount 는 하나의 스레드가 반복문을 돌아야 되는 수를 나타낸겁니다.
ExecutorService 말고도
ThreadPoolExecutor a = new ThreadPoolExecutor();이런식으로 core size와 max size를 설정하거나 다양한 옵션을 제공하는 Executor도 있지만 여기에선 별로 중요하지 않기 때문에 고정스레드풀을 사용했습니다.
아무래도 cpu의 모든 스레드를 순간적으로 사용하기에 CPU 점유율을 잠깐동안 100%를 차지하지만 뭐 잠깐이니까요.
결론
정말 의식의 흐름대로 복권을 검색했다가 여기까지 해버릴줄 몰랐습니다. 근데 최적화 하면서 나아지는게 보이니까 너무 재밌어서 못 놓겠더라구요.
115,411,832회의 로또 시뮬레이션 최적화 결과는 62.697초 -> 0.986초 로 단축에 성공했습니다.
완벽하지 않으니 언제든지 지적해주시면 감사하겠습니다.
끝으로 비트연산, 스레드, ThreadLocalRandom 에 대해서도 더 알게되어서 좋았습니당.
전체코드 공유
public interface LotterySimulator {
void execute();
void print();
}
public abstract class AbstractFixedCountLotterySimulator implements LotterySimulator {
protected final int count;
protected AbstractFixedCountLotterySimulator(int count) {
this.count = count;
}
abstract protected void innerExecute();
@Override
public final void execute() {
Times.timer(this::innerExecute);
}
}
public class Times {
public static void timer(Runnable runnable) {
long start = System.currentTimeMillis();
runnable.run();
long end = System.currentTimeMillis();
System.out.println(end - start + "/ms 소요");
}
}
public class LotterySimulatorMK9 extends AbstractFixedCountLotterySimulator {
private final long TARGET_MASK;
private final long BONUS_TARGET_MASK;
private final int[] ranking = new int[6];
public LotterySimulatorMK9(int count, int[] targetNumbers, int bonusNumber) {
super(count);
this.TARGET_MASK = toBitmask(targetNumbers);
this.BONUS_TARGET_MASK = 1L << bonusNumber;
}
private long toBitmask(int[] numbers) {
long bitmask = 0;
for (int number : numbers) {
bitmask |= 1L << number;
}
return bitmask;
}
@Override
protected void innerExecute() {
int availableThreadCount = Runtime.getRuntime().availableProcessors();
int threadLoopCount = count / availableThreadCount;
try (ExecutorService executor = Executors.newFixedThreadPool(threadLoopCount)) {
for (int t = 0; t < availableThreadCount; t++) {
executor.execute(() -> {
Random random = ThreadLocalRandom.current();
for (int i = 0; i < threadLoopCount; i++) {
long bitmask = generateNumbers(random);
int rank = evaluate(bitmask);
if (rank < 6) {
ranking[rank]++;
}
}
});
}
executor.shutdown();
executor.awaitTermination(Long.MAX_VALUE, TimeUnit.MICROSECONDS);
} catch (Exception e) {
e.printStackTrace();
}
}
private long generateNumbers(Random random) {
long bitmask = 0L;
int count = 0;
while (count < 6) {
long bit = 1L << random.nextInt(45) + 1;
if ((bitmask & bit) == 0) {
bitmask |= bit;
count++;
}
}
return bitmask;
}
private int evaluate(long bitmask) {
int matchCount = Long.bitCount(TARGET_MASK & bitmask);
if (matchCount < 2) return 6;
if (matchCount == 6) return 1;
boolean hasBonusNumber = (bitmask & BONUS_TARGET_MASK) != 0;
return hasBonusNumber ? 8 - (matchCount + 1) : 8 - matchCount;
}
@Override
public void print() {
for (int i = 1; i < 6; i++) {
System.out.printf("%d등 : %d명\n", i, ranking[i]);
}
}
}
public class Main2 {
public static void main(String[] args) {
int count = 115_411_832;
int[] targetNumbers = {3,7,15,16,19,43};
int bonusNumber = 21;
LotterySimulator simulator = new LotterySimulatorMK9(count, targetNumbers, bonusNumber);
simulator.execute();
simulator.print();
}
}'Language > JAVA' 카테고리의 다른 글
| [JAVA] ThreadLocal에 대해서 알아보자 (2) | 2024.12.13 |
|---|---|
| [Java] Stream - 병렬 스트림 (0) | 2024.11.26 |
| [JAVA] StringTokenizer 에 대해서 (0) | 2024.11.14 |
| [JAVA] Record와 Sealed (1) | 2024.11.13 |
| [JAVA] 상속(Inheritance)과 복합(Composition) (1) | 2024.11.12 |
