Jump to content




Recent Status Updates

  • Photo
      15 Nov
    duzamucha

    Hi, I am final year Interior Design Student from University of Huddersfield. I am currently working on my final major project which is going to be linked to coding. I was hoping that you could help me with my research. I have prepared a short survey, it would be a massive help if you could fill it in for me. It takes less than 2 minutes to complete, I promise. Here is the link: https://www.surveymonkey.com/s/73XLJKK Thank you so much in advance!

View All Updates

Developed by TechBiz Xccelerator
Photo
- - - - -

Speed Up Algorithm


  • Please log in to reply
6 replies to this topic

#1 XAW

XAW

    CC Lurker

  • Just Joined
  • Pip
  • 1 posts

Posted 06 April 2012 - 08:24 AM

Hi. I'm trying to do Sphere Online Judge (SPOJ) - Problem DICTSUB

But I'm getting timeout..So i need to speed up my algorithm. How improve my code or write new better code?

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

class Main {

	public static void main (String[] args) throws IOException {
		BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
		int cases=0;
		int cases2=0;
		String slowo=" ";
		String word=" ";
		int p=0;
		cases=Integer.parseInt(br.readLine());
		for(int i=0; i<cases; i++) {
			if(slowo!=null && slowo.length()>0) {
			slowo=br.readLine();
			p=slowo.indexOf(" ");
			cases2=Integer.parseInt(slowo.substring(0,p));
			word=slowo.substring(p+1);
			for(int k=0; k<cases2; k++) {
			slowo=br.readLine();
			slowo=decode(slowo);
			int pom=0;
			int x=0;
			while(pom!=-1 && x<slowo.length()) {	
				pom=word.indexOf(slowo.charAt(x),pom);
				x++;
			}
			if(pom!=-1) System.out.println("YES");
			else System.out.println("NO");
			
			}
			}
		System.out.print("\r");
		}
	}
	
	public static String decode(String W) {
		char[] array=W.toCharArray();
		StringBuilder ret=new StringBuilder("");
		int pom=0;
		for(int i=0; i<array.length; i++)
			if(i%2==0) pom=array[i];
			else for(int k=0; k<pom; k++) ret.append(array[i]);
		return ret.toString();
	}
	
}

  • 0

#2 Norm

Norm

    CC Addict

  • Senior Member
  • PipPipPipPipPip
  • 397 posts
  • Location:Eastern Florida
  • Programming Language:Java, C++, Assembly

Posted 06 April 2012 - 10:15 AM

One way to seed up the code is not to read from System.in. Users are too slow entering data.

Have you tried profiling the execution of the code to see where it is spending the time? Use the java -Xprof option.
  • 0

#3 lethalwire

lethalwire

    while(false){ ... }

  • Senior Member
  • PipPipPipPipPipPip
  • 762 posts
  • Programming Language:Java, PHP
  • Learning:Java, PHP

Posted 06 April 2012 - 10:50 AM

One way to seed up the code is not to read from System.in. Users are too slow entering data.

Have you tried profiling the execution of the code to see where it is spending the time? Use the java -Xprof option.


A server will probably be feeding input to standardin.
  • 0

#4 gregwarner

gregwarner

    Obi Wan of Programming

  • Expert Member
  • PipPipPipPipPipPipPip
  • 1,584 posts
  • Location:Arkansas
  • Programming Language:C, Java, C++, C#, PHP, Transact-SQL

Posted 06 April 2012 - 12:59 PM

I would suggest you speed up your code by specifying the initial capacity of the StringBuilder in your 'decode' method.

The constructor StringBuilder(String str) allocates an array that is 16 plus the length of 'str' characters long. Each time you append more characters than it can hold, StringBuilder has to allocate a whole new array in memory and copy the contents over. This can be very slow. If you know ahead of time the maximum length of each string you're going to be building, you can specify this when creating the StringBuilder:

new StringBuilder(1024); // Creates a StringBuilder with an initial capacity of 1024.

This way, you can append up to 1024 characters onto this StringBuilder and it will be very fast, because it doesn't have to bother with multiple reallocations and copies every time the buffer fills up.
  • 0

ti-99-sig.png
Hofstadter's Law: It always takes longer than you expect, even when you take into account Hofstadter's Law.
– Douglas Hofstadter, Gödel, Escher, Bach: An Eternal Golden Braid


#5 Norm

Norm

    CC Addict

  • Senior Member
  • PipPipPipPipPip
  • 397 posts
  • Location:Eastern Florida
  • Programming Language:Java, C++, Assembly

Posted 06 April 2012 - 04:01 PM

Cross posted at: http://www.java-foru...-algorithm.html
  • 0

#6 Norm

Norm

    CC Addict

  • Senior Member
  • PipPipPipPipPip
  • 397 posts
  • Location:Eastern Florida
  • Programming Language:Java, C++, Assembly

Posted 07 April 2012 - 12:40 PM

You need to debug your code to see what it is doing. Add some printlns to print out the values of the variables as they are given values and used The print out will show you where the problems are.
  • 0

#7 thechef

thechef

    CC Resident

  • Advanced Member
  • PipPipPipPip
  • 73 posts

Posted 08 April 2012 - 09:18 AM

I'd say 99% of timeout errors are due to an insufficient algorithm not subtleties in the code. To speed this up, you need to look at your while loop. It looks at every single letter of word "T" for every word "W", making it an order N-squared algorithm. Think about parsing word "T" into a tree structure that alphabetizes its nodes. Then, for each letter in word "W", you can easily find if the letter is in "T". Here is an example for a T of "AARDVARK":

A -> A -> A -> K
A -> A -> A -> R
A -> A -> D ...
A -> A -> K ...
A -> A -> R ...
A -> A -> V ...
A -> D -> A ...
A -> D -> K
A -> D -> R ...
A -> D -> V ...
A -> K
A -> R ...
A -> V ...

I'll let you fill in the rest. Now, finding a letter is order log(N) because the letters are ordered, and your algorithm takes almost half as much time.

I hope that makes sense, and happy coding!
  • 1
I don't document code. If it was hard to write, it should be hard to read ;)




Powered by binpress