2
\$\begingroup\$

I'm trying to solve this problem. I changed Scanner and used BufferedReader but I'm still getting TLE with the given code. Can I have a code review to help determine where else performance can be optimized?

import java.util.ArrayList;
import java.util.List;
import java.io.BufferedReader;
import java.io.InputStreamReader;

class LittleDeepuAndArray {
    public static void main(String args[] ) throws Exception {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String line = br.readLine();
        long N = Long.parseLong(line);
        List<Long> list = new ArrayList<Long>();
        String line5 = br.readLine();
        String[] numbers = line5.split(" ");
        for(int z=0;z<N;z++) list.add(Long.parseLong(numbers[z]));
        String line2 = br.readLine();
        long M = Long.parseLong(line2);
        long X=0;
        int k=0,m=0;
        long zz=0;
        long size=list.size();
        for(k=0;k<M;k++) {
            X = Long.parseLong(br.readLine());
            for (m=0;m<size;m++) { 
                zz=list.get(m);
                if(X<zz) list.set(m,zz-1);
            }
        }
        for (m=0;m<size;m++) { 
            if(m==size-1) System.out.print(list.get(m));
            else System.out.print(list.get(m) + " ");
        }
    }
}
\$\endgroup\$
  • 2
    \$\begingroup\$ All questions on Code Review have "concerns" about their style or performance. Using your concerns as the "title" makes your question hard to differentiate from other questions. Thus, on code review, we like titles that describe what the code should do, not what is wrong with it. Additionally, the question should describe the problem being solved - which challenge is it? Have a look at this recent question to see how you should edit your question: codereview.stackexchange.com/questions/101181/… \$\endgroup\$ – rolfl Aug 30 '15 at 12:33
  • \$\begingroup\$ We can't meaningfully review your code without knowing what you are trying to accomplish. If this is a programming-challenge, please summarize the challenge here and add a link to it as a citation. \$\endgroup\$ – 200_success Aug 30 '15 at 19:09
7
\$\begingroup\$

Your major performance issue is almost certainly the way you perform your output. This is a common problem in how online judges evaluate performance.... they assume output time is part of the algorithmic solve-time.

Output

When programs output data to the console it is seldom a performance critical aspect of code. So, why should that code be lightning-fast when the console redraws are slow. In other words, Java's System.out.print* methods are not designed to be as fast as some other languages. Specifically, the print*() methods are synchronized so that only one thread can print at a time. They also incur a fair amount of overhead to own, manage, and release the system resources attached to the console. Each time you call print*(...) you repeat a lot of this work.

The bottom line is that you should call these methods just once.

    StringBuilder sb = new StringBuilder();
    for (m=0; m < size; m++) { 
        if(m > 0) {
            sb.append(" ");
        }
        sb.append(list.get(m));
    }
    System.out.println(sb);

Put all the data in to a StringBuilder, and then print it once.

Other things

In addition, you code would benefit from using a number of more convenient mechanisms.... like whitespace and braces.

Your code is suffocating, it has no breathing room. Consider:

    String[] numbers = line5.split(" ");
    for(int z=0;z<N;z++) list.add(Long.parseLong(numbers[z]));
    String line2 = br.readLine();

which should be:

    String[] numbers = line5.split(" ");
    for(int z=0; z < N; z++) {
        list.add(Long.parseLong(numbers[z]));
    }
    String line2 = br.readLine();

Similarly, in other places you have no whitespace or braces on conde blocks or around operators.

Additionally, your variable names are irritating, and inconvenient. You have two variables called "m", both M and m.

Finally, if you put your code in to more methods, it will give the Java compiler a chance to optimize the code when it compiles it. Java's basic using of performance compilation is a "method", since you only have one method, and since it is only called once (the main method), your logic is never compiled and optimized properly.

|improve this answer|||||
\$\endgroup\$
  • \$\begingroup\$ Thanks! I learnt new things. Though it didn't solve my TLE state. But, I think I'd need to refactor my logic rather than applying these optimization techniques! \$\endgroup\$ – tanmay Aug 31 '15 at 16:58

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.