scan은 cumulative 연산이다.
exclusive cumulative sum은 다음과 같이 구현된다. exclusive는 현재 요소는 포함하지 않음을 나타낸다. op 부분은 sum 연산자로 대체된다. identity()는 해당 연산에 대해서 입력과 동일한 결과를 주는 파라미터의 값이다. sum의 경우에는 0이다. 가령, 1+0 = 1.
int acc = identity();
for (int i = 0; i < elements.size(); ++i) {
acc = acc op elements[i];
out[i] = acc;
}
만약 위의 for loop 안의 순서를 바꾸게 되면, inclusive cumulative sum이 된다.
exclusive는 가령 [1, 2, 3, 4] 가 있으면,
[0, 1, 3, 6] 이 결과이고,
inclusive는
[1, 3, 6, 10]이 결과이다.
Naive 방법
step complexity: O(logN)
work complexity: O(N^2)
Hillis/Steele inclusive 방법
step complexity: O(NlogN)
work complexity: O(logN)
Blelloch exclusive 방법
step complexity: O(2logN)
work complexity: O(2N)
댓글