Maintenance script: Repair batch-0001 pages from live compare

2026-03-26T23:56:04Z

Repair batch-0001 pages from live compare

← Older revision		Revision as of 23:56, 26 March 2026
Line 42:		Line 42:

	== To Do ==		== To Do ==
	* ~~[[HTML(<~~STRIKE~~>)]]~~테스트 사양에 독립적인 속도 측정방법 생각~~[[HTML(<~~/STRIKE~~>)]]~~		* <STRIKE>테스트 사양에 독립적인 속도 측정방법 생각</STRIKE>
	* 다른 알고리즘, 자료구조 생각요.		* 다른 알고리즘, 자료구조 생각요.
	* Profiling		* Profiling
Line 112:		Line 112:
	{		{
	private Hashtable result = new Hashtable();		private Hashtable result = new Hashtable();
	private byte [] seq;		private byte [] seq;

	public AnagramTest()		public AnagramTest()
Line 144:		Line 144:
	private void swap( int i, int j )		private void swap( int i, int j )
	{		{
	byte t = seq[i];		byte t = seq[i];
	seq[i] = seq[j];		seq[i] = seq[j];
	seq[j] = t;		seq[j] = t;
	}		}

Line 156:		Line 156:
	int j = u+1;		int j = u+1;
	while( true ) {		while( true ) {
	do i++; while (i <= u && seq[i] < seq[l]);		do i++; while (i <= u && seq[i] < seq[l]);
	do j--; while (seq[j] > seq[l]);		do j--; while (seq[j] > seq[l]);
	if( i > j ) break;		if( i > j ) break;
	swap( i, j );		swap( i, j );
Line 244:		Line 244:


	public static void main(String[] args) throws Exception		public static void main(String[] args) throws Exception
	{		{
	long start = System.currentTimeMillis();		long start = System.currentTimeMillis();
Line 265:		Line 265:
	{		{
	private Hashtable result = new Hashtable();		private Hashtable result = new Hashtable();
	private byte [] seq;		private byte [] seq;

	public FindAnagram( InputStream in ) throws Exception		public FindAnagram( InputStream in ) throws Exception
Line 302:		Line 302:
	private void swap( int i, int j )		private void swap( int i, int j )
	{		{
	byte t = seq[i];		byte t = seq[i];
	seq[i] = seq[j];		seq[i] = seq[j];
	seq[j] = t;		seq[j] = t;
	}		}

Line 314:		Line 314:
	int j = u+1;		int j = u+1;
	while( true ) {		while( true ) {
	do i++; while (i <= u && seq[i] < seq[l]);		do i++; while (i <= u && seq[i] < seq[l]);
	do j--; while (seq[j] > seq[l]);		do j--; while (seq[j] > seq[l]);
	if( i > j ) break;		if( i > j ) break;
	swap( i, j );		swap( i, j );
Line 339:		Line 339:


	public static void main(String[] args) throws Exception		public static void main(String[] args) throws Exception
	{		{
	long start = System.currentTimeMillis();		long start = System.currentTimeMillis();
Line 360:		Line 360:
	{		{
	private Hashtable result = new Hashtable();		private Hashtable result = new Hashtable();
	private byte [] seq;		private byte [] seq;

	public FindAnagram( InputStream in ) throws Exception		public FindAnagram( InputStream in ) throws Exception
Line 397:		Line 397:
	private void swap( int i, int j )		private void swap( int i, int j )
	{		{
	byte t = seq[i];		byte t = seq[i];
	seq[i] = seq[j];		seq[i] = seq[j];
	seq[j] = t;		seq[j] = t;
	}		}

Line 409:		Line 409:
	int j = u+1;		int j = u+1;
	while( true ) {		while( true ) {
	do i++; while (i <= u && seq[i] < seq[l]);		do i++; while (i <= u && seq[i] < seq[l]);
	do j--; while (seq[j] > seq[l]);		do j--; while (seq[j] > seq[l]);
	if( i > j ) break;		if( i > j ) break;
	swap( i, j );		swap( i, j );
Line 434:		Line 434:


	public static void main( String[] args ) throws Exception		public static void main( String[] args ) throws Exception
	{		{
	if( args.length != 1 ) {		if( args.length != 1 ) {
Line 446:		Line 446:
	BufferedOutputStream out = null;		BufferedOutputStream out = null;
	try {		try {
	out = new BufferedOutputStream( new FileOutputStream( args[0] ));		out = new BufferedOutputStream( new FileOutputStream( args[0] ));
	anagram.print( new PrintStream( out ));		anagram.print( new PrintStream( out ));
	}		}
Line 539:		Line 539:


	public static void main( String[] args ) throws Exception		public static void main( String[] args ) throws Exception
	{		{
	if( args.length != 1 ) {		if( args.length != 1 ) {
Line 550:		Line 550:
	BufferedOutputStream out = null;		BufferedOutputStream out = null;
	try {		try {
	out = new BufferedOutputStream( new FileOutputStream( args[0] ));		out = new BufferedOutputStream( new FileOutputStream( args[0] ));
	anagram.print( new PrintStream( out ));		anagram.print( new PrintStream( out ));
	}		}

Maintenance script: Repair MoniWiki formatting after migration

2026-03-26T14:01:36Z

Repair MoniWiki formatting after migration

← Older revision		Revision as of 14:01, 26 March 2026
Line 562:		Line 562:
	----		----
	ClassifyByAnagram		ClassifyByAnagram

imported>Unknown at 05:22, 7 February 2021

2021-02-07T05:22:54Z

New page

__TOC__

----
== Step 1 ==
=== 결과 ===
** 실행: java anagram.FindAnagram < 입력파일> 출력파일
** 테스트환경: P3 1G, 512MB, j2sdk1.4.0, 입력데이터-[http://zeropage.org/pds/2002104113433/word.lst 172823건]
** 결과: 14130 ms

== Step 2 ==
=== 개선사항 ===
** genKey() 메소드의 성능 개선. qsort2([http://www.cs.bell-labs.com/cm/cs/pearls/sortanim.html ProgrammingPerals 참고]) 이용.

=== 결과 ===
** 실행: java anagram.FindAnagram < 입력파일> 출력파일
** 테스트환경: P3 1G, 512MB, j2sdk1.4.0, 입력데이터-[http://zeropage.org/pds/2002104113433/word.lst 172823건]
** 결과: 10885 ms

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

=== 결과 ===
** 실행: java anagram.FindAnagram 출력파일 < 입력파일
** 테스트환경: P3 1G, 512MB, j2sdk1.4.0, 입력데이터-[http://zeropage.org/pds/2002104113433/word.lst 172823건]
** 결과: 7270 ms

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

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

== To Do ==
* [[HTML(<STRIKE>)]]테스트 사양에 독립적인 속도 측정방법 생각[[HTML(</STRIKE>)]]
* 다른 알고리즘, 자료구조 생각요.
* Profiling
* 복잡도 구해보기

== Sources ==
=== 상대시간 비교를 위한 애플릿 ===
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 );
}
}

=== Step 1 ===
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" );
}
}

=== Step 2 ===
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" );
}
}

=== Step 3 ===
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" );
}
}

=== Step 4 ===
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" );
}
}
----
ClassifyByAnagram

ClassifyByAnagram/sun - Revision history

Maintenance script: Repair batch-0001 pages from live compare

Maintenance script: Repair MoniWiki formatting after migration

imported>Unknown at 05:22, 7 February 2021