1. 오늘 발견한 문제

MarketService.updateMarketItemList() 메소드를 보다가 뭔가 이상한 걸 발견했다.

for (Market market : newMarketList) {           // O(n)
    Optional<Market> find = oldList.stream()
            .filter(item -> item.getLostarkMarketId() == market.getLostarkMarketId())
            .findFirst();                        // O(m) 😱
    // ...
}

for문 안에서 stream으로 또 순회하고 있었다. 전형적인 O(n²) 패턴이다.

데이터가 1,000개면 1,000 × 1,000 = 1,000,000번 비교하는 거다. 지금은 괜찮을 수 있지만, 데이터가 늘어나면 문제가 될 수 있다.



2. 해결 방법

핵심은 List를 Map으로 변환해서 조회를 O(1)로 만드는 것이다.

Before (O(n²))

for (Market market : newMarketList) {
    Optional<Market> find = oldList.stream()
            .filter(item -> item.getLostarkMarketId() == market.getLostarkMarketId())
            .findFirst();  // 매번 전체 순회
    // ...
}

After (O(n))

// Map으로 변환 (O(n))
Map<Long, Market> existingMap = oldList.stream()
        .collect(Collectors.toMap(Market::getLostarkMarketId, Function.identity()));

// Map에서 조회 (O(1))
Market existing = existingMap.get(market.getLostarkMarketId());



3. partitioningBy 처음 써봤다

리팩토링하면서 Collectors.partitioningBy()를 처음 써봤는데, 꽤 유용했다.

partitioningBy란?

조건에 따라 데이터를 true/false 두 그룹으로 분류해주는 Collector다.

Map<Boolean, List<Market>> partitioned = newMarketList.stream()
        .collect(Collectors.partitioningBy(m -> existingMap.containsKey(m.getLostarkMarketId())));

List<Market> toUpdate = partitioned.get(true);   // 기존에 있는 것들 (업데이트 대상)
List<Market> toInsert = partitioned.get(false);  // 기존에 없는 것들 (신규 저장 대상)

groupingBy와 차이점

구분 partitioningBy groupingBy
분류 기준 boolean (true/false) 임의의 키
결과 항상 2개 그룹 N개 그룹
빈 그룹 빈 리스트로 존재 키 자체가 없음

partitioningBy는 조건에 맞는 게 없어도 빈 리스트를 반환해서 NPE 걱정이 없다.

예시

List<Integer> numbers = List.of(1, 2, 3, 4, 5, 6);

Map<Boolean, List<Integer>> result = numbers.stream()
        .collect(Collectors.partitioningBy(n -> n % 2 == 0));

// result.get(true)  → [2, 4, 6]  (짝수)
// result.get(false) → [1, 3, 5]  (홀수)



4. Five Lines of Code? 해봤는데 별로였다

리팩토링 중에 "Five Lines of Code"라는 원칙을 적용해봤다. 메소드를 5줄 이하로 유지하자는 원칙인데...

시도해본 코드

public void updateMarketItemList(List<Market> newMarketList, int categoryCode) {
    exception(newMarketList);
    Map<Long, Market> existingMap = getExistingMarketMap(categoryCode);
    Map<Boolean, List<Market>> partitioned = partitionByExistence(newMarketList, existingMap);
    updateExistingMarkets(partitioned.get(true), existingMap);
    saveNewMarkets(partitioned.get(false));
}

private Map<Long, Market> getExistingMarketMap(int categoryCode) { ... }
private Map<Boolean, List<Market>> partitionByExistence(...) { ... }
private void updateExistingMarkets(...) { ... }
private void saveNewMarkets(...) { ... }

메인 메소드는 5줄이 됐다. 근데...

솔직한 느낌: 오히려 복잡하다

별로였다. 이유는:

  1. 코드 점프가 많아짐 - 흐름 파악하려면 메소드 4개를 왔다갔다해야 함
  2. 원래 12줄짜리 코드였음 - 한눈에 보이던 게 쪼개지니까 더 파악이 어려움
  3. 메소드 이름 짓느라 시간 소모 - partitionByExistence가 맞나? splitByExistence가 맞나?
  4. private 메소드만 4개 추가 - 한 곳에서만 쓰는 로직인데 굳이?

롤백했다

결국 원래대로 돌렸다. 주석만 잘 달아두면 12줄짜리 코드가 훨씬 읽기 좋았다.

// 기존 데이터를 Map으로 변환하여 O(1) 조회 가능하게 함
Map<Long, Market> existingMap = ...

// 기존 존재 여부에 따라 분류 (true: 업데이트 대상, false: 신규 저장 대상)
Map<Boolean, List<Market>> partitioned = ...

// 기존 데이터 업데이트
partitioned.get(true).forEach(...)

// 신규 데이터 일괄 저장
marketRepository.saveAll(partitioned.get(false));

언제 쓰면 좋을까?

Five Lines of Code가 유용한 경우:

  • 복잡한 비즈니스 로직이 50줄 이상일 때
  • 분리한 메소드를 다른 곳에서도 재사용할 때
  • 각 단계를 개별적으로 테스트해야 할 때

단순한 로직에는 과한 원칙이다. 규칙을 위한 규칙이 되면 안 된다.



5. 최종 코드

/**
 * 거래소 데이터 업데이트 메소드
 * - Map을 활용하여 O(n) 시간복잡도로 처리
 * - partitioningBy로 업데이트/신규 대상 분류
 * - saveAll로 신규 데이터 일괄 저장
 */
@Transactional
public void updateMarketItemList(List<Market> newMarketList, int categoryCode) {
    exception(newMarketList);

    // 기존 데이터를 Map으로 변환하여 O(1) 조회 가능하게 함
    Map<Long, Market> existingMap = marketRepository.findAllByCategoryCode(categoryCode)
            .stream()
            .collect(Collectors.toMap(Market::getLostarkMarketId, Function.identity()));

    // 기존 존재 여부에 따라 분류 (true: 업데이트 대상, false: 신규 저장 대상)
    Map<Boolean, List<Market>> partitioned = newMarketList.stream()
            .collect(Collectors.partitioningBy(m -> existingMap.containsKey(m.getLostarkMarketId())));

    // 기존 데이터 업데이트
    partitioned.get(true).forEach(m -> existingMap.get(m.getLostarkMarketId()).changeData(m));

    // 신규 데이터 일괄 저장
    marketRepository.saveAll(partitioned.get(false));

    log.info("✅ 업데이트: {}, 추가: {}", partitioned.get(true).size(), partitioned.get(false).size());
}



6. 성능 테스트

정말 빨라졌는지 테스트 코드를 작성해서 확인해봤다.

테스트 코드

@Test
@DisplayName("O(n²) vs O(n) 성능 비교 - 10,000개 아이템")
void comparePerformance_10000Items() {
    int itemCount = 10_000;
    List<Market> oldList = createMarketList(itemCount, 0);
    List<Market> newList = createMarketList(itemCount, 0);

    // 기존 O(n²) 버전
    long startV1 = System.nanoTime();
    for (Market market : newList) {
        Optional<Market> find = oldList.stream()
                .filter(item -> item.getLostarkMarketId() == market.getLostarkMarketId())
                .findFirst();
        find.ifPresent(existing -> existing.changeData(market));
    }
    long durationV1 = (System.nanoTime() - startV1) / 1_000_000;

    // 개선된 O(n) 버전
    long startV2 = System.nanoTime();
    Map<Long, Market> oldMap = oldList.stream()
            .collect(Collectors.toMap(Market::getLostarkMarketId, Function.identity()));
    for (Market market : newList) {
        Market existing = oldMap.get(market.getLostarkMarketId());
        if (existing != null) {
            existing.changeData(market);
        }
    }
    long durationV2 = (System.nanoTime() - startV2) / 1_000_000;

    System.out.println("O(n²) 버전: " + durationV1 + "ms");
    System.out.println("O(n)  버전: " + durationV2 + "ms");
}

테스트 결과

========================================
아이템 개수: 1000
----------------------------------------
O(n²) 버전: 7ms
O(n)  버전: 1ms
----------------------------------------
성능 향상: 7배
========================================

========================================
아이템 개수: 5000
----------------------------------------
O(n²) 버전: 62ms
O(n)  버전: 0ms
----------------------------------------
성능 향상: O(n) 버전이 1ms 미만으로 완료
========================================

========================================
아이템 개수: 10000
----------------------------------------
O(n²) 버전: 199ms
O(n)  버전: 1ms
----------------------------------------
성능 향상: 199배
========================================

10,000개 기준으로 199배 빨라졌다. 이론대로 데이터가 많아질수록 차이가 극적으로 벌어진다.



7. 정리

항목 Before After
시간복잡도 O(n²) O(n)
10,000개 처리 199ms 1ms
DB 저장 개별 save() saveAll()
코드 가독성 if-else 분기 partitioningBy로 분류

배운 점

  1. List에서 반복 조회가 필요하면 Map으로 변환하자
  2. partitioningBy는 true/false 두 그룹으로 나눌 때 유용하다
  3. 성능 개선은 테스트 코드로 증명하자
  4. Five Lines of Code는 만능이 아니다 - 단순한 로직에는 오히려 복잡해진다



저작자표시 (새창열림)

티스토리툴바