두 스택으로 구현하는 슬라이딩 윈도 집계

AI 요약

합계처럼 역연산이 있는 집계는 값을 넣을 때 더하고, 윈도에서 빠질 때 빼면 됩니다. 하지만 최솟값, 분위수, HyperLogLog 기반 고유값 근사치처럼 역연산이 없는 집계는 이 방법을 쓰기 어렵습니다. 부동소수점 덧셈도 엄밀히는 역연산이 아닙니다. 윈도에 NaN이 한 번 들어오면 빠져나간 뒤에도 누적 합계가 계속 NaN으로 남을 수 있습니다.

글은 여러 집계를 지원하는 간단한 두 스택 알고리즘을 소개합니다. 저자는 최악의 경우 단계마다 O(1) 시간을 보장하는 연구 논문을 읽다가, 그 논문에 함께 소개된 더 단순한 분할 상환 O(1) 알고리즘을 접했습니다. 논문은 이 알고리즘의 출처로 2011년 Stack Overflow 게시물을 들고, 게시물은 2001년 D. Sleator의 강의 노트를 참고합니다. 다만 강의 노트에는 FIFO 큐를 두 스택으로 구현하는 기법이 나오며, 슬라이딩 윈도 집계 자체를 다루지는 않습니다.

집계 연산을 일반화하기

알고리즘은 empty(), unit(x), combine(x, y), finalize(x) 네 함수로 집계를 표현합니다. empty는 빈 집계값을 만들고, unit은 입력값 하나를 집계 표현으로 바꿉니다. combine은 두 집계값을 합치며, finalize는 내부 집계값을 최종 결과로 변환합니다. 평균은 (합계, 개수) 쌍을 집계값으로 두면 됩니다. 각 입력을 (x, 1)로 바꾸고 쌍끼리 더한 뒤, 합계를 개수로 나눕니다.

입력값 Value, 내부 집계값 Agg, 최종 결과 Out은 서로 다른 타입일 수 있습니다. 예를 들어 문자열의 근사 고유값 집계에서는 각각 String, HyperLogLogSketch, u64가 됩니다.

두 스택의 역할

새 값은 values 스택에 넣고, 이 스택에 든 값의 누적 집계는 values_agg에 보관합니다. 반대편 cum_aggs에는 윈도에서 먼저 들어온 값들의 누적 집계가 역순으로 쌓입니다. 전체 윈도 집계는 cum_aggs 맨 위의 집계값과 values_agg를 결합해 구합니다. 따라서 조회는 상수 시간에 끝납니다.

삭제할 값이 cum_aggs에 없으면 values의 값을 하나씩 꺼내 반대 순서로 옮깁니다. 옮기는 동안 각 값의 누적 집계를 계산해 cum_aggs에 쌓습니다. 이 작업은 한 번에 O(w)까지 걸릴 수 있지만, 각 값은 스택 사이를 한 번만 이동합니다. 여러 연산에 걸쳐 비용을 나누면 삽입과 삭제는 분할 상환 O(1)입니다. 윈도 크기를 고정하지 않아도 되며, push와 pop을 필요한 횟수만큼 호출해 윈도를 늘리거나 줄일 수 있습니다. 최대 윈도 크기를 w라고 하면 메모리는 O(w)입니다.

결합 법칙과 부동소수점

combine은 결합 법칙을 만족해야 합니다. 즉, 세 값을 묶을 때 괄호를 어느 쪽에 두든 결과가 같아야 합니다. 부동소수점 덧셈은 이 조건을 엄밀하게 만족하지 않지만, 저자는 Kahan summation 같은 보정 합산을 쓰면 결과가 기대값에 더 가까워진다고 설명합니다.

이 알고리즘은 현재 윈도에 들어 있는 값만으로 각 집계값을 만듭니다. NaN이나 무한대가 윈도에서 빠진 뒤에도 그 값이 이후 결과를 계속 오염시키지 않습니다. 부동소수점 계산 오차도 윈도 밖의 값에서 장기간 누적되지 않습니다. 예를 들어 단순 누적 합계는 1e20 + 1 - 1e20 - 1을 계산하면 -1.0을 반환하지만, 윈도별로 집계를 다시 구성하면 현재 윈도에 없는 값이 결과에 남지 않습니다.

Lobsters 반응

• @pervognsen — 지연 시간을 분할 상환 방식이 아닌 방식으로 보장하는 접근은 @pkhuong의 글 https://pvk.ca/Blog/2025/08/19/monoid-augmented-fifos/ 도 참고하세요. 도입부에서 고전적인 두 스택 기법을 한 문단으로 요약한 뒤, 그 기법으로는 분할 상환을 없애기 어려운 이유를 설명합니다. 순수 함수형 데이터 구조에서 모노이드로 확장한 FIFO 큐를 만드는 익숙한 방법이 있습니다. 스택은 새 값을 넣을 때 이전 곱에 새 값을 곱하고 이전 cons 스택을 가리키면, 언제든 스택 안의 모든 값의 곱을 구하도록 확장할 수 있습니다. 스택 A는 새 값을 받고 스택 B는 값을 내보내는 식으로 큐를 만들 수 있습니다. A에서 꺼낸 값을 B에 넣으면 A의 내용이 뒤집혀 B 위에 놓입니다. 집계 기능이 없는 두 스택 큐 자체도 순수 함수형 환경 바깥에서 오래된 기법입니다. 어릴 때 Knuth의 연습문제를 풀며 처음 배웠고, 적어도 한 문제에 나오므로 1960년대까지 거슬러 올라간다고 생각합니다. 모노이드로 확장한 두 스택 큐는 그 기법에 스택 집계를 더한 것이니, 이 조합도 오래된 아이디어일 수 있습니다.
• @cblake — 글에서 암시한 빠진 인용은 지연 시간 급증을 막는 더 강한 보장을 다룬 Hood와 Melville의 「Real-time queue operations in pure LISP」(1981), 또는 Tarjan의 유명한 교재 「Data Structures and Network Algorithms」(1983)인 것 같습니다. 세 사람 이름이 모두 Robert라 재미있었습니다. 히스토그램처럼 전체 분포에 민감한 방식으로 분위수 등을 온라인에서 증분 계산하는 일반적인 문제라면, 제가 아는 가장 빠른 알고리즘은 https://github.com/c-blake/adix/에 있습니다. 특히 adix/bist.nim, lmbist.nim, embist.nim 등을 보세요. 다만 이 점을 뒷받침하는 인용은 찾지 못했습니다. CPU 캐시 예산에 따라 양자화 오차가 유효 숫자 3~6자리 정도로 제한되지만, 제가 보기에는 통계값 자체의 안정도보다 정확한 편입니다.

원문: orlp.net / 번역·요약: Trawling