(Spring) 취향 기반 향수 추천 서비스 - 11. 성능 개선기

향수 위시리스트에 대한 테스트코드를 작성 중에 개선해야할 것이 보였다.
WishList객체 내의 Perfume들중 이름이 똑같은 항목만을 추출하여 Counting하는 로직이었다. 당시 전시 일정때문에 빠른 시간 내에 개발해야해서 급하게 하느라 그랬던 것 같다.

기존 코드

private Long countWishListObjects(List<WishList> wishLists, int index) {
        return wishLists.stream()
                .filter(perfume -> getPerfumeName(perfume).matches(wishLists.get(index).getPerfume().getPerfumeName()))
                .count();
    }
 
    private List<RankingResponse> makeCountedWishList() {
        List<WishList> wishLists = findAllWishList();
        List<RankingResponse> rankingResponses = new ArrayList<>();

        for (int i = 0; i < wishLists.size(); i++) {
            long count = countWishListObjects(wishLists, i);

            RankingResponse rankingResponse = RankingResponse.makeRankingResponseObject(wishLists.get(i).getPerfume(), count);
            rankingResponses.add(rankingResponse);
        }
        return rankingResponses;
    }

문제점은 다음과 같습니다.
countWishListObjects내에서 WishLists를 순회하며 같은 항목을 찾는데 makeCountedWishList 메서드 내에서도 for문을 통해 총 WishList 두번을 순회하는 것입니다.
즉 외부 루프와 내부 메서드에서 순회를 중첩하기 때문이었습니다..
우리 서비스의 규모상 성능에 영향을 주지 못하는 수준이지만 그래도 성능상 개선, 가독성의 이유로 개선을 했습니다.

public List<RankingResponse> makeCountedWishList() {
        List<WishList> wishLists = findAllWishList();
        List<RankingResponse> rankingResponses = new ArrayList<>();

        Map<String, Long> countedWishLists = countWishListObjects(wishLists);

        for (WishList wishList : wishLists) {
            long count = countedWishLists.getOrDefault(wishList.getPerfume().getPerfumeName(), 0l);
            RankingResponse rankingResponse = RankingResponse.makeRankingResponseObject(wishList.getPerfume(), count);
            rankingResponses.add(rankingResponse);
        }
        return rankingResponses;
    }
    
private Map<String, Long> countWishListObjects(List<WishList> wishLists) {
        return wishLists.stream()
                .collect(Collectors.groupingBy(
                        wishList -> wishList.getPerfume().getPerfumeName(), Collectors.counting()
                ));
    }

개선 점은 다음과 같습니다.
1. countWishList~메서드에서 리스트를 한번만 순회한 후에 각각의 Perfume이름과 몇개의 항목이 있는지 Map에 저장합니다 -> O(n)
2. makeCountedWishList메더스에 for문은 이미 계산된 맵 내에서 Count값을 가져옵니다. -> O(n)
이 두 과정을 합쳐 결국 시간복잡도는 O(n)이 됩니다.

확장성 측면에서도 문제가 있었습니다.
countWishList 메서드는 wishLists와 index 두가지의 인자를 받아서 내부에서 처리합니다. 메서드가 여러가지 일을 하고 있었고 불 필요한 매개변수로 인해 추후의 확장에 있어 불편함을 겪을 수 있습니다.

다음 개선입니다.

    public Long countElement(List<String> elementList, int i) {
        return elementList.stream().filter(x -> elementList.get(i).matches(x)).count();
    }

    public AnalyzeResponse countPerfumeList(List<String> elementList) {
        Long maxCount = 0L;
        String elementName = "";
        int perfumeNameListSize = elementList.size();

        for (int i = 0; i < perfumeNameListSize; i++) {
            Long count = countElement(elementList, i);
            if (count > maxCount) {
                elementName = elementList.get(i);
                maxCount = count;
            }
        }
        isCountingNumberExist(maxCount);

        return AnalyzeResponse.builder()
                .elementName(elementName)
                .count(maxCount)
                .build();
    }

해당 코드도 문제점이 있었습니다.
countElement()에서 이미 Stream으로 순회를 하는데, 다음 countPerfumeList에서 또 한번 순회를 거치면서 시간복잡도가 O(N^2)이 되어버렸습니다..
따라서 이를 Map에 담아 한번만 순회할 수 있도록 수정하였습니다.

    public Map<String, Long> countElement(List<String> elementList) {
        Map<String, Long> elementCountMap = new HashMap<>();

        for (String element : elementList) {
            elementCountMap.put(element, elementCountMap.getOrDefault(element, 0L) + 1);
        }
        return elementCountMap;
    }

    public AnalyzeResponse countPerfumeList(List<String> elementList) {
        Long maxCount = 0L;
        String elementName = "";

        Map<String, Long> elementCountMap = countElement(elementList);

        for (Map.Entry<String, Long> entry : elementCountMap.entrySet()) {
            if (entry.getValue() > maxCount) {
                elementName = entry.getKey();
                maxCount = entry.getValue();
            }
        }
        isCountingNumberExist(maxCount);

        return new AnalyzeResponse(elementName, maxCount);
    }
}