두 스택으로 역함수 없는 슬라이딩 윈도우 집계를 분할 상환 O(1)에 처리하는 방법

pop 이름을 shift로 바꾸면 어떨까 싶음. pop이라고 하면 윈도우 뒤에서 뭔가 빠진다는 느낌이 잘 안 와서 코드 보다가 멈칫함

shift는 윈도우 전체가 움직이는 것처럼 보여서 별로임. push는 크기를 1 늘리고 pop은 제일 먼저 들어온 값을 1 줄이는 거라 pop이 더 정확하다고 봄

스트리밍 분석이나 이상치 탐지에 쓸 데가 많아 보임. 윈도우 갱신당 분할 상환 O(1), 질의 O(1)(병합 비용 고정이라는 전제), 버킷 W개에 O(W) 메모리인 셈임. 매초 전체 윈도우를 다시 계산 안 해도 되는 게 큼

맞음. 그리고 수치 안정성 쪽에서 더 중요한 성질이 하나 있음. 집계가 지금 윈도우에 있는 값에만 의존하니까 NaN이나 무한대, 상쇄 소거 문제 대부분이 여기서 막힘

values_agg가 왜 필요한지 궁금했는데, values가 W만큼 커질 수 있어서 매번 합치면 O(W)가 된다는 답을 보고 이해함. 그래서 캐시해둔 거더라

Datalog 연구하면서 윈도우 집계를 매번 전체 재계산 없이 하는 방법을 못 찾았는데, 공간을 연산으로 바꾸는 발상 진짜 좋음

이미지 처리 쪽에는 1990년대에 이미 비슷한 방법이 있었음. 스택 대신 출력을 윈도우 크기 블록으로 나누는 방식이고 van Herk/Gil-Werman 알고리즘이라고 부름. Gil과 Werman 논문 2절에 1차원 윈도우 연산이 한 단락 나옴

Flakiness.io에서 커밋 이력으로 회귀를 잡는 데 윈도우 집계를 쓰는 중인데, 지금은 최근 10개 커밋까지만 보는 제약이 있음. 이 알고리즘이면 lookback을 키우거나 설정 가능하게 만들 수 있을 듯함

SQLite는 push/pop/eval 스트리밍 API로 윈도우 집계를 하고, DuckDB는 combine을 pop으로 바꾸는 세그먼트 트리 방식이더라. 이걸 쓰면 결합 가능한 집계를 역함수 집계로 바꾸는 어댑터를 만들 수 있을 듯함

f32 윈도우 합을 Rust로 짰는데 초당 3억 번 처리함. 이 알고리즘 알고 나서 주변에 엄청 얘기하고 다니는 중임

cum_aggs 스택이 사실상 prefix scan이라 병렬화도 될 것 같음. 합 같은 경우엔 입력을 미리 prefix scan해두면 길이가 정해지지 않은 부분 구간 합도 O(1)에 구할 수 있음