온라인 알고리즘을 이용해서 평균 값 구하기

 

개요

 

이번 포스팅에서는 온라인 알고리즘을 이용해서 평균값을 구하는 법에 대해서 다루어 보도록 하겠다.

 

 

온라인 알고리즘

 

 

보통 알고리즘을 이용해서 어떠한 문제를 풀때에는, 보통 문제를 풀때 필요한 데이터를 전부 들고 있어야 한다.

 

 

예를 들어서, 100만 개의 데이터를 퀵소트를 이용해서 정렬한다고 가정하면,

메모리에 100만개의 데이터를 미리 가지고 있어야 정렬이 가능하다.

 

 

위에서 언급한 이러한 알고리즘을 보통 오프라인 알고리즘(off-line algorithm) 이라고 한다.

 

 

하지만, 실제 서비스를 만드는 경우 데이터가 언제/얼마나 들어올지도 모르는 데다가

설사 예측을 한다고 하더라도 데이터의 크기가 너무 커서 메모리에 한번에 다 못올리는 경우가 생긴다.

 

 

이러한 경우, 모든 데이터를 들고 있지 않아도 알고리즘을 이용해서 원하는 결과를 구할 수 있다.

 

보통 아래의 종류로 나누어 진다.

• 스트림 방식
• 다이나믹 프로그래밍 방식

 

 

이번 예제에서는 간단하게 온라인 알고리즘을 이용해서 평균을 구하는 법에 대해서 다루어 보도록 하겠다.

 

 

온라인 알고리즘을 이용해서 평균 값 구하기

 

일반적으로 자바 코드로 평균을 구할때는 아래와 같이 구한다.

 

import java.util.*;
import java.lang.*;
import java.io.*;

class Ideone
{

    public static void main (String[] args) throws java.lang.Exception
    {
        int[] data = {1,2,3,4,5,6,7,8,9,10};
        double total = 0;

        for(int i=0;i<data.length;i++)
            total += (double)data[i];

        System.out.println(total/data.length);
    }
}

 

하지만 위의 방식으로 구하는 경우, 평균값을 구하기 위해서 메모리가 너무 많이 필요하다.

 

또한 값이 너무 많이 들어오는 경우 오버플로가 발생 할 수 도 있다.

 

 

조금 더 개선을 해보도록 하자.

import java.util.*;
import java.lang.*;
import java.io.*;

import java.lang.Math; 

class Ideone
{
    public final static int min = 1;
    public final static int max = 10;
    public final static int range = max - min + 1;

    public static int generatorSeq(){
        return (int)((Math.random() * range) + min); 
    }

    public static void main (String[] args) throws java.lang.Exception
    {
        int[] data = {1,2,3,4,5,6,7,8,9,10};
        int count = 0;
        double total = 0;

        for(count=0;count<10;count++){
            int seq = generatorSeq();
            System.out.printf("%d ",seq);
            total += (double)seq;
        }
        System.out.println("");

        System.out.println(total/count);
    }
}

 

 

하지만 여전히, 오버플로우 문제에서 자유롭지 못하다.

 

 

이제 온라인 알고리즘을 통해서 평균을 구해보도록 하자.

 

 

온라인 알고리즘을 통해서 구하는 방법은 아래와 같다.

 

<새 평균> = <이전 평균> * (count-1)/count + <새로 들어온값> / count

 

 

코드로 구현하면 아래와 같다.

 

import java.util.*;
import java.lang.*;
import java.io.*;
import java.util.ArrayList;

import java.lang.Math; 

class Ideone
{
    public final static int min = 1;
    public final static int max = 10;
    public final static int range = max - min + 1;

    public static int generatorSeq(){
        return (int)((Math.random() * range) + min); 
    }

    public static void main (String[] args) throws java.lang.Exception
    {
        double avg = 0.0;
        for(count=1;count<=10;count++){
            int seq = generatorSeq();
            avg -= (avg / count);
            avg += ((double)seq / count);
        }
        System.out.println(avg);
    }
}