BFS로 서비스 스펙 나름 재밌게 친 썰

업무로 프리미엄 컨텐츠 허브 서버개발을 진행하며, 작은 스펙이지만 기억에 남았던 내용이 있어서 가볍게 공유 드리고자 합니다.
mongodb를 사용하고 있기에 이전 글/다음 글은 아래 용어와 동일하게 이해해주시면 됩니다.

 

• 이전 글 == lte(less than equal), lt(less than)
• 다음 글 == gte(greater than equal), gt(greator than)

스펙 설명

• 컨텐츠 엔드

아래 사진처럼 각 컨텐츠 엔드 하단에는 동일 카테고리의 컨텐츠 목록을 노출하는 영역이 존재하구요. 

노출 세부 스펙은 아래와 같습니다.

 

• 현재 컨텐츠는 가운데로 두고 앞(다음 글) 뒤(이전 글)의 컨텐츠 노출
• 총 N개 노출
  • e.g.) 5개 노출인 경우 -> 다음 글 2개 / 현재 컨텐츠 / 이전 글 2개

단순 접근

총 N개 노출이므로, 단순하게 아래처럼 데이터를 추출한 뒤 순서대로 append 해서 내려주고 싶습니다.

 

• 다음 글 N/2개
• 현재 컨텐츠
• 이전 글 N/2개

간편합니다, 하지만 이런 방법으로 접근 시 아래 케이스를 커버하지 못합니다.

 

• 현재 컨텐츠가 최신글이라 다음 글이 없는 경우 (gt가 없는 경우)
• 현재 컨텐츠가 가장 마지막글이라 이전 글이 없는 경우 (lt 가 없는 경우)
• 다음 글 개수가 N/2 보다 적고, 이전 글 개수는 더 많은 경우 (gt 개수는 적고 / lt가 많은 경우)
• 이전 글 개수가 N/2 보다 적고, 다음 글 개수가 더 많은 경우 (lt 개수는 적고 / gt는 많은 경우)

이런식의 진행은 분기가 들어가고 약간 복잡해질 것 같습니다.

또한 항상 N개를 채워서 내려주어야 합니다. (컨텐츠가 N개 이하로 존재하는 경우는 제외)

 

이전 글 / 다음 글을 N개씩 가져와서 풀어줄 필요가 있어 보입니다. (aggregation은 지양하고 있습니다.)

BFS(너비우선탐색)

이제 개발자들의 국민? 그래프 알고리즘인 BFS를 적용시켜 볼 차례입니다. 순서는 아래와 같습니다.

 

• 다음 글(gte) N개, 이전 글(lte) N개 가져옴. (gte, lte 옵션이므로 중복 원소 1개 존재 / 중복 원소가 현재 컨텐츠)
• reduce.
• 현재 컨텐츠를 기준으로 bfs 탐색
• N에 도달한 경우 탐색 중지

아래는 그림은 N이 5이고, 이전 글/다음 글 개수가 균등하게 존재하는 경우를 설명합니다.

 

• 그래프는 단순 방향 그래프로 나타낼 수 있습니다.
• Pivot은 현재 글을 나타냅니다.

다음은 N이 5이고, 존재하는 다음 글 개수가 적은 경우를 설명합니다.

이처럼 처리하니 여러 상황에 대해 유연하게 대응 가능하게 되는 장점이 있습니다.

 

• 이전 글 / 다음 글 개수가 균등하게 존재하지 않는 경우
• 서비스 스펙이 변해 N이 동적으로 변하는 경우

실제 사용

서비스 메소드 접기/펼치기

   public Mono<ContentsResponse> getPrevAndNextContentsOnSameCategory(String contentId, int limit) {
        Mono<ContentDataQueryParams> content = contentsRepository.getContentById(contentId)
                ...
                .cache();

        Flux<Content> nextContents = content.flatMapMany(c -> contentsRepository.getNextContents(c,.. );
        Flux<Content> previousContents = content.flatMapMany(c -> contentsRepository.getPreviousContents(c, ..);

        return Flux.mergeSequential(nextContents, previousContents)
                .reduce(new ArrayList<>(), new Reducer<Content>().listReducer)
                .flatMapIterable(reduced -> {
                    ContentsBfsExpander contentsSearcher = new ContentsBfsExpander(reduced, contentId, limit);
                    return contentsSearcher.searchBothSides();
                })
                .collectList()
                .map(c -> ContentsResponse.builder()
                        .contents(c)
                        .build()
                );
    }

 

ContentsBfsExpander 접기/펼치기 버튼

public class ContentsBfsExpander {
    private List<Content> contents;
    private String contentId;
    private int limit;
    private int [] dx = {-1, 1};
    private boolean[] visited = null;

    @Builder
    public ContentsBfsExpander(List<Content> contents, String contentId, int limit) {
        this.contents = contents;
        this.contentId = contentId;
        this.limit = limit;
        this.visited = new boolean[limit * 2];
    }

    @Getter
    @AllArgsConstructor
    static class SearchTarget {
        Integer pivot;
        List<Content> distinctContents;

        public boolean isValid() {
            return pivot != null && !CollectionUtils.isEmpty(distinctContents);
        }
    }

    /**
     * SearchTarget 의 pivot element 를 기준으로 좌/우 원소를 차례대로 추출한다. (left -> right 순 탐색)
     * @return LinkedList<Contents>
     */
    public LinkedList<Content> searchBothSides() {
        SearchTarget target = this.target();
        if (target == null || !target.isValid()) {
            log.warn("{} search target contains nothing", this.contentId);
            return new LinkedList<>();
        }

        int pivot = target.getPivot();

        List<Content> contents = target.getDistinctContents();
        LinkedList<Pair<Integer, Content>> queue = new LinkedList<>();
        queue.add(Pair.of(pivot, contents.get(pivot)));

        this.visited[pivot] = true;

        LinkedList<Content> result = new LinkedList<>();
        result.add(contents.get(pivot));

        while (!queue.isEmpty()) {
            Pair<Integer, Content> content = queue.poll();
            pivot = content.getLeft();

            for (int index = 0; index < this.dx.length; ++ index) {
                int nx = pivot + this.dx[index];

                if (nx < 0 || nx >= contents.size()) {
                    continue;
                }

                if (result.size() == this.limit || result.size() == contents.size()) {
                    break;
                }

                if (index == 0 && !this.visited[nx]) {
                    result.addFirst(contents.get(nx));
                }

                if (index == 1 && !this.visited[nx]) {
                    result.addLast(contents.get(nx));
                }

                queue.offer(Pair.of(nx, contents.get(nx)));
                this.visited[nx] = true;
            }
        }
        return result;
    }

    private SearchTarget target() {
        if (CollectionUtils.isEmpty(this.contents)) {
            log.warn("{} no contents for remove duplicates", this.contentId);
            return new SearchTarget(null, null);
        }

        SearchTarget target = null;
        int prevIndex = 0;

        for (int index = 1; index < this.contents.size(); index ++) {
            Content prev = this.contents.get(prevIndex);
            Content now = this.contents.get(index);

            if (prev.get_id().equals(now.get_id()) && prev.get_id().equals(this.contentId)) {
                this.contents.remove(index);
                target = new SearchTarget(prevIndex, this.contents);
                break;
            }
            prevIndex = index;
        }

        return target;
    }
}

 

아직까지는 위 처럼 bfs 탐색용 클래스를 따로 만들어서 사용 중에 있습니다.

 

Flux.expand()로도 대체하면 코드 양을 대폭 줄일 수는 있습니다만, 유지하고 있던 이유는 작성된 bfs로직이 가장 흔하게 사용되는 패턴이기 때문입니다. 이제는 변경 해야하지 않을까 싶습니다 (구글링 혹은 알고리즘 문제 풀때 가장 많이 볼 수 있는 유형..?)

 

작은 스펙에 간단한 알고리즘을 적용한것이지만, 나름 기억에 남는 스펙이 된 것 같네요ㅎㅎ

감사합니다.

 

글은 21년 작성되었고, 좀 더 최근 내용은 아래에서 확인하실 수 있습니다. (8분 20초)
https://tv.naver.com/v/23652646/list/753227