±è»ó¿íÀÇ Vector, Hashtable Ŭ·¡½º ¼º´É ½ÇÇè ¿Ü

 

¡Ø °­Á¿¡ ´ëÇÑ Áú¹®Àº '¹®ÀÇ°Ô½ÃÆÇ'¿¡¼­ ÇØÁÖ¼¼¿ä.

¸Ó¸®¸» :

¾È³çÇϼ¼¿ä? /^.^/ À̹ø °­Á¿¡¼­´Â ÀÚ·áÀÇ ÀúÀå ¹× °ü¸®¿¡ ¾²ÀÌ´Â ¹è¿­ ƯÈ÷³ª ±× Å©±â°¡ Àý·Î ´Ã¾î³ª´Â µ¿Àû¹è¿­ÀÎ 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°³ÀÏ °æ¿ì

0/0 10/171
0/0 0/10

50

0/10 0/470
0/0 0/10

100

0/10 0/1152
0/0 0/20

1000

20/171 20/(´Ù¿î)
20/0 20/250

10000

91/378 91/(´Ù¿î)
81/10 90/23193

Hashtable °ú ºñ±³¼³¸í

30

0/40 0/210(60)
0/0 0/0

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