U E D R , A S I H C RSS
ZeroWiki

Classify By Anagram/sun

No older revisions available

No older revisions available



1. Step 1

1.1. 결과

  • 실행: java anagram.FindAnagram < 입력파일> 출력파일
  • 테스트환경: P3 1G, 512MB, j2sdk1.4.0, 입력데이터-172823건
  • 결과: 14130 ms


2. Step 2

2.1. 개선사항

2.2. 결과

  • 실행: java anagram.FindAnagram < 입력파일> 출력파일
  • 테스트환경: P3 1G, 512MB, j2sdk1.4.0, 입력데이터-172823건
  • 결과: 10885 ms


3. Step 3

3.1. 개선사항

  • 테스트중 OS 표준입력과 자바에서 직접 파일을 읽는 것과는 별 차이가 없지만, OS 표준 출력이 자바에서 직접 파일출력하는것 보다 상당히 느림을 발견. 자바에서 직접 출력하도록 코드 변경


3.2. 결과

  • 실행: java anagram.FindAnagram 출력파일 < 입력파일
  • 테스트환경: P3 1G, 512MB, j2sdk1.4.0, 입력데이터-172823건
  • 결과: 7270 ms


4. Step 4

4.1. 개선사항

  • String 객체의 생성을 줄임.(대략 300ms 정도 줄어듬) : 마이크로 튜닝으로 넘어갈수록 노력 대비 결과가 크지 않음.
  • Class, method 이름 refactoring

4.2. 결과

  • 실행: java anagram.Anagram 출력파일 < 입력파일
  • 테스트환경: P4 1.8, 512MB, j2sdk1.4.1-b21, 입력데이터-172823건
  • 결과: 3047 ms
  • 분석: 예전에 우스개 소리로, 프로그램을 빠르게 하려면 컴퓨터를 업그레이드 하라더니, 웃을일이 아니다 -_-;

5. To Do

  • 테스트 사양에 독립적인 속도 측정방법 생각
  • 다른 알고리즘, 자료구조 생각요.
  • Profiling
  • 복잡도 구해보기


6. Sources

6.1. 상대시간 비교를 위한 애플릿 


~cpp 
import java.awt.Graphics;
import java.applet.Applet;
import java.io.*; 
import java.util.*; 

public class PowerTest extends Applet 
{
	long elapsed = 0;
	AnagramTest anagram;
	
	
	public void start()
	{
		elapsed = System.currentTimeMillis();
		InputStream in = null;
		anagram = new AnagramTest();
		for( int i=0; i<10000; i++ ) {
			anagram.add( "test" );
			anagram.add( "aah" );
			anagram.add( "aahed" );
			anagram.add( "aahing" );
			anagram.add( "aahs" );
			anagram.add( "aal" );
			anagram.add( "aalii" );
			anagram.add( "aaliis" );
			anagram.add( "aals" );
			anagram.add( "aardvark" );
			anagram.add( "aardvarks" );
			anagram.add( "aardwolf" );
			anagram.add( "aardwolves" );
			anagram.add( "aargh" );
			anagram.add( "aarrgh" );
			anagram.add( "aarrghh" );
			anagram.add( "aas" );
			anagram.add( "aasvogel" );
			anagram.add( "aasvogels" );
			anagram.add( "ab" );
			anagram.add( "aba" );
			anagram.add( "abaca" );
			anagram.add( "abacas" );
			anagram.add( "abaci" );
			anagram.add( "aback" );
		}
		elapsed = System.currentTimeMillis() - elapsed;
		repaint();
	}
	
	
	public void paint( Graphics g )
	{
		g.drawString( "JVM info:", 10, 20 );
		g.drawString( "....vendor : " + System.getProperty( "java.vm.vendor"), 10, 35 );
		g.drawString( "....version: " + System.getProperty( "java.vm.version"), 10, 50 );
		g.drawString( "....name: " + System.getProperty( "java.vm.name"), 10, 65 );
		if( elapsed != 0 )
			g.drawString( "Estimated power: " + String.valueOf(elapsed), 10, 90 );
	}
}

class AnagramTest   
{ 
        private Hashtable result = new Hashtable();  
        private byte [] seq; 
          
        public AnagramTest()
        {  
        }  
          
          
        public void add( String str )  
        {  
                List list;  
                Object key = genKey( str );  
                Object value = result.get( key );  
                if( value == null ) {  
                        list = new ArrayList();  
                        result.put( key, list );  
                }  
                else  
                        list = (ArrayList)value;  
                list.add( str );  
        }  
 
          
        private Object genKey( String str )  
        { 
                seq = str.getBytes(); 
                qsort2( 0, seq.length-1 ); 
                return java.nio.ByteBuffer.wrap( seq ); 
        }  
 
 
        private void swap( int i, int j ) 
        {        
                byte t = seq[i]; 
                seq[i] = seq[j]; 
                seq[j] = t; 
        } 
         
         
        private void qsort2( int l, int u ) 
        {        
                if( l >= u ) return; 
                int i = l; 
                int j = u+1; 
                while( true ) { 
                        do i++; while (i <= u && seq[i] < seq[l]); 
                        do j--; while (seq[j] > seq[l]); 
                        if( i > j )     break; 
                        swap( i, j ); 
                } 
                swap( l, j ); 
                qsort2( l, j-1 ); 
                qsort2( j+1, u ); 
        } 
}

6.2. Step 1 


~cpp 
package anagram; 
 
import java.io.*; 
import java.util.*; 
 
public class FindAnagram  
{ 
        Hashtable result = new Hashtable(); 
         
        public FindAnagram( InputStream in ) throws Exception 
        { 
                BufferedReader reader = new BufferedReader( new InputStreamReader( in )); 
                String readLine; 
                 
                while( (readLine=reader.readLine()) != null ) { 
                        putTable( readLine.trim() ); 
                } 
        } 
         
         
        private void putTable( String str ) 
        { 
                List list; 
                Object key = genKey( str ); 
                Object value = result.get( key ); 
                if( value == null ) { 
                        list = new ArrayList(); 
                        result.put( key, list ); 
                } 
                else 
                        list = (ArrayList)value; 
                         
                list.add( str ); 
        } 
         
         
        private Object genKey( String str ) 
        { 
                Hashtable table = new Hashtable(); 
                Object value; 
                String ch; 
                for( int i=0; i<str.length(); i++ ) { 
                        ch = String.valueOf( str.charAt( i )); 
                        value = table.get( ch ); 
                        if( value == null ) value = "0"; 
                        table.put( ch, String.valueOf(Integer.parseInt((String)value)+1)); 
                } 
                
                StringBuffer keyBuf = new StringBuffer( table.size()*2 );
                Object keyElement;
                for( Enumeration e=table.keys(); e.hasMoreElements(); ) {
                	keyElement = e.nextElement();
                	keyBuf.append( keyElement );
                	keyBuf.append( table.get( keyElement ));
                }
                
                return keyBuf.toString(); 
        } 
 
 
 
        public void print() 
        { 
                List list; 
                for( Enumeration e=result.elements(); e.hasMoreElements(); ) { 
                        list = (ArrayList)e.nextElement(); 
                        for( Iterator item=list.iterator(); item.hasNext(); ) { 
                                System.out.print( item.next() ); 
                                System.out.print( " " ); 
                        } 
                        System.out.println(); 
                } 
                 
        } 
         
 
        public static void main(String[] args) throws Exception 
        { 
                long start = System.currentTimeMillis();
                FindAnagram anagram = new FindAnagram( System.in ); 
                long end = System.currentTimeMillis();
                anagram.print(); 
                long printEnd = System.currentTimeMillis();
                System.out.println( "수행시간: " + (end-start) + " ms" );
                System.out.println( "수행시간(print): " + (printEnd-start) + " ms" );
        } 
}

6.3. Step 2 


~cpp 
package anagram; 
 
import java.io.*; 
import java.util.*; 
 
public class FindAnagram  
{
	private Hashtable result = new Hashtable(); 
	private byte [] seq;
         
	public FindAnagram( InputStream in ) throws Exception 
	{ 
		BufferedReader reader = new BufferedReader( new InputStreamReader( in )); 
		String readLine; 
                 
		while( (readLine=reader.readLine()) != null )
			putTable( readLine.trim() ); 
	} 
         
         
	private void putTable( String str ) 
	{ 
		List list; 
		Object key = genKey( str ); 
		Object value = result.get( key ); 
		if( value == null ) { 
			list = new ArrayList(); 
			result.put( key, list ); 
		} 
		else 
			list = (ArrayList)value; 
		list.add( str ); 
	} 

         
	private Object genKey( String str ) 
	{
		seq = str.getBytes();
		qsort2( 0, seq.length-1 );
		return java.nio.ByteBuffer.wrap( seq );
	} 


	private void swap( int i, int j )
	{	
		byte t = seq[i];
		seq[i] = seq[j];
		seq[j] = t;
	}
	
	
	private void qsort2( int l, int u )
	{	
		if( l >= u ) return;
		int i = l;
		int j = u+1;
		while( true ) {
			do i++; while (i <= u && seq[i] < seq[l]);
			do j--; while (seq[j] > seq[l]);
			if( i > j )	break;
			swap( i, j );
		}
		swap( l, j );
		qsort2( l, j-1 );
		qsort2( j+1, u );
	}
        
 
    public void print( PrintStream out ) 
    { 
        List list; 
        for( Enumeration e=result.elements(); e.hasMoreElements(); ) { 
            list = (ArrayList)e.nextElement(); 
            for( Iterator item=list.iterator(); item.hasNext(); ) { 
               out.print( item.next() ); 
               out.print( " " ); 
            } 
            out.println(); 
        } 
    }

 
    public static void main(String[] args) throws Exception 
    { 
	long start = System.currentTimeMillis();
	FindAnagram anagram = new FindAnagram( System.in ); 
	long end = System.currentTimeMillis();
	anagram.print( System.out ); 
	long printEnd = System.currentTimeMillis();
	System.out.println( "수행시간: " + (end-start) + " ms" );
	System.out.println( "수행시간(print): " + (printEnd-start) + " ms" );
    } 
}

6.4. Step 3 


~cpp 
package anagram; 
 
import java.io.*; 
import java.util.*; 
 
public class FindAnagram  
{
	private Hashtable result = new Hashtable(); 
	private byte [] seq;
         
	public FindAnagram( InputStream in ) throws Exception 
	{ 
		BufferedReader reader = new BufferedReader( new InputStreamReader( in )); 
		String readLine; 
                 
		while( (readLine=reader.readLine()) != null )
			putTable( readLine.trim() ); 
	} 
         
         
	private void putTable( String str ) 
	{ 
		List list; 
		Object key = genKey( str ); 
		Object value = result.get( key ); 
		if( value == null ) { 
			list = new ArrayList(); 
			result.put( key, list ); 
		} 
		else 
			list = (List)value; 
		list.add( str ); 
	} 

         
	private Object genKey( String str ) 
	{
		seq = str.getBytes();
		qsort2( 0, seq.length-1 );
		return java.nio.ByteBuffer.wrap( seq );
	} 


	private void swap( int i, int j )
	{	
		byte t = seq[i];
		seq[i] = seq[j];
		seq[j] = t;
	}
	
	
	private void qsort2( int l, int u )
	{	
		if( l >= u ) return;
		int i = l;
		int j = u+1;
		while( true ) {
			do i++; while (i <= u && seq[i] < seq[l]);
			do j--; while (seq[j] > seq[l]);
			if( i > j )	break;
			swap( i, j );
		}
		swap( l, j );
		qsort2( l, j-1 );
		qsort2( j+1, u );
	}
        
 
    public void print( PrintStream out ) 
    { 
        List list; 
        for( Enumeration e=result.elements(); e.hasMoreElements(); ) { 
            list = (List)e.nextElement(); 
            for( Iterator item=list.iterator(); item.hasNext(); ) { 
               out.print( item.next() ); 
               out.print( " " ); 
            } 
            out.println(); 
        } 
    }

 
    public static void main( String[] args ) throws Exception 
    {
    	if( args.length != 1 ) {
    		System.out.println( "usage: java anagram.FindAnagram out_file < input_file" );
    		System.exit( -1 );
    	}
		long start = System.currentTimeMillis();
		FindAnagram anagram = new FindAnagram( System.in ); 
		long end = System.currentTimeMillis();

		BufferedOutputStream out = null;
		try {
			out = new BufferedOutputStream( new FileOutputStream( args[0] ));
			anagram.print( new PrintStream( out ));
		}
		finally {
			if( out != null ) try { out.close(); } catch( Exception e ) {}
		}
		long printEnd = System.currentTimeMillis();
		System.out.println( "수행시간: " + (end-start) + " ms" );
		System.out.println( "수행시간(print): " + (printEnd-start) + " ms" );
    } 
}


6.5. Step 4 


~cpp 
package anagram; 
 
import java.io.*; 
import java.util.*; 
import java.nio.*;
 
public class Anagram  
{
	private Hashtable result = new Hashtable( 512 ); 
    
    
    public Anagram() {}
    

	public Anagram( InputStream in ) throws Exception 
	{ 
		BufferedReader reader = new BufferedReader( new InputStreamReader( in )); 
		String readLine; 
                 
		while( (readLine=reader.readLine()) != null )
			if( readLine.length() != 0 )
				add( readLine );
	} 
         
         
	public void add( String str ) 
	{ 
		ByteBuffer key = ByteBuffer.wrap( str.getBytes() );
		qsort2( key, 0, key.capacity()-1 );

		Object value = result.get( key ); 
		if( value == null ) { 
			List list = new ArrayList();
			result.put( key, list ); 
			list.add( str );
		} 
		else 
			((List)value).add(str);
	} 

         
	private void swap( ByteBuffer buf, int i, int j )
	{	
		byte t = buf.get(i);
		buf.put( i, buf.get(j));
		buf.put( j, t );
	}
	
	
	private void qsort2( ByteBuffer buf, int l, int u )
	{	
		if( l >= u ) return;
		int i = l;
		int j = u+1;
		while( true ) {
			do i++; while (i <= u && buf.get(i) < buf.get(l));
			do j--; while (buf.get(j) > buf.get(l));
			if( i > j )	break;
			swap( buf, i, j );
		}
		swap( buf, l, j );
		qsort2( buf, l, j-1 );
		qsort2( buf, j+1, u );
	}
        
 
    public void print( PrintStream out ) 
    { 
        List list; 
        for( Enumeration e=result.elements(); e.hasMoreElements(); ) { 
            list = (List)e.nextElement(); 
            for( Iterator item=list.iterator(); item.hasNext(); ) { 
               out.print( item.next() + " " ); 
            } 
            out.println();
        } 
    }

 
    public static void main( String[] args ) throws Exception 
    {
		if( args.length != 1 ) {
			System.out.println( "usage: java anagram.FindAnagram out_file < input_file" );
			System.exit( -1 );
		}
		long start = System.currentTimeMillis();
		Anagram anagram = new Anagram( System.in ); 

		BufferedOutputStream out = null;
		try {
			out = new BufferedOutputStream( new FileOutputStream( args[0] ));
			anagram.print( new PrintStream( out ));
		}
		finally {
			if( out != null ) try { out.close(); } catch( Exception e ) {}
		}
		long end = System.currentTimeMillis();
		System.out.println( "Elapsed time: " + (end-start) + " ms" );
    } 
}
Valid XHTML 1.0! Valid CSS! powered by MoniWiki
last modified 2021-02-07 05:22:54
Processing time 0.0354 sec