스택 두 개로 하는 슬라이딩 윈도 집계

요약

빼기가 안 되는 집계도 스택 두 개만 있으면 슬라이딩 윈도에서 평균 상수 시간에 구할 수 있습니다.

orlp.net 블로그의 글쓴이가 정리한 알고리즘입니다. 슬라이딩 윈도 집계(데이터 흐름에서 가장 최근 구간의 값만 모아 요약하는 계산)에 두루 쓸 수 있는데도 쓸모에 비해 덜 알려졌다고 봤습니다.

왜 중요한가

합계처럼 빼서 되돌릴 수 있는 연산이 아니어도 됩니다. 최댓값, 분위수, HyperLogLog 같은 근사 고유 개수에도 같은 방법이 통합니다.
결과가 지금 창 안의 값에만 달려 있습니다. 그래서 NaN 하나가 이후 합계를 계속 망치는 문제가 생기지 않습니다.
최악의 경우에도 상수 시간을 보장하는 논문의 방법보다 훨씬 단순해서 직접 구현하기 쉽습니다.

핵심 내용

새 값은 values 스택에 쌓고, 그 값들을 합친 집계 하나를 따로 유지합니다.
앞쪽 값을 뺄 때 cum_aggs 스택이 비어 있으면 values를 거꾸로 옮기며 누적 집계를 새로 만듭니다.
원소마다 한 번만 옮기므로 분할 상환 O(1)(가끔 느린 연산이 있어도 전체로 나누면 상수 시간)에 메모리는 창 크기만큼 듭니다.
합치는 함수는 결합 법칙(묶는 순서와 상관없이 결과가 같은 성질)만 지키면 되고, 문자열 이어 붙이기처럼 순서가 중요한 연산도 됩니다.
2011년 Stack Overflow 답변과 2001년 슬리터의 강의 노트에 나온 방법으로, 더 오래된 출처가 있을 것이라고 봤습니다.

HN 반응

일부 이용자는 1990년대 영상 처리 논문에 같은 문제를 블록 단위로 푼 알고리즘이 이미 있다고 보충했습니다.
데이터베이스 윈도 함수나 테스트 회귀 탐지에 쓰겠다는 경험담이 이어졌고, 앞쪽 값을 빼는 함수 이름을 pop으로 지은 것은 헷갈린다는 지적도 나왔습니다.

24개 표시 · 전체 24개

mlochbaum21시간 전 HN

짐작하셨듯이 이 주제는 1990년대 영상 처리 분야에 오래된 문헌이 있습니다. 거기서는 스택이나 큐가 아니라, 출력을 (길이가 일정한) 윈도와 같은 크기의 블록으로 나누는 방식을 씁니다. 독립적으로 발견한 두 팀의 이름을 따서 van Herk/Gil-Werman 알고리즘이라고도 부릅니다. 두 논문 중에서는 Gil과 Werman의 "Computing 2-D Min, Median, and Max Filters"를 더 좋아하는데, 1차원 윈도 연산은 섹션 II에서 한 문단만 할애해 설명합니다.

이걸 스트리밍 버전으로 처음 설명한 사람이 누구인지는 모르겠지만, https://signalsmith-audio.co.uk/writing/2022/constant-time-peak-hold/ 의 설명이 마음에 듭니다. 이렇게 쓸모가 많은데도 잘 알려지지 않았다는 건 정말 아쉬운 일입니다.
bradrn21시간 전 HN

내용도 무척 흥미롭지만, 이 웹사이트 디자인이 특히 마음에 든다는 말을 하고 싶습니다. 깔끔하고 균형이 잡혀 있고 읽기 편합니다. (사실 예전에 처음 접했을 때도 같은 생각을 했는데, 그 뒤로 URL을 잊어버렸습니다. 다시 만나게 되어 반갑습니다.)
tinco1일 전 HN

정말 멋집니다. 그런데 pop 함수 이름을 shift로(좀 못생긴 이름도 괜찮으시다면 popleft로) 바꾸시면 어떨까요? 윈도를 pop한다는 건 보통 쓰는 개념이 아니라서, 코드를 보다가 잠깐 멈칫했습니다.
orlp22시간 전 HN

shift는 윈도 전체가 이동한다는 인상을 줄 수 있어서 이름으로 마음에 들지 않습니다. push는 윈도 크기를 하나 늘리고, pop은 윈도 크기를 하나 줄입니다(가장 먼저 push된 원소를 내보내면서요).

제 머릿속에서 shift는 윈도 전체를 옮기는 동작이라서, push 한 번에 pop 한 번을 합친 것에 해당합니다.
tinco22시간 전 HN

그렇긴 한데, 그 연산을 가리키는 흔한 이름은 shift이고, pop은 보통 방금 설명하신 것과 다른 일을 합니다. shift보다 나은 단어를 찾으신다면 그것도 좋겠지만, 제 생각에 pop은 push의 역연산이어야 합니다. push하고 pop했으면 처음 상태의 데이터가 그대로 있어야죠.
orlp22시간 전 HN

push하고 pop했으면 처음 상태의 데이터가 그대로 있어야죠.

LIFO 큐라면 그렇지만 FIFO 큐는 아닙니다. 둘 다 push/pop이라는 명칭을 흔히 씁니다.
tinco22시간 전 HN

아, 그런 건 처음 봤네요. 저는 이론 문헌 쪽에는 약하다고 인정해야겠습니다. 제가 실무에서 본 큐는 put/get이나 enqueue/dequeue를 썼고, 루비 스크립트에서는 배열을 쓰면서 push/shift를 썼습니다.
dataflow18시간 전 HN

흔하지 않다고 말하고 싶습니다. 사실 어떤 언어에서든 FIFO 큐의 그 연산들을 가리키는 데 push()와 pop()을 둘 다 쓰는 건 한 번도 본 적이 없는 것 같습니다. (그리고 LIFO는 스택이고, 큐와는 정반대입니다.)

FIFO에는 보통 enqueue()와 dequeue()를 쓰는 걸 봤습니다. 아니면 push_front(), pop_back() 같은 것도 있고요.
teiferer22시간 전 HN

안타깝게도 그러면 pop이 두 가지 다른 뜻이 됩니다. 파이썬 리스트에서는 "오른쪽에서" pop하는데 TwoStackAgg에서는 "왼쪽에서" pop하거든요. 그래서 코드를 이해하기가 더 어려워져요.

차라리 popleft를 쓰는 건 어떨까요?
armcat23시간 전 HN
정말 멋지네요. 스트리밍 분석과 이상 탐지에 크게 쓸 수 있겠어요. 제가 제대로 이해했다면 다음과 같은 이점이 있는 거죠?
- 윈도를 갱신할 때마다 분할 상환 O(1) 작업
- 병합 연산 비용이 일정하다고 할 때 집계 질의는 O(1)
- 스케치 크기를 고정으로 보면, 버킷 W개에 대해 메모리는 O(W)
- 매초 윈도 전체를 다시 계산할 필요 없음
orlp22시간 전 HN
맞습니다. 그리고 수치 안정성 면에서 아주 중요하다고 보는 속성이 하나 더 있습니다.
- 집계값이 현재 윈도 안에 있는 값에만 의존합니다.
슬라이딩 윈도에서 NaN, 무한대, 유효숫자 손실(catastrophic cancellation) 등으로 생기는 문제는 대부분 이 속성으로 해결됩니다.
Sesse__19시간 전 HN

제가 데이터베이스 쪽에서 일할 때 이 알고리즘을 알았더라면 좋았을 텐데요. 윈도 함수에 딱 맞았을 겁니다(대부분의 사용자에게는 부동소수점에서도요). 이제 보니 이 알고리즘이 설명된 곳을 두세 군데에서 본 것 같네요 :-)
Lichtso18시간 전 HN

제가 틀리지 않았다면, 슬라이딩 윈도(커널)에 대한 가중 fold / reduction 0은 합성곱(convolution) 1이죠?

여기서 소개된 알고리즘은 순차적이지만, 병렬로 할 수 있을 것 같은 냄새가 납니다.

사실 "cum_aggs" 스택은 prefix scan 2입니다.

값의 합(그리고 그것의 확장으로 평균)이라면, 입력에 prefix scan을 해 두었을 경우(이건 병렬로 할 수 있습니다) 어떤 부분 구간이든(그렇습니다, 고정 크기 윈도가 아니라 동적 크기여도 됩니다) reduction을 상수 시간에 구할 수 있습니다.
ashkankiani17시간 전 HN

첫 번째 슬라이딩 윈도의 경우, 필요한 게 합뿐이고 연산이 가역적이라면 양방향 큐조차 필요 없습니다. 연산을 적용할 때 되돌려야 할 N번째 값만 알면 되거든요. 개수만 세다가 N개가 쌓이면 N번째 값을 내보내기 시작하면 됩니다. 저장할 값이 말 그대로 3개뿐입니다.
teiferer14시간 전 HN

좀 더 설명해 주실 수 있나요? 한 번 그렇게 하고 나면 어떻게 하나요? 저장해 두지 않았다면 N-1번째 값은 어디서 가져오죠?
ktimespi21시간 전 HN

저는 datalog 연구 프로젝트에서 이런 집계를 다루고 있었는데, 윈도 전체를 다시 계산하지 않고 해낼 방법을 찾지 못했습니다. 공간을 주고 계산을 얻는 방식이 정말 마음에 듭니다. 너무 멋져요!!!
MawKKe22시간 전 HN

이 클래스를 어떻게 쓰는지 보여 주는 예제 코드가 있으면 좋겠습니다.

somat16시간 전 HN

저도 사용법을 정확히 이해하기가 좀 어려웠습니다. 합계 예제를 재현해 보려다가 이렇게 만들었는데, 전체적으로 너무 투박해서 제가 잘못 쓰고 있는 게 분명합니다.

    def example_sum():
        def sum_empty():
                return 0
        def sum_unit(value):
                return value
        def sum_combine(agg_a, agg_b):
                return agg_a + agg_b
        def sum_finalize(agg):
                return agg

sum_agg = two_stack_agg(sum_empty, sum_unit, sum_combine, sum_finalize)
        w_size = 4
        entry_values = list(range(1, 11) )
        trim_flag = False
        i = 0
        print(agg_sum.eval(), agg_sum.cum_aggs, agg_sum.values)
        agg_sum.push(entry_values[i])
        i += 1
        while agg_sum.len() > 0:
                if i < len(entry_values):
                        agg_sum.push(entry_values[i])
                        i += 1
                if trim_flag:
                        agg_sum.pop()
                elif agg_sum.len() >= w_size:
                        trim_flag = True
                print(agg_sum.eval(), agg_sum.cum_aggs, agg_sum.values)

결과는 다음과 같습니다.

    0 [] []
    3 [] [1, 2]
    6 [] [1, 2, 3]
    10 [] [1, 2, 3, 4]
    14 [5, 9, 12, 14] []
    18 [5, 9, 12] [6]
    22 [5, 9] [6, 7]
    26 [5] [6, 7, 8]
    30 [] [6, 7, 8, 9]
    34 [10, 19, 27, 34] []
    27 [10, 19, 27] []
    19 [10, 19] []
    10 [10] []
    0 [] []

그러니까 크기 4짜리 윈도 집계라면 값을 push하다가 윈도 크기를 넘으면 pop하는 겁니다. 저는 윈도 크기를 재려고 길이(values 길이와 cum_agg 길이의 합)를 썼지만, 그냥 개수를 세도 됩니다.

투박한 부분은 대부분 예제와 똑같이 윈도가 차오르고 비워지는 동작을 만들려다 생긴 것이라, 실제 데이터에서는 아마 필요 없을 겁니다. 나머지는 제가 원래 단순하고 투박하게 파이썬을 짜는 편이라서 그렇고, 주어진 집계 함수들을 집계 클래스 안에 저장해 뒀습니다.

aslushnikov21시간 전 HN

저희는 Flakiness.io에서 커밋 이력의 회귀(regression)를 찾아내려고 슬라이딩 윈도 집계를 계산하고 있습니다.

현재 알고리즘은 최적이 아니라서 "되돌아볼 범위(lookback)"를 제한해야 했습니다. 테스트 실패는 관측된 최근 10개 커밋 동안 이력이 완벽했을 때만 회귀로 표시합니다.

지금 방식도 꽤 잘 동작하지만, lookback을 더 크게 하거나 설정할 수 있게 해 달라는 요청이 몇 번 있었습니다. 이 알고리즘으로 그걸 해낼 수 있을 것 같습니다.

공유해 주셔서 감사합니다!
ncruces21시간 전 HN

정말 멋지네요.

SQLite는 윈도 집계에 "스트리밍" 방식의 push/pop/eval API를 씁니다.

DuckDB는 "combine"을 "pop" 대신 쓰는 방식으로 "세그먼트 트리 집계"를 구현합니다.

그러니 결합 가능한(combinable) 집계를 가역(invertible) 집계로 바꿔 주는 어댑터를 분할 상환 O(1)로 제공할 수 있겠네요.
repiret19시간 전 HN

저는 한 달쯤 전에 이 알고리즘을 알게 됐고, 그 뒤로 만나는 사람마다 이야기하고 있어요. 진짜 너무 멋지잖아요.

지금 제 Rust 구현은 f32 슬라이딩 윈도 합을 초당 3억 개 속도로 유지할 수 있어요.
teiferer22시간 전 HN

self.values_agg는 무엇에 필요한가요? finalize가 호출될 때 아직 cum_aggs에 반영되지 않은 값들의 집계에만 쓰이는데, 그 값은 그 자리에서 바로 계산하면 되지 않나요?

혹시 finalize를 반복 호출할 때 그 계산을 재사용하려는 건가요?
orlp21시간 전 HN

values가 꽤 클 수 있어서(최대 W), values_agg가 없으면 현재 윈도 값을 구하는 데 O(1)이 아니라 O(W)가 듭니다.

참고로 finalize 호출은 없고 eval만 있습니다. eval은 윈도에 대한 현재 집계값을 돌려줍니다. 이런 슬라이딩 윈도 함수는 보통 윈도가 움직일 때마다 현재 값을 얻고 싶은 용도로 씁니다.
ktimespi21시간 전 HN

네, 저도 그게 좀 거슬린다는 데 동의합니다.

Hacker News에서 보기 ↗