역함수 없는 데이터에도 쓰는 슬라이딩 윈도우 집계 알고리즘

핵심 요약

• 슬라이딩 윈도우에서 합계·최댓값 같은 집계를 유지하려면, 합계처럼 역함수가 있는 연산은 deque로 쉽게 구현할 수 있지만 최솟값·최댓값·분위수·근삿값 중복 제거 등 대부분의 실용적인 연산은 역함수가 없어 다른 방식이 필요하다.
• 두 개의 스택과 하나의 집계값을 이용한 '투 스택' 알고리즘은 2001년의 FIFO 큐 구현 논문에서 영감을 받았으며, 이후 Tangwongsan et al.의 2011년 논문에서 더 일반화되었고, 이론적으로는 수십 년 전부터 알려진 간단하지만 강력한 기법이다.
• 알고리즘은 values(현재 스택)와 cum_aggs(이전 원소들의 누적 집계 역순)라는 두 스택을 유지하며, 새 값은 values에 추가하고, pop할 때 values가 비면 그 원소들의 누적 집계를 계산해 cum_aggs에 쌓는다.
• 매 pop마다 O(w) 작업을 하지만 w번에 걸쳐 분산되므로 amortized O(1)의 시간복잡도를 달성하며, 전체 메모리는 O(w)이다.
• 핵심은 eval() 호출 시 cum_aggs의 마지막 값과 values_agg를 combine하면 전체 윈도우의 집계를 상수 시간에 얻을 수 있다는 점이다.
• 알고리즘이 associate 연산을 요구하기 때문에 부동소수점 덧셈처럼 엄밀히 연관성이 없는 경우도 있지만, 각 집계가 윈도우 내 원소만의 조합이므로 NaN이나 무한대 같은 이상치가 해당 윈도우에만 영향을 미치고 다른 계산을 오염시키지 않는 장점이 있다.
• 윈도우 크기를 고정하지 않고 동적으로 push와 pop을 원하는 만큼 호출해도 작동하며, 부동소수점 오차가 윈도우 경계를 넘어 누적되지 않아 [1e20, 1] 같은 극단적 입력에서 기존 방식보다 정확한 결과를 보장한다.