Anyone knows how to speed up JAVA a little bit?

[.pandre.]

Hi

I'm getting tired of getting TLE in some problems!

I aways try to optimize my code, but in some problems it is just not enough... some examples are problems number 498 (Polly the polynomial) and 583 (Prime Factors) - I think I have the right algorithm, even with some optimizations, but it's still slow...

Can anyone help me out?

[java][/java]

[Maniac]

Hi,

I'm sorry to disappoint you, but there are lots of problems which can't be solved with Java just because Java is some factor slower than the other languages (and the admins don't take this into account).

My experience is that Java is 2-10 times slower than C for example (depending on the problem) so by looking at the running times of other accepted solutions you can see wether a Java solution can be found or not. If the best solution takes 2 secs or more, don't even try solving it in Java! I've seen a lot of problems where coding the same algorithm in C++ gives AC whereas the Java version gives TLE. So look at the running times of accepted solutions and then decide whether you can use Java to solve the problem.

It's unfair, I know.....

[randomtaiwanese]

it sucks....
in some other OJs... or online contests, they give java 5x the time than other programs...
and they scale the time for java

btw... did anyone ever got 0.000 runtime for java in the OJ???

my shortest code submitted to OJ follows:

[java]class Main
{
public static void main(String[] args)
{
System.out.println("The 1500'th ugly number is *********.");
}
}[/java]

and it took 0:00.004 to run...

[randomtaiwanese]

btw me and my friend thought it would be nice if we can improve the efficency of the standard input that the OJ provided
http://acm.uva.es/p/data/p100.java.html
[java] static String ReadLn (int maxLg) // utility function to read from stdin
{
byte lin[] = new byte [maxLg];
int lg = 0, car = -1;
String line = "";

try
{
while (lg < maxLg)
{
car = System.in.read();
if ((car < 0) || (car == '\n')) break;
lin [lg++] += car;
}
}
catch (IOException e)
{
return (null);
}

if ((car < 0) && (lg == 0)) return (null); // eof
return (new String (lin, 0, lg));
}[/java]

[Andrew Neitsch]

Use C.

[TigerC10]

I don't mean to revive an old topic, but I have some stuff to say.

I'm sorry to disappoint you, but there are lots of problems which can't be solved with Java just because Java is some factor slower than the other languages (and the admins don't take this into account).

In some cases Java is faster than C++. I believe foreach is an example of one. Though, that might be the case for the current Java and not the outdated one that the online judge is running.

Also, you have a problem with other languages that you don't have with Java - and that is you have to compile the other languages for specific processor types, or operating systems... Java isn't platform dependant - so compile once and go. Honestly, people overlook that as a real problem.



But now to the topic at hand (from two years ago).

If you want to speed up your program, one way is to use bit shifting instead of multiplying or dividing by powers of 2. You'd especially want to do it with dividing!

For example
int result1 = 16 / 2;
int result2 = 16 /4
int result3 = 16 * 2;
becomes
int result1 = 16>>1;
int result2 = 16>>2;
int result3 = 16<<1;


In problems that deal with odds and evens, since the modulus operator is pretty much just like the divide operator when it comes to time, bitwise comparisons help out big time!

For example:
if( someInt % 2 !=0) //if odd
becomes
if( (someInt & 1) == 1) //if odd


Also, if you're going to be doing lots of repetative calculations, you might want to look at caching your results. In extreme cases, you'd actually lose time - but if you have numbers that you've already calculated before there should be no reason to calculate them again if they're frequent (prime example is the 3n+1 - problem number 100).

[MaVa]

I code only java, shure it is a pain in the ... sometimes.
but in real competitions it is a good choice.

Java is not that much slower on input and output, but you must take care!!

1. using System.out.print*() will make the stream flush, which takes time, by using System.out.write() you can save time, and gain work.
(try on 10189)

2. readLn() metods given as examle on the page is slow, because when you make an array such as byte[] java must make shure all bytes are decleared to right initial value, as opposed to C. Using a small array speed thing up.

3. Integer.parseInt() is not optimized either, to many checks for invalid arguments. On this site you can rely on input-format!!
(if it says positive numbers, dont check for minus signs)

I dont know how to best test the difference in input speed, but even on problems with lots of input I think it is possible to make fast java programs.
There is indeed some difference in I/O-speed but not 10x for shure.

Good Luck
MaVa

[TigerC10]

Yeah yeah! Great tips! And hooray for topic necromancy!

Here's a couple more:

Iterating through loops has the following structure in many cases:

for(int k=0; k<someVar.length(); k++)

Check it out, you execute the k=0 command, then you execute the comparison as well as the length method as many times as you have n variables to loop through. Finally you increment k n+1 times. This all leads to a lot of executions. To make it go faster:

int length = someVar.length();
for(int k=0; k<length; k++)

Taking the method call to length() out will increase the loop's speed slightly. However, you're still calling length from the variable table n times. So try it this way instead:

int length = someVar.length();
for(int k=length; k>0; --k)

This will iterate backwards. What that means, is that now you won't be pulling up 2 variables in the comparison. You'll only compare one variable to 0. Although, it isn't necessarily that much more beneficial to call length outside of the loop statement now since your call to length is only executed once.


Now consider iterating through an array. A lot of time is wasted checking to make sure that you're not out of bounds at every step. I like to do something like this:

try{
for(int k=0; ; k++)
//Do something with array[k]
}
catch(ArrayOutOfBoundsException e){}

This way, you don't even need to compare anymore. All you do is find out when the out of bounds occurs and catch it - which by the way, this is REALLY bad programming practice... I highly recommend only using it for these purposes.


Who else has optimizing techniques?

[MaVa]

I aways try to optimize my code, but in some problems it is just not enough... some examples are problems number 498 (Polly the polynomial) and 583 (Prime Factors)
[java][/java]

I tryed using all the tricks in this post to solve 498, and got AC after 1.2sec.
So you should have a fair chance of solving this problem.

But you need some fancy way of reading and printing.
Read byte for byte and parse the longs your self.
Same for printing, find each digit in the answer, store in array, and print using System.out.write()

Good Luck

[PVM]

having skimmed through all the replies, i found no easier solution than using C. I also tried with java for my first problem and voila!. Time Limit Exceed.
Actually, it will take me less time to rewrite my code in C/C++ than making my java code faster.

so GO FOR C.. atleast for 24 hours judge.