2.1. 개선사항 ¶
- genKey() 메소드의 성능 개선. qsort2(ProgrammingPerals 참고) 이용.
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" );
}
}
