Keep it simple, Stupid !!!

회사에서 Memory 사용량을 실시간으로 파일로 기록하는 아주 단순한 프로그램을 만들었다. 그 동안, 눈으로 작업관리자를 뚫어져라 쳐다봤던 방식보단 조오금 진보했다랄까?

아무튼 유틸리티가 필요했던 이유는 다름이 아니라 바로 개발자의 최대의 적! 메모리 누수가 일어나는 지를 알아보기 위함이다.

회사 프로젝트 특성상, Operation에 따라 메모리 사용량이 출렁거리는 상황이기 때문에 꾸준히 메모리를 본다고 해서 누수가 나는지, 안나는지를 알 수 없었다. 그래서 단순히 실시간으로 프로그램의 메모리 사용량을 파일로 기록하는 프로그램을 만들었는데...

메모리 사용량의 추세를 알기 위해 다음의 짓을 매번 반복했다.
1. 로그 파일을 열어서
2. Excel에 붙여넣고
3. 2차원 꺽은선 그래프를 그리고
4. 추세선 그리기

근데 너무 이 짓이 귀찮아서, 실시간으로 추세선을 알 수 있는 방법이 있지 않을까 해서 사용한 것이 "최소제곱(자승)법" 이다.

뭐... 이쯤되면 최소 자승법이 뭔지는 네이버, 구글에서 뒤져보면 나올 것이고...귀찮은 분은 위에 링크를 클릭~!

이를 구현하기 위해서 수식을 살펴봤는데, 적용하기엔 무리가 있었다. 왜냐하면 "최소제곱법"을 이용해 추세선을 그리기 위해서는 데이터를 모두 가지고 있어야 한다는 점이였다.


위 수식을 보면, 실시간 데이터기 때문에 평균x, y가 매번 바뀌고, 이를 구하기 위해서는 매번 평균 계산을 다시해야 한다. 물론 평균값을 유지하는 것이 아니라 데이터의 총 합만 유지하면 매번 평균값을 구하는 것은 O(1)시간에 구할 수 있다.

그러나... a 공식의 분자, 분모를 계산할 때도 그럴까?

이를 계산하기 위해서는 O(n)의 계산이 필요한데, 매 초당 이런 계산을 한다는 것은 매우 부담스러운 일이고... 시간이 갈 수록 n이 커지기 때문에 점점 계산량이 많아진다는 부담이 있다.

개선의 시작은 다음과 같은 아이디어에서 시작했다.

"n-1번째의 a를 구하고, 여기에 x,y 평균의 변화량을 이용해서 n번째의 a를 구할 수 있지 않을까?"

그래서 각 식을 n-1번째 식으로 전개해서 풀어보았다.

(수식을 타이핑하기 귀찮으므로... 전개는 생략한다...)



는 페르마드립이고, 첨부파일에 스캔해놓은 발로 쓴 공식을 참조하길 바란다.


결국, 1), 2) 식과  각 x, y의 총합만 매 Tick(데이터가 들어오는 순간)마다 업데이트하면 a를 구할 수 있었다.

다음은 이를 c++로 구현한 소스이다.

[LSM Structure.h]

### cpp
struct LSMData
{
    float x, y;
};
struct Linear
{
    float a, b;
};

[LeastSquareMethod.h]

### cpp
#include "LSMStructure.h"
class LeastSquareMethod
{
public:
    LeastSquareMethod(void);
public:
    ~LeastSquareMethod(void);
    int Count() { return m_nCount; };
    void Reset()
    {
        m_lnResult.a = 0;
        m_lnResult.b = 0;

        m_nCount = 0;

        m_fTotalX    = 0.0f;
        m_fTotalY    = 0.0f;
        m_fDeltaX    = 0.0f;
        m_fDeltaY    = 0.0f;
        m_fDeltaXX    = 0.0f;
        m_fDeltaXY    = 0.0f;
    }

    void AddData(const LSMData& data);
    Linear GetTrendency();

private:
    void Update(const LSMData& data);

    Linear m_lnResult;
    int    m_nCount;

    float  m_fTotalX, m_fTotalY;
    float  m_fDeltaX, m_fDeltaY;
    float  m_fDeltaXX, m_fDeltaXY;
};

[LeastSquareMethod.cpp]

### cpp
#include "LeastSquareMethod.h"

LeastSquareMethod::LeastSquareMethod(void)
{
    Reset();
}

LeastSquareMethod::~LeastSquareMethod(void)
{
}

void LeastSquareMethod::AddData(const LSMData& data)
{
    m_nCount++;
    Update(data);
}

Linear LeastSquareMethod::GetTrendency()
{
    return m_lnResult;
}

void LeastSquareMethod::Update(const LSMData& data)
{
    if(m_nCount == 1)
    {
        m_fTotalX    = data.x;
        m_fTotalY    = data.y;
        m_lnResult.a = data.x;
        m_lnResult.b = data.y;
        return;
    }

    float prevAvrX = m_fTotalX / (m_nCount-1);
    float prevAvrY = m_fTotalY / (m_nCount-1);
    float curAvrX = (m_fTotalX + data.x) / m_nCount;
    float curAvrY = (m_fTotalY + data.y) / m_nCount;

    float deltaXavr = curAvrX-prevAvrX;
    float deltaYavr = curAvrY-prevAvrY;

    // 이전 값을 재활용해 LSM 전개
    m_fDeltaXY    = m_fDeltaXY - deltaXavr*m_fDeltaY - deltaYavr*m_fDeltaX
                   + (m_nCount-1)*deltaXavr*deltaYavr        //    상수
                   + (data.x-curAvrX)*(data.y-curAvrY);        //    상수
    m_fDeltaXX    = m_fDeltaXX - 2*deltaXavr*m_fDeltaX + deltaXavr*deltaXavr*(m_nCount-1)
                   + (data.x-curAvrX)*(data.x-curAvrX);
    m_lnResult.a = m_fDeltaXY / m_fDeltaXX;
    m_lnResult.b = curAvrY - curAvrX*m_lnResult.a;

   

    // 다음 계산을 위해 변수 Update
    m_fTotalX += data.x;
    m_fTotalY += data.y;

    m_fDeltaX = m_fDeltaX - (curAvrX-prevAvrX)*(m_nCount-1) + data.x - curAvrX;
    m_fDeltaY = m_fDeltaY - (curAvrY-prevAvrY)*(m_nCount-1) + data.y - curAvrY;
}

[main.cpp]

### cpp
#include <cmath>
#include "LeastSquareMethod.h"
#define FLOAT_EQ(x, y, t) (abs(x-y) < t)

int _tmain(int argc, _TCHAR* argv[])
{
    NLeastSquareMethod nlsm;
    LSMData example[] = {
        {10, 71}, {20, 45}, {30, 24}, {40, 8}
    };
    int numOfData = sizeof(example)/sizeof(LSMData);

    LeastSquareMethod lsm;
    for(int i=0; i<numOfData; i++)
    {
        lsm.AddData(example[i]);
    }
    Linear lsmResult = lsm.GetTrendency();
   


    printf("Answer >> \n");
    printf("a : %.3f\tb : %.3f\n\n", -2.1f, 89.5f);

    printf("Fast LSM >> [%s]\n", (FLOAT_EQ(-2.1f, lsmResult.a, 0.0001f) && FLOAT_EQ(89.5f, lsmResult.b, 0.0001f))?"Success" : "Failed");
    printf("a : %.3f\tb : %.3f\n\n", lsmResult.a, lsmResult.b);
    return 0;
}