DB 안 씀.

모든 데이터는 램에 올려놓고 사용한다.


각 만화의 정보가 저장되어있음. id로 구분함.

예시: { id: 123456, title: "Lorem ipsum", tags: ["A", "B", "C"] }


위의 정보를 토대로 태그별로 목록을 뽑아놓은 인덱스가 있음. 내림차순으로 정렬되어있다.

예시: { "A": [ 1234, 123, 12, 1 ], "B": [ 123, 21, 1 ] }


처리해야 하는 건 다음과 같음.

쿼리 ["A", "B"]가 들어왔을 경우, "A"와 "B"라는 태그를 모두 가지고 있는 만화의 목록을 반환해야 함.

위의 경우에는 [ 123, 1 ]을 반환해야 함.


현재 방식은 아래와 같음.

우선 태그를 만화의 개수를 기준으로 오름차순으로 정렬함.

(["A", "B"]는 A 태그를 가진 만화가 4개, B 태그를 가진 만화는 3개이므로, ["B", "A"]가 됨.)


그리고, 둘의 교집합을 구함. 정렬되어있는 두 목록의 교집합은 O(|A|+|B|)만에 구할 수 있으므로,

최종 수행시간은 각 태그를 가진 만화의 개수의 합에 비례한다는 것을 알 수 있음.


매우 단순한(무식한?) 방식이지만, 여기다 캐시도 달고 적당히 최적화도 해주면 생각보다 빠르게 돌아감.

근데 여기다가 제외 쿼리.. 그러니까 "A -B"처럼 A는 포함하고 B는 제외하는 방식의 쿼리도 비슷하게 구현하면

최악의 경우 시간이 좀 오래 걸림.


열심히 검색해서 이런 것도 읽어봤는데 내 상황에 맞는 건 아닌 것 같음.

몬가 성능을 크게 개선시킬만한 알고리즘이나 최적화 기법이 없을까..