[스프링부트] 인기 검색어 순위 변동 계산

상황

인기 검색어의 순위 변동 상황도 보여주기 위해서 한시간 전 인기 검색어 순위와 현재 인기 검색어 순위를 추출

비교하기로 하였다.

 

이때 하나의 키워드와 인기 검색어 점수를 가지고 있는 SearchPopularResponse의 리스트를 비교해야하는데,

두개의 리스트를 계산하게 되면 O(n^2)의 시간복잡도가 발생하게 된다.

 

현재는 10개의 랭킹만 사용하기 때문에 10^2의 연산이 발생하여 부담스럽지 않지만,

100개의 랭킹을 보여준다고 하면, 10000번의 연산을 진행해야 한다는 점에서 매우 비효율적이라고 판단하였다.

따라서 이 부분을 튜닝하기로 하였다.

@Getter
@Setter
@NoArgsConstructor
@AllArgsConstructor
@Builder
public class SearchPopularResponse {
    private double score;

    private String keyword;
}

List<SearchPopularResponse> nowSearchPopularResponse=getPopularKeywordsByMilliSeconds(now);
List<SearchPopularResponse> oneHourAgoSearchPopularResponse=getPopularKeywordsByMilliSeconds(oneHourAgo);

방법

두 리스트의 랭킹을 비교하는 방식은 다음과 같다.

1. 현재 시간의 랭킹 리스트를 기준으로 잡는다.
2. 중첩 반복문을 돌면서 현재 시간 리스트의 keyword와 같은 다른 리스트의 키워드를 찾는다.
3. 같은 경우에 리스트의 Index의 차이를 비교, 랭킹의 상승, 하락, 새로운 등장 (현재 리스트를 기준으로 판단하기 때문에 낙오는 고려할 필요가 없다.)을 판단한다.

이 방법을 해결하기 위해 고민하던 중. keyword를 찾는 것이 목표이기 때문에, keyword를 key값으로 사용하기 위해 Map을 사용하기로 하였다.

 

List 즉 배열은 key값이 나열된 정수이지만, Map은 Key값을 문자열로 지정할 수 있다.

따라서 keyword를 찾는데, O(1)의 시간 복잡도만 발생한다.

즉 O(1)에 현재 시간 랭킹 리스트를 순회하는 시간 복잡도O(n)이 발생하게 되어, 총 O(n)의 시간복잡도로 최적화할 수 있다.

구현

리스트의 인덱스에 대해서 IntStream을 통하여 순회하였다.

자바 collector를 사용하기 위해서는 레퍼런스 타입이여야 하기 때문에, int 타입을 boxed함수를 통해 Integer로 변환시켰다.

Collectors의 toMap함수를 통해 KeyMapper 함수, KeyValue함수를 인자로 넣어 랭킹 리스트를 Map형태로 변환하였다.

List<SearchPopularResponse> nowSearchPopularResponse=getPopularKeywordsByMilliSeconds(now);
List<SearchPopularResponse> oneHourAgoSearchPopularResponse=getPopularKeywordsByMilliSeconds(oneHourAgo);

Map<String, Integer> pastPopularMap = IntStream.range(0, oneHourAgoSearchPopularResponse.size())
        .boxed()
        .collect(Collectors.toMap(
                index -> oneHourAgoSearchPopularResponse.get(index).getKeyword(),
                index -> index + 1
        ));

그리고 아래와 같이 과거 검색어 순위를 나타내는 Map과 List의 순위 차를 구해서 랭킹 변화량을 저장하게 되었다.

List<SearchPopularDocument> documents = IntStream.range(0, nowSearchPopularResponse.size())
                    .mapToObj(index -> {
                        String keyword = nowSearchPopularResponse.get(index).getKeyword();
                        int currentRank = index + 1;

                        // 과거에 없는 경우 new
                        int pastRank = pastPopularMap.getOrDefault(keyword, -1);
                        boolean isNewKeyword = pastRank == -1;

                        int changeRank =  pastRank-currentRank; // 양수: 순위 상승 음수: 순위 하락

                        log.info("과거 랭킹: {}, 현재 랭킹: {}, 랭킹 차이: {}", pastRank, currentRank, changeRank);

                        return SearchPopularDocument.builder()
                            .rank(index + 1)
                            .keyword(nowSearchPopularResponse.get(index).getKeyword())
                            .updatedAt(instantNow)
                            .rankChange(changeRank)
                            .isNewKeyword(isNewKeyword)
                            .build()
                            ;
                    })
                    .toList();

아래는 저장된 데이터를 조회한 엘라스틱 서치 쿼리의 일부이다.

한시간 전과 현재의 검색어 순위가 일치하기 때문에, rank_change가 0으로 출력된 것을 볼 수 있다.

"hits" : [
      {
        "_index" : "search_popular",
        "_id" : "vQ3mjpUBJB7oeKkU01lU",
        "_score" : null,
        "_source" : {
          "_class" : "com.medeasy.domain.search.db.SearchPopularDocument",
          "rank" : 1,
          "keyword" : "타이레놀",
          "updatedAt" : "2025-03-13T09:47:26.910Z",
          "rankChange" : 0,
          "isNewKeyword" : false
        },
        "sort" : [
          1741859246910,
          1
        ]
      },

 

인기 검색어 구현의 일부분을 작성하였다. 

총 구현 방법은 추후 포스팅을 남길 예정이다.