5
\$\begingroup\$

I need to get some information about the Pascal Triangle.

What is a pascal triangle ?

It is a triangle of integers with 1 at the top and at the sides. Any number inside is equal to the sum of the two numbers above his. For example, here are the first 5 lines of the triangle:

Pascal Triangle

So I need to figure out the number of numbers pairs that exist in the first thousand lines of the triangle.

I would like to know how I can improve the performance of my code or rewrite some part that is poorly structured

import java.sql.Date;
import java.text.DecimalFormat;
import java.text.SimpleDateFormat;
import java.util.Vector;

public class PascalTriangle {

    private static int [][] matrix;
    private static int i, j, n;

    public static void main(String[] args) 
    { 

        long start_time = System.currentTimeMillis();  

        n = 0; // Number of even numbers;

        matrix = new int[1000][1000]; 

        for (i = 0; i < 1000; i++) {        
            for (j = 0; j < 1000; j++) {
                matrix[i][j] = 0;
            }
        }

        matrix[0][0] = 1;
        matrix[1][0] = 1;
        matrix[1][1] = 1;

        for (i = 2; i < 1000; i++) {        
            matrix[i][0] = 1;
            matrix[i][i] = 1;
            for (j = 1; j < i; j++) {
                matrix[i][j] = matrix[i-1][j-1]+matrix[i-1][j];
                if ( matrix[i][j] % 2 == 0 ) {
                    n++;
                }
            }
        }

        System.out.println( "Amount of even numbers = " + n );

        long end_time  = System.currentTimeMillis();   
        System.out.println(new SimpleDateFormat("ss.SSS").format(new Date(end_time - start_time)));  

    }
}

Expected result:

Amount of even numbers = 448363

Currently taking a time of 00.011 seconds

\$\endgroup\$
  • \$\begingroup\$ Are you really calculating what you're asked to calculate? I understand "number of number pairs" to mean how many numbers in one line are duplicated. So, for example, line 2 has 1 pair (1 and 1 are a pair). Line 3 has 1 pair (1 and 1 are paired but the 2 isn't), while line 4 has 2 pairs (a pair of 1s and a pair of 3s). You seem to be looking for even numbers instead. \$\endgroup\$ – DodgyCodeException May 9 at 14:18
3
\$\begingroup\$

One array solution

The following algorithm is an improvement on the two array system stated bellow it. Basically, we only need the context of the old previous value (as well as the next value, which goes unmodified), so we copy this value. From there we can set the new end to 1 then start over. This cuts down on the memory overhead. I think you'll see minimal computational improvements as yours was already pretty efficient, but this one takes less memory. I suspect there will be a performance increase where you are dealing with pretty large arrays.

import java.util.Arrays;

class Pascal{

     public static void main(String []args) {
        int toNthLine = 1000;
        int[] row = new int[toNthLine+1];
        int counter = 0;
        int previous;
        row[0] = 1;
        for (int i = 0; i < toNthLine; i++) {
            previous = 1;
            for (int j = 0; row[j+1] != 0; j++) {
                int temp = row[j+1];
                row[j+1] = previous + row[j+1];
                previous = temp;
                if (row[j+1] % 2 == 0)counter++;
            }
            row[i] = 1;
        }
        System.out.println(counter);
     }
}
\$\endgroup\$
2
\$\begingroup\$

There is one fairly obvious optimization that should cut your time in roughly half. Pascal's Triangle is symmetric. Take advantage of that with whatever algorithm you are using. Roughly speaking (without checking my end-conditions so do that):

for (j=1;j<i/2;j++)
{
  value = matrix[i-1][j-1] + matrix[i-1][j];
  matrix[i][j] = matrix[i][i-j] = value;
  if (value % 2 == 0) 
    n+=2;
}
if ((2*j==i) && (value%2 == 0))
  n--;

This also shows some minor optimizations that may gain you time. Saving the new value in a separate variable so that you aren't dereferencing the array subscripts repeatedly, especially the check I added outside the loop, should save a little time. The check outside is because most of the way through the half row you want to count two for every even number, but on the specific end condition in the rows with an odd number of values you will double count it and have to subtract it out again. Do that outside the loop to avoid an if statement inside the loop.

@Neil suggested using two arrays instead of a two dimensional array. That may gain you savings by allowing you to set a variable to row1[i] outside the while loop to avoid double subscripting throughout the j loop. However a good compiler may do that optimization for you. Try it with and without.

\$\endgroup\$
  • \$\begingroup\$ It should also be possible to optimize the space of a row in half, but it makes the calculation in the middle a little trickier. If memory isn't an issue it may not be worth it to bother. It may also slow the solution by making the middle less general since it is different for even sized rows than odd sized rows. \$\endgroup\$ – Sinc May 8 at 15:56

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.