ps:병렬_이분_탐색
병렬 이분 탐색 (Parallel Binary Search; PBS)
- 일단 참고자료는
- 이하는 PBS의 동작방법 자체보다는.. 다른 테크닉들과 어떤식으로 다른지 내가 공부하면서 느낀 방식대로 정리한것.
- 우선 이름에 이분탐색이 들어가긴 하지만, 이분탐색의 변형..이라는 느낌보다는 오프라인 쿼리 테크닉의 일종으로 생각하자
- 문제 형태는 '조건이 처음 만족하는 시점' 을 찾는데, 이것을 여러개의 조건들(=쿼리들)에 대해서 처리해야 하는 문제이다
- 당연히 그 시점 이후로는 계속 조건이 만족되어야 한다. 이분탐색 필이 나긴 한다.
- 먼저 이걸 기본적인 이분탐색을 써서 푸는 상황을 생각해보자. t시점에서 조건이 맞는지 여부를 체크하는 것을 Y의 시간복잡도로 처리할 수 있는 경우이다. 그러면 시간 범위가 T까지라고 했을때, 조건이 맞는지를 O(logT)개의 시점에 대해서 체크해서 O(YlogT)에 하나의 쿼리를 처리할수 있다.
- 그리고 쿼리가 Q개인 문제를 각각의 쿼리에 대해서 이렇게 푼다면 총 O(QYlogT)의 시간이 걸린다.
- 하지만 만약에 t시점에서 조건이 맞는지를 바로 확인할 수가 없다면?
- t시점에서의 조건 충족 여부를 확인하기 위해서는 처음 시점부터 t시점까지 일종의 시뮬레이션을 돌려서 상태를 순서대로 업데이트해야만 가능하다고 하자. 그리고 이때 시뮬레이션을 한 스텝 돌리는 것은 X의 시간복잡도가 걸린다고 생각하자. t시점에서 조건이 맞는지를 체크하기 위해서는 t스텝의 시뮬레이션을 돌려야 하므로 O(X*t + Y) 가 걸린다고 할수 있다. 만약에 이걸 이용해서 이분탐색을 하면 이걸 O(logT)번 해야 하므로, O(logT*(X*T+Y))가 걸릴것이다. 하지만 이 경우에는 굳이 이분탐색을 할 필요가 없다. 이럴바에는 그냥 시뮬레이션을 한번 처음부터 끝까지 돌리면서, 매 스텝마다 조건을 체크해서 조건이 만족하는 순간 멈추면 그만이다. 그러면 O(T*(X+Y))가 될것이고, 한개의 쿼리만을 처리한다면 이게 가장 좋은 방법이다.
- 이제 그러면 여기에 쿼리가 여러개라는 조건이 추가된다면??
- 가장 나이브하게 위에서 말한 시뮬레이션을 첨부터 끝까지 돌리는 방법을 Q개에 쿼리에 대해서 각각 반복하면 O(Q*T*(X+Y)) 이 될 것이다
- 좀더 좋은 방법은 없을까..
- 만약에, 시뮬레이션을 한번 끝까지 돌리면서 중간 단계 결과들을 어떤 좋은 자료구조에 잘 저장해둬서, 이후에 쿼리들을 빠르게 처리할 수 있게 만들 수 있다면 가장 베스트이다.
- 자료구조를 활용해서 어떤 조건을 만족하는 최초 시점을 Z의 시간복잡도로 구할수 있게 된다면 O(X'*T)로 시뮬레이션을 돌리면서 중간 결과를 저장해두고, O(Z*Q)로 쿼리를 해결하면 된다. 총 O(X'*T + Z*Q). 매우 훌륭하다.
- (X' 는 시뮬레이션을 한스텝 돌리고, 중간결과를 저장하는데까지 걸리는 시간복잡도이다)
- '조건을 만족하는 처음 시점'을 빠르게 구할수 있게 만들지 못하더라도, 특정 시점에서 '조건을 만족하는지 여부'를 빠르게 구할수 있게 할수 있다면 이분탐색을 쓸수 있다. Persistent data structure 같은 느낌이다.
- O(X'*T)로 시뮬레이션을 돌리면서 중간 결과를 저장해두고, O(Z'*logT*Q)의 이분탐색으로 쿼리를 해결하면 된다.
- 하지만 저런 좋은 자료구조가 항상 있는게 아니니.. 다른 방법을 생각해보자. 만약 오프라인 쿼리가 가능한 경우라면?
- 만약 어떤 시점에서, 이 시점에 처음으로 조건이 충족된 쿼리들을 바로 추출할수 있다면, 상황은 매우 간단하다.
- 시뮬레이션을 한스텝 돌릴때마다, 조건이 충족된 쿼리들에 대해서 현재 시점을 답으로 기록하면 된다. 지금 조건이 만족되는 쿼리 한개를 W에 찾을수 있다고 한다면 O(X*T+W*Q)면 해결된다..
- 하지만 그게 아니라면 시뮬레이션을 한스텝 돌릴때마다, 모든 쿼리들에 대해서 조건이 만족하는지를 확인해야 한다.
- 이것은 O(T*(X+Q*Y))인데.. 맨 처음에 언급한 가장 무식한 방법인 O(Q*T*(X+Y)) 보다는 낫긴 하지만, 보통은 이미 Q*T에서 계산 가능한 시간 범위를 초과하게 될것이다.
- 자.. 그럼 이방법도 안되고 저방법도 안되는 상황.. 중간결과를 효과적으로 저장할 방법도 안떠오르고, 오프라인 쿼리는 가능하긴 하지만 조건이 충족된 쿼리들을 빠르게 찾아낼수 있는 방법도 안떠오를때.. 그냥 기계적으로 적용할수 있는 방법이 병렬이분탐색이다..
- 맨 처음에 말했듯이, 쿼리 하나를 이분탐색으로 해결하려면 시뮬레이션을 O(logT)번 돌려야 하므로 O(logT*(T*X+Y))이다. 이것을 Q개의 쿼리로 확장할때에도 쿼리들을 모아서 오프라인으로 처리하면 여전히 O(logT)번의 시뮬레이션으로 가능하다. 그러면 시간복잡도를 O(logT*(T*X +Q*Y))로 제한시킬수가 있다!
- 시뮬레이션을 한스텝 돌릴때마다 모든 쿼리들에 대해서 조건을 체크하는 O((X+Q*Y)*T)와 비교하자. X연산을 T번 하던것을 TlogT번 하게 되었지만, Y연산을 Q*T번 하던것을 QlogT번만 하게 되었다. Y연산이 상수시간이나 로그시간 정도에 해결되는 거라면, 대충 풀릴것이다.
세줄요약
- T번의 업데이트를 진행하고, Q개의 쿼리를 처리해야 한다. 쿼리는 어떤 조건을 처음으로 만족시킨 시점이 언제인가 (몇번째 업데이트가 진행되었을때인가) 하는 형태이다.
- 처음에 T번의 업데이트를 쭉 진행하면서, 이후에 쿼리들을 빠르게 처리할수 있는 형태로 T개의 중간 결과들을 저장해둘 수 있다면 아주 좋다
- 아니면, 오프라인 쿼리로 처리하는 것이 가능하고, 업데이트할 때마다 현재 시점에서 조건이 만족되는 쿼리들이 뭐뭐인지를 빠르게 구할 수 있다면 이것도 좋다
- 둘다 불가능하지만, 그래도 오프라인 쿼리로 처리할수는 있다면 이제 병렬이분탐색으로 해결한다. 업데이트를 TlogT번이나 해야 해서 앞의 방법들보다 비효율적이지만, 그래도 복잡도를 O(logT*(T*X +Q*Y)) 선으로 막을수 있다.
- 오프라인 쿼리도 안된다고? 그럼 ㅈㅈ..
대표 유형
그래프에서 엣지를 추가
- 업데이트 연산과 쿼리 연산이 disjoint의 union과 find 쿼리에 대응되는 문제이다.
- 이렇게 되면 둘다 O(α(V)). E번의 업데이트를 하려면 O(E*α(V))가 된다
- 하지만, 이 문제는 PBS를 써서 풀 필요가 없다. 위의 세줄요약에서 말했던 더 좋은 온라인풀이와 오프라인 풀이가 모두 가능하다. 자세한 설명은 엣지를 추가하는 쿼리만 들어올 때 참고
- LCA 또는 경로 쿼리를 이용해서 온라인으로 풀수 있고, 대충 O(E*α(V)+V+QlogV) 에 해결된다
- 오프라인쿼리를 쓰면 small-to-large trick을 이용해서 O(E*α(V)+QlogQ) 에 풀수있다
- PBS를 써서 잘 하면 O(E*α(V) + (V+Q)*logV*α(V)) 까지 만들수 있다..
- E*α(V)를 빼고 비교하고 α(V)도 상수라고 생각하면 O(V+QlogV), O(QlogQ), O((V+Q)logV) 이다. 실제로는 small-to-large 방법이 보통 젤 빨랐다
구간을 업데이트
- 업데이트 연산과 쿼리 연산이 세그먼트 트리의 update와 query에 대응되는 문제이다.
- 이것도 PST를 쓰면 PBS 없이도 풀수 있을것..같긴 하다 (TODO)
구현
- 이분탐색을 처리할때, 일반적인 방법으로 구현하려면 쿼리마다 구간의 시작, 끝, 중간값을 다 저장하고 있어야 하는데, 구현도 귀찮고 수행 시간도 좀 걸린다
- 그보다 binary jumping 으로 이분탐색을 구현하면, 쿼리마다 현재 확인할 구간 위치 하나만 들고 있으면 되므로 구현이 훨씬 편해진다. 스텝값은 모든 쿼리에 공통이니.
- 0에서 시작해서 n/2, n/4.. 이렇게 증가시켜 나가는 방법보다. n에서 시작해서 n/2, n/4,.. 이렇게 감소시켜 나가는 방법이 좀더 효율적으로 구현할수 있었다.
- 디자인적으로 고민을 많이 했는데, PBS의 공통 로직과, 문제에 따라 달라지는 개별 로직을 분리해서 라이브러리화 시키는 것이 복잡했다.
- 어떻게든 PBS부분을 라이브러리 함수로 뽑아낸다면, 이 함수는 시뮬레이션을 한단계씩 진행하고, 각 단계에서 특정 쿼리의 조건이 만족되는지를 확인하고, 각 단계에서 특정 쿼리가 원하는 답을 얻어낼수 있어야 한다. 추가적으로 시뮬레이션을 다시 처음부터 진행할수도 있어야 한다.
- 가장 제대로 짜려면.. proceed(), is_valid(), get_answer(), reset() 의 멤버변수를 갖는 Simulation 인터페이스를 만들고, 유저는 이 인터페이스를 구현한 클래스를 PBS 함수에 인자로 넘겨주도록 하는 것이 옳은 설계일 것이다..
- 하지만 PS하는데 무슨 인터페이스에 상속까지 해가면서 코드를 짜는거는 좀 너무 나간것 같은 느낌….
- 함수에 전달할 것을 좀 줄여보려는 고민끝에 두가지 방법이 나왔다. 둘다 유저가 클래스를 만들어야 하는 것은 피하고, 차라리 함수 클로저를 이용해서 시뮬레이션 상태를 유지하려는 방법인데..
- 하나는, proceed() 함수를 직접 만들지 않고 매 스텝마다 is_valid 함수를 yield해주는 제너레이터로 구현하는 것. 대충 이런식이다
# 유저가 구현해야 할 부분 def simulate(queries): def is_valid(query_no): u, v = queries[query_no] return dsu.find(u) == dsu.find(v) def get_answer(query_no) u, v = queries[query_no] return dsu.size(u) dsu = disjointset.DisjointSet(n) for u, v in merge_list: dsu.union(u, v) yield is_valid, get_answer def main(): ... binsearch.pbs(simulate, len(queries), len(merge_list)) ... # 라이브러리 부분 def pbs(simulate, ...): ... for t, (is_valid, _) in zip(range(X), simulate()): for q in queries: if is_valid(q): ... ...
- 다른 방법은 proceed와 is_valid함수를 리턴해주는 클로저를 만드는 것. 대충 이런식이다
# 유저가 구현해야 할 부분 def simulate(queries): def is_valid(query_no): u, v = queries[query_no] return dsu.find(u) == dsu.find(v) def get_answer(query_no) u, v = queries[query_no] return dsu.size(u) def proceed(): u, v = next(merge_iter) dsu.union(u, v) dsu = disjointset.DisjointSet(n) merge_iter = iter(merge_list) return proceed, is_valid, get_answer def main(): ... binsearch.pbs(simulate, len(queries), len(merge_list)) ... # 라이브러리 부분 def pbs(create_simulator, ...): ... proceed, is_valid, _ = create_simulator() for t in range(X): proceed() for q in queries: if is_valid(q): ... ...
- 전자가 좀더 짧은 느낌이라 전자로 구현했었는데.. 사실 크게 차이나는 부분은 아니다. 속도도 별로 차이는 없다
- 중요한것은 한참 뒤에 PBS라이브러리를 써서 문제를 풀때, 만들어야 하는 simulate 함수의 형태를 쉽게 다시 기억해낼 수 있는가인데.. 이것도 둘다 비슷해보인다; 음??
ps/병렬_이분_탐색.txt · 마지막으로 수정됨: 2023/08/01 07:23 저자 teferi
토론