|
※ 강좌에 대한 질문은 '문의게시판'에서
해주세요.
머리말
:
안녕하세요? /^.^/ 이번 강좌에서는
자료의 저장 및 관리에 쓰이는 배열 특히나 그 크기가 절로 늘어나는 동적배열인 Vector클래스와 key값으로 value값을
찾아가는 검색클래스 Hashtable의 성능실험을 해보도록 하겠습니다.
곁다리로 반복문에서 String클래스와
StringBuffer 클래스의 이용이 성능에 얼마만큼 차이를 보이는지도 직접 알아보지요.
문제제기는 Hashtable은 개발자에게
데이타 검색 알고리즘에 신경을 쓰지 않도록 해주는 매우 유용한 클래스임을 알게된 데에서 시작되었습니다. key값으로 value값을
바로 찾아갈 수 있도록 해주기는 하지만 실제로 이게 얼마만큼의 효용을 가지겠느냐에 대한 의문을 갖고 있던 차에,
수학적으로 따지자면, 검색속도가 거의 O(1)에
떨어지는 자료구조라는 것이지요. 리스트나 배열은 적어도 n번을 뒤져야하기 때문에 검색속도가 O(n)에 바운드 되나, 해쉬테이블은
key값을 가지고 바로 찾아가므로 거의 O(1)가 됩니다.
O notation은 Big-Oh Notation이라고 부르구요. 알고리즘의 수행시간의 upper bound입니다. 정확하게
수학적으로 정의되어있습니다. 소팅을 가장 좋은 예로 들죠. 버블 소트는 O(n^2) - n개의 데이터가 있으면 최대 n*n만큼
데이터를 처리해야한다 이런 뜻입니다. 아시다시피 퀵소트는 O(nlogn)입니다. 한번 n에다가 100만을 넣어보세요.. 그럼...
n^2과 nlogn의 차이가 엄청남을 알 수 있죠. 그렇다면 O(1)는 상수시간이라는 말입니다. 즉, 데이터 사이즈에 상관업시
이 작업은 상수시간에 떨어진다는 말이죠. 가장 성능이 좋은 알고리즘이겠죠..
Big O notation의 정확한 정의는,f(x)와
g(x)가 있을 때, 0 <= f(n) <= c*g(n) (for all n larger than N, c>0)
을 만족하면 f(x)=O(g(x)) 로 나타내는 것을 말한답니다. - 나우누리 자바동에서 발췌 -
이러한 내용을 보고서, 그제서야 채팅방을 구성할 때 제목을 키값으로
Hashtable을 즐겨 쓰던 이유를 알게된 거거든요. (저도 그 전까지는 솔직히 그냥 남들이 쓰니까 썼지요.) 그렇다면,
데이타가 2단으로 구성되어있을 경우에는 어떨까? 하는 궁금증이 일어 실험을 시작하게 되었습니다. 즉, Hashtable안에
또 Hashtable들을 넣는 거와 Vector안에 또 Vector를 넣는 경우를 비교해보는 것이지요. Hashtable안에
또 Hashtable을 넣느다. 방(Hashtable) 안에 클라이언트(Hashtable)들을 관리한다? 이것이 만족스러운
결과가 나오면 저는 다음 프로젝트에 Hashtable을 3단으로 이용할 지도 모릅니다. ^_^ 궁금하시지 않으십니까? 재미없으신가요?
나가욧~! 전 재미있는데....^_^
제가 궁금해서 필요한 대로 코딩해 비교를 했기 때문에 읽으시는 분께는
적절한 비교가 아닐지도 모릅니다. 감안하시고 읽으셨으면 좋겠습니다. ^_^
시작해볼까요? 아자자잣
실험 컴퓨터 사양 :
CPU : 음, 모지???? 셀러론 400~
500 정도일겁니다. --;
RAM : 265M
OS : win2k pro.
실험에 사용된 소스 : 2 가지 입니다
|
//TestVector.java
import java.util.*;
public class TestVector
{
private int nMap;
private Vector vt1, vt2;
private long nTime1, nTime2, nTime3;
public TestVector(String str)
{
nMap = Integer.parseInt(str);
vt1 = new Vector(nMap);
vt2 = new Vector(nMap);
nTime1 = System.currentTimeMillis();
inputData();
nTime2 = System.currentTimeMillis();
// outputDataAll();
outputData();
nTime3 = System.currentTimeMillis();
System.out.println("입력경과시간 :" + (nTime2 - nTime1));
System.out.println("출력경과시간 :" + (nTime3 - nTime2));
}
private void inputData()
{
for(int i = 0; i < nMap ; i++)
vt1.add(i + "vt1");
for(int i = 0; i < nMap ; i++)
vt2.add(vt1);
}
private void outputDataAll()
{
String strtemp="";
for(int i = 0; i < nMap ; i++)
{
for(int j = 0; j < nMap; j++)
{
strtemp= (String)((Vector)vt2.get(i)).get(j) ;
// System.out.print(strtemp + " ");
}
// System.out.println();
}
}
private void outputData()
{
String strtemp = "";
int i = 0, j =0;
for(; i < nMap; i++)
{
for(; j < nMap; j++)
{
strtemp = (String)((Vector)vt2.get(i)).get(j);
if(strtemp.equals(j + "vt1"))
System.out.print(strtemp + " ");
}
}
System.out.println();
}
public static void main(String[] args)
{
if(args.length == 1)
new TestVector(args[0]);
System.exit(0);
}
}
//TestHashTable.java
import java.util.*;
public class TestHashTable
{
private int nMap;
private Hashtable ht1, ht2;
private long nTime1, nTime2, nTime3;
public TestHashTable(String str)
{
nMap = Integer.parseInt(str);
ht1 = new Hashtable(nMap);
ht2 = new Hashtable(nMap);
nTime1 = System.currentTimeMillis();
inputData();
nTime2 = System.currentTimeMillis();
outputDataAll();
// outputData();
nTime3 = System.currentTimeMillis();
System.out.println("입력경과시간 :" + (nTime2 - nTime1));
System.out.println("출력경과시간 :" + (nTime3 - nTime2));
}
private void inputData()
{
for(int i = 0; i < nMap ; i++)
ht1.put(new Integer(i), i + "ht1");
for(int i = 0; i < nMap ; i++)
ht2.put(new Integer(i), ht1);
}
private void outputDataAll()
{
String strtemp="";
for(int i = 0; i < nMap ; i++)
{
for(int j = 0; j < nMap; j++)
{
strtemp= (String)((Hashtable)ht2.get(new Integer(i))).get(new
Integer(j)) ;
// System.out.print(strtemp + " ");
}
// System.out.println();
}
}
private void outputData()
{
String strtemp = "";
int i = 10, j = 12;
for(; i < 20; i++,j++)
{
strtemp = (String)((Hashtable)ht2.get(new Integer(i))).get(new
Integer(j));
System.out.print(strtemp + " ");
}
}
public static void main(String[] args)
{
if(args.length == 1)
new TestHashTable(args[0]);
System.exit(0);
}
}
|
테이블 구성
| |
콘솔출력x |
콘솔출력o |
| 모든 데이타 |
값/값 |
값/값 |
| 일부 검색 |
값/값 |
값/값 |
이런 식이고요, 안에 들어가는 항목은 값/값 으로 되어있는데
앞의 값은, 데이타를 입력하는데 걸리는 시간이고, 뒤의 값은 데이타를
검색 및 출력하는데 걸리는 시간입니다. 시스템에 출력하는 것이 시간을 많이 잡아먹기 때문에, 순수 access 비교를 위해
따로 분리시켜 두었습니다. 아 이 배려심. 음 1000개 넘게 출력할 때에는 다운도 되네요. (1000개면 2단이므로 1000x1000이니까..음)
ms (1/1000초) 단위입니다.
Vector
30개일 경우
50
100
1000
| 20/171 |
20/(다운) |
| 20/0 |
20/250 |
10000
| 91/378 |
91/(다운) |
| 81/10 |
90/23193 |
Hashtable 과 비교설명
30
50
| 0/70 |
0/480(131) |
| 10/0 |
10/0 |
100
| 10/171 |
10/1372(451) |
| 10/0 |
10/0 |
1000
| 30/2794 |
30/166940(다운) |
| 30/0 |
30/0 |
10000
| 161/141594 |
161/(다운)(다운) |
| 161/10 |
161/10 |
(빨간) 글씨는
String대신 StringBuffer을 사용했을 때의 수치입니다.
Hashtable과 Vector의 테이블을 비교해보시면, (테이블의 첫번째 row를 보세요)
입력에서, Vector가 1.5 배 빠른 속도를 보여주고 있습니다.
출력에서, 콘솔출력을 뺀 순수 access에서 key값을 만들어서 value값을 가져오는 Hashtable보다
훨씬 Vector가 빠릅니다. 비교가 되지 않을 정도군요. 10000 개 데이타에서는 장난이 아닌 속도차를 보여주고 있습니다.
콘솔출력에서는 이상할 정도로 그다지 차이가 나지 않는군요. 제가 코딩 미숙인지? StringBuffer
클래스 이용과 Vector이용에서 데이타 수가 매우 크면 메모리 부족현상이 나타나더군요. 초기용량을 잡든 안잡든... 쩝.
1000 x 1000 = 1,000,000 개 데이타라...(오늘 실험 때문에 다운 5번 먹음.)
그런데 두번째 row 검색부분에서는 Hashtable이 또한 장난이 아닙니다. 10000 단위
데이타에서도 거의 0에 가까운 검색시간을 보여주는군요. 10000개의 Hashtable을 다시 10000개의 Hashtable에
넣었는데도 말입니다. 믿어지지 않을 정도군요.
여러분, 검색할 때 Hashtable남발하세요 ㅜ.ㅜ
부가적으로 빨간 글씨는
private void outputDataAll()
{
String strtemp="";//얘는 이렇게 밖으로 뽑아두셔야지 for문안에 넣으시문 큰일~ 납니다.^_^
for(int i = 0; i < nMap ; i++)
{
for(int j = 0; j < nMap; j++)
{
strtemp= (String)((Vector)vt2.get(i)).get(j) ;
// System.out.print(strtemp + " ");
}
// System.out.println();
}
}
위에서 String에 해당하는 부분을
StringBuffer stb = new StringBuffer(일정값*nMap);
stb.append();
이걸로 대체해서 실험한 결과이며, 예상대로 StringBuffer클래스가 계속 새로운 객체
생성(자바에서 가장 비용이 많이 드는 일이죠.)을 하는 String클래스보다 월등한 성능을 보여주고 있습니다. 한글자만 붙이는데에는
10000개 데이타 실험하면 약 250배 차이난다고 하더군요. 하지만, 데이타 수가 증가할 수록 많은 양의 데이타에 다음
데이타를 append하는 과정에서 String클래스와의 격차가 조금씩 줄어드는 모습을 보여주었으며, 큰 데이타에서는 제 코딩미숙?으로
큰 버퍼용량을 감당하지 못하고 컴까지 다운시키는 용감성을 보여주더군요... 흑흑
물론 개발자의 편의를 위해 API에 추가된 클래스들은 우리가 꼭 필요로 하는 기능 이외에도
이것저것 달라붙어있으니 필요한 기능만 갖추도록 직접 만들어 쓰는 것 보다야 성능이 쳐진다는 건 이미 짐작하시겠죠?
자, 이 실험이 도움이 되셨나 모르겠네요. 그럼 다음 이시간에 -_-V
|