6
\$\begingroup\$

I was solving a problem on codechef (online judge and contest organizer). I was writing my code in Java and was getting TLE at last testcase where as I wrote the same code in C++ and it was accepted. Now I know C++ is faster then java but If anyone could help me optimize my Java code ?

Here is the question

Chef has finished his freshman year in college. As a present, his parents gave him a new problem to solve: Chef has to fill a K x K square grid of integers in a certain way. Let us say that such a grid is valid if:

  • Each cell contains an integer from 1 and K (inclusive).
  • No integer appears twice in the same row or the same column.

Let F(K) be maximum possible distance between the center of the square and the closest cell that contains 1, among all possible squares with the side length K.

Here, we use the following notions:

  • The distance between cell (x, y) and (i, j) is equal to |x-i|+|y-j|.
  • The center of a K × K square is cell ((K+1)/2, (K+1)/2) for odd K.

Input

The first line of input contains a single integer T denoting the number of test cases. Each test case consists of a single line containing a single odd integer K.

Output

For each test case, print K lines each consisting of K space separated integers giving some square grid where the distance from the center of the grid to the nearest 1 is exactly F(K). If there's more than 1 possible answer output any of them.

Constraints

Ki is odd.

Subtask #1 (10 points):

1 ≤ T ≤ 50
1 ≤ Ki ≤ 5

Subtask #1 (90 points):

1 ≤ T ≤ 10
1 ≤ Ki < 400

Example

Input:

2
1
3

Output:

1
3 2 1
1 3 2
2 1 3

Here is my code in Java

import java.util.*;
import java.io.*;

public class Main {       
    public static void main(String[] args) throws IOException{
        BufferedReader sc = new BufferedReader(new InputStreamReader(System.in));
        int t = Integer.parseInt(sc.readLine());
        while(t-- > 0){
            int n = Integer.parseInt(sc.readLine());        
            int center = (n + 1)/2 ;                
            for(int i = 0; i < n; i++){
                int temp = center;
                for(int j = 0; j < n; j++){
                    System.out.print(temp+" "); 
                    temp++;
                    if(temp > n)
                        temp = 1;                                               
                }                   
                center--;
                if(center < 1)
                    center = n;
                System.out.printf("%n");
            }
        }    
    }   
}

Here is my code in c++

#include <iostream>
using namespace std;

int main(void){
    int t;
    cin>> t;
    while(t--){
        int n;
        cin>>n;
        int center = (n + 1)/2 ;                
        for(int i = 0; i < n; i++){
            int temp = center;
            for(int j = 0; j < n; j++){
                cout<<temp<<" "; 
                temp++;
                if(temp > n)
                    temp = 1;                                               
            }                   
            center--;
            if(center < 1)
                center = n;
            cout<<"\n";
        }
   }    
   return 0;
}
\$\endgroup\$
  • \$\begingroup\$ add: std::ios_base::sync_with_stdio(false);std::cin.tie(nullptr); At the beginning of main() to make it go faster. \$\endgroup\$ – Martin York Nov 9 '16 at 17:03
  • \$\begingroup\$ This works in java? I am getting a compilation error . \$\endgroup\$ – lord_ozb Nov 9 '16 at 20:01
  • \$\begingroup\$ No: That is for C++ \$\endgroup\$ – Martin York Nov 10 '16 at 16:37
6
\$\begingroup\$

To me the implementations look identical. But one thing jumps out at me:

If n is big then you will do a lot of string concatenations here: System.out.print(temp+" "); which may look inconspicuous but if n=399, then you will do around 160k useless string concatenations. Try to use a StringBuilder and build all your output into it and then dump it in one go when you're done. Or simply change to:

System.out.print(temp);
System.out.print(' ');

Also I think System.out.format("%n"); is a bit odd why not simply do System.out.println();?

And temp is a really bad variable name. I suggest you change it.

\$\endgroup\$
  • \$\begingroup\$ I read on stackoverflow that System.out.printf("%n); is faster than System.out.println();. But I am not still sure about it. Anyways thanks a lot for your answer! :) \$\endgroup\$ – lord_ozb Nov 8 '16 at 19:44
  • \$\begingroup\$ Instead of printing everything I used StringBuilder and then kept on appending everything and then at last printed a single string and it managed to get accepted. Finally I can sleep in peace . \$\endgroup\$ – lord_ozb Nov 8 '16 at 20:06
9
\$\begingroup\$

My first observation was the same as @EmilyL.'s: that you're performing unneeded string concatenations. Upon investigation, however, it turned out to be a loser to substitute two invocations of System.out.print() methods for a string concatenation plus one method invocation -- the result ran about 70% slower than the original code for me.

It took a while for the lightbulb to turn on, but that slowdown is a key symptom of the underlying problem: System.out is unbuffered, at least when it's not connected to a terminal. In a comment you described addressing the problem by building the output in a StringBuilder and then printing it all at once. That's a viable mechanism for buffering manually, but cleaner and easier to integrate into your original solution would have been to wrap a buffered stream around System.out and print to that. In other words, at the top of main() add ...

PrintStream out = new PrintStream(new BufferedOutputStream(System.out));

... and everywhere else print to out instead of to System.out(). Doing that cut my run time by more than 50% relative to the original code, for a maximal-size test set.

\$\endgroup\$
  • 2
    \$\begingroup\$ bonus: use System.setOut(out) ;) (and I could be wrong, but since you're in a BufferedOutputStream now, I think you'll have to call System.out.flush() at the end) \$\endgroup\$ – Olle Kelderman Nov 8 '16 at 23:52
  • \$\begingroup\$ I was not aware that System.out is unbuffered. I learned something new today! \$\endgroup\$ – Emily L. Nov 9 '16 at 8:00
  • \$\begingroup\$ Using PrintStream out = new PrintStream(new BufferedOutputStream(System.out)); the execution time is 0.36 sec whereas with StringBuilder and System.out.print(); it 0.16 sec. But Thank you for your answer, I learned something new today :) \$\endgroup\$ – lord_ozb Nov 9 '16 at 8:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.