•

Check out our Community Blogs

Register and join over 40,000 other developers!

### Recent Blog Entries

• phi

I love this community !

• JackJames

hi i am jack i am seo expert jack james would love you to read new post

# Speed Up Algorithm

6 replies to this topic

### #1 XAW

XAW

CC Lurker

• Just Joined
• 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;

class Main {

public static void main (String[] args) throws IOException {
int cases=0;
int cases2=0;
String slowo=" ";
String word=" ";
int p=0;
for(int i=0; i<cases; i++) {
if(slowo!=null && slowo.length()>0) {
p=slowo.indexOf(" ");
cases2=Integer.parseInt(slowo.substring(0,p));
word=slowo.substring(p+1);
for(int k=0; k<cases2; k++) {
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

• Senior Member
• 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
• 766 posts
• Programming Language:C, Java, PHP, JavaScript
• Learning: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
• 1586 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

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

• Senior Member
• 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

• Senior Member
• 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

• 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

Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download