5
\$\begingroup\$

I am currently working on a problem of an online judge (not a contest). The program must calculate how many years will require for the population A (which is always less than B) to be higher than B. If the time is more than a Century then print "More than a century" in Portuguese.
Input

1
90000 120000 5.5 3.5

Where 1 is the number of test cases and in the next line are the population of A, population of B, percentage growing rate of A and percentage growing rate of B. For this input the result will be 16 years.

However, my code keeps exceeding the time limit, which is only 1 second. I have used Scanner and System.out.print() however I have been told that such methods will make my code slower and will consume more memory, that is way I buffered the input and output. I cannot use types such as long or int as the data stored the variables is longer than those values.

import java.io.*;
import java.math.BigDecimal;

class Main {
    public static void main(String[] args) throws NumberFormatException, IOException{
        java.io.InputStreamReader iSR = new java.io.InputStreamReader(System.in);
        java.io.BufferedReader bR = new java.io.BufferedReader(iSR, 16 * 1024);
        BufferedWriter bW = new BufferedWriter(new OutputStreamWriter(System.out));
        String tL;
        BigDecimal PRA = BigDecimal.ZERO, PRB = BigDecimal.ZERO, PA = BigDecimal.ZERO, PB = BigDecimal.ZERO;
        int input = Integer.parseInt(bR.readLine());
        for(int j = 0; j < input; j++){
            tL = bR.readLine();
            String [] = arr = tL.split(" ");
            PA = BigDecimal.valueOf(Integer.parseInt(arr[0]));
            PB = BigDecimal.valueOf(Integer.parseInt(arr[1]));
            PRA = BigDecimal.valueOf(Double.parseDouble(arr[2]));
            PRB = BigDecimal.valueOf(Double.parseDouble(arr[3]));
            PRA = PRA.divide(BigDecimal.valueOf(100)); PRA = PRA.add(BigDecimal.ONE);
            PRB = PRB.divide(BigDecimal.valueOf(100)); PRB = PRB.add(BigDecimal.ONE);
            int i = 1;
            while(PA.compareTo(PB) < 0 && i < 103){
                BigDecimal ibd = BigDecimal.valueOf(i);
                PA = PA.multiply(PRA).multiply(ibd);
                PB = PB.multiply(PRB).multiply(ibd);
                i++;
            }
            i--;
            if(i > 100) bW.write("Mais de 1 seculo.\n");
            else bW.write(String.valueOf(i) + " anos.\n");
            bW.flush();
        }
    }
}
\$\endgroup\$
  • \$\begingroup\$ What exactly is the program supposed to do? \$\endgroup\$ – Vitruvius Feb 21 '14 at 3:44
  • \$\begingroup\$ @Saposhiente Please have a look at the first edit \$\endgroup\$ – Hans Feb 21 '14 at 3:53
2
\$\begingroup\$

First, the syntax error:

        String [] = arr = tL.split(" ");

You probably meant

        String[] arr = tL.split(" ");

Now, let's make all of your variable names readable. Longer names take the same amount of time to access:

    java.io.InputStreamReader inputStream = new java.io.InputStreamReader(System.in);
    java.io.BufferedReader reader = new java.io.BufferedReader(inputStream, 16 * 1024);
    BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));
    String input;
    BigDecimal GrowthA, GrowthB, PopulationA, PopulationB; //no need to assign initial values to them; the values are never used
    int repetitions = Integer.parseInt(reader.readLine());

Now, as always, choosing a better algorithm is a far bigger deal than small things such as your particular means of input and output. On my computer, the code between input = reader.readLine(); and writer.flush(); takes 6 milliseconds to run once and 24 milliseconds to run 50 times for the example input you gave; make sure that your timing measurement does not include the amount of time it spends waiting for you to enter input. For your algorithm, you have chosen to iteratively simulate each year of population growth; this is mathematically inefficient. Your problem algebraically reduces to

PA*(1+PRA/100)^t>PB*(1+PRB/100)^t, solve for t. 
=PA*((PRA+100)/100)^t>...
=PA*(PRA+100)^t*(1/100)^t>...
PA*(PRA+100)^t>...
ln(PA)+t*ln(PRA+100)>ln(PB)+t*ln(PRB+100)
t(ln(PRA+100)-ln(PRB+100))>ln(PB)-ln(PA)
t>(ln(PB)-ln(PA))/(ln(PRA+100)-ln(PRB+100)) (assuming PRA > PRB)

It will be much faster to just use this one computation, and as bonus you will get more precise answers. Also, since you will not be increasing your numbers exponentially in your algorithm, you will now be able to directly use Integer.parseInt instead of having to ever make BigDecimals.

Marginal changes: Testing reveals that using final local variables is faster than reusing larger-scope variables, and that using BufferedReader and BufferedWriter does not create any significant difference in performance (at least on my machine), so unless you test it and get a different result you should use Scanner and System.out just because it's simpler. Also, you should mark all variables that are never modified as final.

    final Scanner scanner = new Scanner(System.in);
    final int repetitions = scanner.nextInt();
    scanner.skip("\n");
    for(int j = 0; j < repetitions; j++){
        final String input = scanner.nextLine();
        final String[] arr = input.split(" ");
        final double PopulationA = Double.parseDouble(arr[0]);
        final double PopulationB = Double.parseDouble(arr[1]);
        final double GrowthA = Double.parseDouble(arr[2]);
        final double GrowthB = Double.parseDouble(arr[3]);
        System.out.print((Math.log(PopulationB)-Math.log(PopulationA))/(Math.log(GrowthA+100)-Math.log(GrowthB+100)) + " anos.\n");
    }

If integer output is required, throw in a call to Math.ceil. On my machine, the code after final String input = scanner.nextLine(); runs once in 3 milliseconds, 50 times in 6 milliseconds, and 10,000 times in 450 milliseconds, with your example input. A doubling of speed for one run, and faster and faster for the same input repeated.

\$\endgroup\$
  • 1
    \$\begingroup\$ Comments are a code smell. Your print statement is horrible, especially in the light of what you put in the comment is valid Java syntax. (log(pb) - log(pa)) / (log(pra + 100) - log(prb + 100)) Why not just say what you mean? \$\endgroup\$ – abuzittin gillifirca Feb 21 '14 at 8:18
  • \$\begingroup\$ I don't find Scanner and System.out less or more readable than BufferedReader and BufferedWriter. They are just different tools to do the "same" kind of task. If you don't need buffering than don't use it, but I don't find readability a problem. \$\endgroup\$ – Marc-Andre Feb 21 '14 at 14:19
  • \$\begingroup\$ @abuzittingillifirca Had initially written that because asker wanted performance over clarity, testing reveals that using final variables instead has no significant performance difference, edited to use those instead. \$\endgroup\$ – Vitruvius Feb 22 '14 at 3:00
0
\$\begingroup\$
  1. The code prints a short line in every iteration and forces the BufferedWriter to flush in every iteration. It just makes no sense to buffer such small amount of data. I would move the flushing outside the for loop. I'm not sure that it will help at all (since you are writing to the standard output) but I guess it would help if you redirect the output to a file.

  2. The tL variable could be declared inside the loop. (Effective Java, Second Edition, Item 45: Minimize the scope of local variables)

  3. BigDecimal.valueOf(100) is used and created multiple times. You could create a constant for it. Although the JVM might already optimize it for you it would be readable.

  4. I'd put the variable declarations to separate lines. From Code Complete, 2nd Edition, p759:

    With statements on their own lines, the code reads from top to bottom, instead of top to bottom and left to right. When you’re looking for a specific line of code, your eye should be able to follow the left margin of the code. It shouldn’t have to dip into each and every line just because a single line might contain two statements.

\$\endgroup\$

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.