performance - Need to fasten my Java code -
i'm trying solve problem spoj. problem me not actual difficulty of algorithm; performance of java code results in time limit exceeded error.
i heard java notorious slow performance on contest problems compared c/c++; however, language in can code java. thus, asking suggestions make code neater , faster. below solution , source problem.
public class nextpalindrome { public static biginteger secondhalf(biginteger b) { string s = b.tostring(); int n = s.length(); if(n==1){ return b; } string end = s.substring((n + 1) / 2, n); biginteger end = new biginteger(end); return end; } public static biginteger reverse(biginteger b) { string s = b.tostring(); int n = s.length(); string beg = b.tostring(); string reversebeg = ""; while (true) { (int = n - 1; >= 0; i--) { reversebeg = reversebeg + beg.charat(i); } break; } biginteger reverse = new biginteger(reversebeg); return reverse; } public static biginteger firsthalf(biginteger b) { string s = b.tostring(); int n = s.length(); if(n==1){ return b; } string beg = s.substring(0, n / 2); biginteger beg = new biginteger(beg); return beg; } public static biginteger nextpalindrom(biginteger b) { string s = b.tostring(); int n = s.length(); if(n==1){ if(b.equals(9)){ return biginteger.valueof(11); } else { return b.add(biginteger.valueof(1)); } } if (n % 2 == 1&&n>1) { character c = s.charat(n / 2); string c = c.tostring(); biginteger med = new biginteger(c); biginteger beg = firsthalf(b); biginteger end = secondhalf(b); if (reverse(beg).compareto(end) <= 0) { beg.add(biginteger.valueof(1)); if (med.compareto(biginteger.valueof(9)) == 0) { c = '0'; } else { med = med.add(biginteger.valueof(1)); } } string temp = beg.tostring(); string temp1 = reverse(beg).tostring(); c = med.tostring(); string result = temp + c; result = result.concat(temp1); biginteger b = new biginteger(result); return b; } biginteger beg = firsthalf(b); biginteger end = secondhalf(b); if (reverse(beg).compareto(end) <= 0) { beg = beg.add(biginteger.valueof(1)); } string temp = beg.tostring(); string temp1 = reverse(beg).tostring(); string result = temp.concat(temp1); biginteger b = new biginteger(result); return b; } public static void main(string[] args)throws ioexception { bufferedreader in = new bufferedreader(new inputstreamreader(system.in)); string s = in.readline(); int n = integer.parseint(s); (int = 0; < n; i++) { biginteger big = new biginteger(in.readline()); biginteger palindrom = nextpalindrom(big); system.out.println(palindrom); } } }
biginteger used precise calculations, slow. int or long better here.
and there many conversions , string, slow, too.
and slow string operations...
so recommend use int or long , static helper methods of integer or long manipulate raw bits of numbers.
that should lead best performance of program.
Comments
Post a Comment