2019-08-11프로그래밍 / 알고리즘

실시간 데이터의 평균을 효율적으로 구하기

이번 포스팅에서는 실시간으로 빠르게 쌓이는 데이터들의 평균을 효율적으로 구할 수 있는 방법에 대해서 간단하게 설명하려고 한다. 이런 실시간 데이터의 평균을 구해야하는 경우는 생각보다 꽤 많은데, 서버 엔진의 액세스 로그에 쌓이는 응답들의 평균 응답 시간을 구한다던가, 센서에서 들어오는 값들의 평균을 구한다던가 하는 경우이다. 이때 이런 데이터들은 빠르게는 1ms 정도의 간격으로 수집되는 경우도 비일비재하기 때문에, 데이터를 입력받자마자 빠르게 처리해야하는 성능이 굉장히 중요하다.

이때 우리가 이 데이터들을 가지고 실시간으로 평균을 구해야한다면, 일반적으로 생각나는 평균의 수식은 전체 데이터의 총합 / 데이터 배열의 길이일 것이다. 이렇게 구한 평균 값을 산술 평균이라고 한다. 그러나 우리가 일반적으로 산술 평균을 구하는 방법은 데이터를 실시간으로 빠르게 처리해야하는 시스템과는 별로 맞지 않는 방법이다. 왜 그럴까?

일반적인 산술 평균 공식의 문제점

일반적으로 우리가 산술 평균을 구한다고 할때 떠오르는 공식은 다음과 같다.

Average(n) = \frac{1}{n}\sum_{k=1}^{n}x_k = \frac{x_1 + x_2 + ... + x_n}{n}

수식으로 보면 조금 복잡해보일 수 있지만 결국 k=1일 때 n이 될 때 까지 이터레이션을 돌리며 x1 ~ xn까지 전부 더한 다음 마지막으로 1/n을 곱해주는 것, 결국 우리가 학교에서 배웠던 일반적인 평균 알고리즘이다. 이렇게 데이터를 모두 모아서 한번에 연산하는 방식을 배치식(Batch Expression)이라고 부른다.

배치식의 단점은 바로 시간 복잡도가 $O(n)$ 이라는 것이다. 이건 데이터의 숫자가 적을 때는 큰 문제가 없더라도 계속 해서 누적되는 실시간 데이터를 빠르게 처리해야하는 시스템에서는 치명적인 단점이 된다.

간단하게 1부터 100,000까지의 평균을 반복적으로 구하는 배치식 평균 알고리즘의 수행 시간을 확인해보자.

let avg = 0;
const numbers = [];

function average (numbers = []) {
  const sum = numbers.reduce((prev, current) => prev + current, 0);
  return sum / numbers.length;
}

console.time('avg1');
for (let k = 1; k < 100001; k++) {
  numbers.push(k);
  avg = average(numbers);
}
console.timeEnd('avg1');
console.log(`그래서 평균은? -> ${avg}`);

실시간 데이터 처리를 흉내낸 간단한 코드를 작성했다. numbers 배열에는 반복적으로 새로운 데이터가 입력되고 그때마다 새로운 평균을 구한다. 첫번째 for문은 실시간으로 입력되는 데이터 환경을 구현하기 위한 것이므로 시간 복잡도에서 제외하고 getAvg 함수의 내부만 봐도, 한번 평균을 구할 때마다 지금까지 누적한 전체 데이터의 배열을 처음부터 순회하며 총합을 구하는 모습을 볼 수 있다.

그래서 결국 이 알고리즘이 100,000개 데이터의 평균을 구하는 데 소요된 시간은…

$ node average.js
avg1: 8146.261ms
그래서 평균은? -> 50000.5

8146ms 정도? 대략 8초라는 엄청 나게 긴 시간이다. 실시간 데이터 처리 시스템에서 어떤 값을 처리하는데 8초가 걸린다면 그건 그냥 망한거다. (사실 1초만 넘어도 망했다고 한다.)

게다가 실시간 데이터의 특성 상 데이터의 양은 점점 누적되어 늘어날 수 밖에 없는데, 100,000개 처리에 8초면 1,000,000개 처리면 대충 80초 정도 걸리지 않을까?

사실 배치식의 단점은 시간이 단순히 오래 걸린다는게 아니라 데이터가 늘어나면 수행시간도 비례해서 늘어난다는 것이다. 또한 $n$ 번째 데이터까지 합친 평균을 계산할 때 이전 평균 계산 결과를 전혀 사용하지 못하므로 결국 지금까지 들어온 모든 데이터를 저장하고 있어야 하는데, 이때 불필요한 메모리 자원도 낭비되게 된다. 그럼 데이터가 늘어나도 언제나 수행 속도가 일정한 $O(1)$ 평균 알고리즘이 있을까?

평균 필터 알고리즘

있다. 바로 평균 필터(Average Filter) 알고리즘이다. 이 알고리즘은 n번째 데이터가 들어온 데이터 셋의 평균을 구할 때 n-1 까지의 평균을 재사용할 수 있는 알고리즘이다. 이런 알고리즘을 재귀식(Recurrence Expression)이라고 한다. (참고로 재귀식은 재귀함수보다 좀 더 포괄적인 개념이다.)

재귀식인 평균 필터 알고리즘을 사용하면 이전에 들어온 데이터를 전부 저장해놓을 필요도 없고 몇개의 데이터가 누적되든 반드시 $O(1)$ 의 시간 복잡도를 보장한다. 그래서 이 알고리즘은 센서에서 짧은 간격으로 들어오는 데이터들을 실시간으로 처리해야하는 IOT나 임베디드 분야에서 더 많이 사용된다.(필자도 이 쪽 분야에서 일하는 형한테 처음 배웠다.)

하지만 다짜고짜 수학으로 들어가면 재미가 없으니, 이해를 돕기 위해 이번에는 먼저 코드와 수행시간을 확인해보고나서 이 알고리즘에 대한 설명을 하도록 하겠다.

let avg = 0;
function cumulativeAverage (prevAvg, newNumber, listLength) {
  const oldWeight = (listLength - 1) / listLength;
  const newWeight = 1 / listLength;
  return (prevAvg * oldWeight) + (newNumber * newWeight);
}

console.time('avg2');
for (let k = 1; k < 100001; k++) {
  avg = cumulativeAverage(avg, k, k);
}
console.timeEnd('avg2');
console.log(`그래서 평균은? -> ${avg}`);

cumulativeAverage 함수는 이전 데이터까지의 평균과 새로 들어온 데이터, 총 데이터 개수 이렇게 3개의 인자를 사용하는 함수이다. 그리고 간단한 수식을 통해서 바로 평균을 계산한다. 위에서 작성한 average 함수와 가장 큰 차이점이 있다면, 함수 내부에 이터레이션이 없다는 것이다.

위에서 봤던 배치식 평균 알고리즘은 100,000개 데이터의 평균을 실시간으로 구해내는데 8초의 시간이 소요되었지만 이 친구는 급이 다르다.

$ node average.js
avg: 4.631ms
그래서 평균은? -> 50000.5

쨘, 8000ms에서 4ms가 되었다. 뭐 이건 사실 당연한 사실이다. 평균을 구하기 위해 전체 데이터를 순회할 필요가 없이 단순한 연산만 반복하면 되기 때문이다. 데이터의 개수를 1,000,000개로 늘려도 수행시간은 대략 10ms 정도로, 크게 변하지 않는다.

그리고 이 코드에서 데이터의 양을 100,000에서 1,000,000으로 늘렸을 때 시간이 늘어난 이유는 그저 for문이 더 오래 도니까 그런 것인데, 실시간 데이터 처리 시스템에서는 이렇게 이터레이션을 돌면서 데이터를 입력하는 것 아니라 말 그래도 비동기적으로 쭉쭉 데이터가 들어오고 이벤트 리스너를 통해 평균 함수를 실행할 것이므로 결국 실제 사용 사례에서는 항상 균일한 수행 속도를 가지게 된다고 생각할 수 있다.

그럼 이 알고리즘은 어떤 원리로 작동하는 것일까?

무슨 원리로 이렇게 되는건가요?

구글에 평균 필터 알고리즘을 검색해보면 이미 많은 분들이 배치식에서 재귀식을 유도해내는 과정을 많이 포스팅 해놓은 것을 볼 수 있었다. 하지만 이런 포스팅들의 특성 상 글쓴이 본인의 아카이브 느낌이 강하기 때문에 친절한 설명은 딱히 없었던 것 같다.

그리고 그렇게 수식을 유도하며 설명하는 방법은 수학과 친하지 않은 사람에게는 직관적인 설명이 될 수 없다. 그래서 필자는 배치식에서 재귀식을 유도하는 방법 보다 좀 더 직관적이고 간단한 느낌으로 설명해보려고 한다. 일단 평균 필터 알고리즘의 공식을 한번 보자.

Average(n) = \frac{n-1}{n}Average(n-1) + \frac{1}{n}x_n

이 식의 $n$ 은 현재까지의 전체 데이터 길이, $Average(n-1)$ 는 이전 데이터까지의 평균, $x_n$ 은 이번에 새로 들어온 데이터를 의미한다. 그렇다면 이 식이 의미하는 것이 뭐길래 평균을 구할 수 있도록 해주는 것일까?

이 식에서 중요한 키워드는 바로 가중치이다. 우리가 배치식을 버리고 재귀식을 사용하기 위한 조건은 바로 “이전 평균 값을 활용할 수 있을 것”이었다. 그러기위해 우리는 새로운 평균을 구하기 위해 사용할 이전 평균 값이 새로운 평균 값에 끼칠 영향을 계산해줘야 하는 것이다.

식을 자세히 보면 이전 평균 값인 $Average(n-1)$ 에는 $\frac{n-1}{n}$ 이 곱해지고 있다. 이때 $\frac{n-1}{n}$ 이 의미하는 것이 바로 가중치이다. 또 새로 들어온 데이터인 $x_n$ 을 보면 $\frac{1}{n}$ 이 곱해지고 있는데, 이 또한 새로운 데이터의 가중치이다.

좀 더 빠른 이해를 돕기 위해 간단한 예시를 보면서 설명하도록 하겠다.

const prevData = [1, 2, 3, 4];
const prevAverage = (1 + 2 + 3 + 4) / 4; // 2.5

여기 길이가 4인 간단한 데이터셋이 있다. prevAverage는 여러분이 좀 더 직관적으로 이해할 수 있도록 그냥 배치식을 하드코딩했고, 할당된 값은 1, 2, 3, 4의 평균인 2.5가 된다.

이때 이 데이터셋에 5라는 값이 새로 들어오면 배열의 길이는 5가 될 것이다. 이때 배치식을 사용하며 계산하게 되면 1부터 5까지 모두 더한 후 배열의 길이인 5로 나누게 될 것이고, 재귀식을 사용하면 기존 4개 원소의 평균이었던 2.5에 가중치인 4/5를 곱해주고 새로 들어온 5에도 가중치인 1/5를 곱한 후 서로 더하기만 하면 된다.

한번 아래 코드를 콘솔에서 실행시켜보고 결과를 확인해보자.

const batch = (1 + 2 + 3 + 4 + 5) / 5;
const recurrenced = (2.5 * (4 / 5)) + (5 * (1 / 5));
console.log(batch, recurrenced);
// 3 3

결과는 둘 다 3으로 동일하게 출력된다. 즉, 쉽게 말하자면 이전 평균의 값과 새로운 데이터가 새로운 평균에서 얼마 만큼의 비중을 가지고 있는지를 계산해서 더해주는 것이다.

이제 대충 이해가 되었으리라 생각한다. 만약 배치식에서 재귀식을 유도하는 과정이 궁금하신 분은 구글에 평균 필터라고 검색해보면 다른 분들이 작성해놓은 많은 포스팅이 있으니 그 쪽을 참고해보도록 하자. 필자는 개인적으로 그런 수식 유도 과정보다 이 알고리즘이 작동하는 추상적인 개념을 이해하는 것이 더 중요하다고 생각하기 때문에 이 포스팅에서는 별도의 유도 과정을 적지는 않겠다.

이상으로 실시간 데이터의 평균을 효율적으로 구하기 포스팅을 마친다.

일반적인 산술 평균 공식의 문제점

평균 필터 알고리즘

무슨 원리로 이렇게 되는건가요?

Evan Moon