Two methods implement same algorithm one is taking running time more than other in java

Question

I am trying to calculate running time of two methods using new Date().getTime(). the two methods follow same algorithm,and one of them increase some steps,however the method with less steps take more time .

I am confusing of that. here is the two methods: This the first method use less steps and take more time:

public void encryptFiles(List<BloomFilter> bfList1) {
    Matrix matrix2 = new Matrix(400,400);
    Matrix matrix3 = new Matrix(400,400);

    matrix2.setMat(value1);
    matrix3.setMat(value2);

    a2 = matrix2.transpose();
    b2 = matrix3.transpose();

    startTime2 = new Date().getTime();
    for (BloomFilter bfList2 : bfList1) {
        Random raa = new Random();
        int g1 = raa.nextInt();
        double m1 = (double) ((double) Math.round(g1 * 10) / 10.0);

        List<double[]>  res1 = new ArrayList<>();
        double[] e1 = new double[400];
        double[] k1 = new double[400];

        Vector<Double> j = new Vector<Double>(400);
        Vector<Double> h = new Vector<Double>(400);

        //System.out.println("bloom filter in bloom filter list:" + Arrays.toString(bfList2.getBitSet().data));
        String bfName = bfList2.getName();
        for (int i = 0; i < s.size(); i++) {
            if (s.get(i) == 1) {
                j.add( (double) bfList2.getBitSet().getWord(i));
                h.add((double) bfList2.getBitSet().getWord(i));
            } else {
                j.add(0.5 * (bfList2.getBitSet().getWord(i))+m1);
                h.add(0.5 * (bfList2.getBitSet().getWord(i))+m1 );
            }
        }

        for (int u = 0; u < 400; u++) {
            for (int y = 0; y < 400; y++) {
                e1[u] += a2[u][y]*j.get(y);
                k1[u] += b2[u][y]*h.get(y);
            }
        }
        res1.add(e1);
        res1.add(k1);
        hasssh.put(bfName,res1 );
    }
    encryptedBFListInTime = (new Date().getTime())-startTime2;
    encryptedBFListInTime /= 1000.0; 
    System.out.println("encrypt files only in "+encryptedBFListInTime);
}

and the following is the second method use more steps but less time:

public  BloomFilterIndex encryptTree(BloomFilterIndex tree) {

    startTime9 = new Date().getTime();
    for(int m = 0; m < tree.root.children.size(); m++){
        BloomFilterIndex.BFINode<Integer> n =(BloomFilterIndex.BFINode<Integer>)tree.root.children.get(m);
        encrypt(n);
    }
    end = new Date().getTime() - startTime9;
    //end1 = end - startTime9;
    end /= 1000.0;
    System.out.println("encrypt node in :"+end);
    return tree;
}

calling the following method :

public void encrypt(BloomFilterIndex.BFINode<Integer> root) {

    List<double[]> ress = new ArrayList<>();
    if (!root.isLeaf()) {
        c = new double[root.value.size()];
        // c = new double[4];
        for (int i = 0; i < root.value.size(); i++) {
        //  for(int i = 0; i < 4; i++){
            c[i] = root.value.getBitSet().getWord(i);
        }
        ress.add(c);
        root.value = null;
        root.value2 = ress;

        for (BloomFilterIndex.BFINode<Integer> g : root.children) {
            encrypt(g);
        }

    } else {
        //String bfName1 = root.value.getName(); 
        double[] y = new double[400];
        double[] z = new double[400];
        Random r = new Random();
        Integer g1 = r.nextInt();
        double m5 = (double) ((double) Math.round(g1 * 10) / 10.0);
        Vector<Double> m6 = new Vector<Double>(400);
        Vector<Double> n1 = new Vector<Double>(400);

        for (int i = 0; i < s.size(); i++) {
            //  for(int i = 0;i < 400; i++) {
            if (s.get(i) == 1) {
                m6.add((double) root.value.getBitSet().getWord(i));
                n1.add((double) root.value.getBitSet().getWord(i));
            } else {
                m6.add(0.5 * (root.value.getBitSet().getWord(i)) + m5);
                n1.add(0.5 * (root.value.getBitSet().getWord(i)) + m5);
            }
        }

        for (int i = 0; i < 400; i++) {
            for (int j = 0; j < 400; j++) {
                y[i] += a2[i][j] * m6.get(j);
                z[i] += b2[i][j] * n1.get(j);
            }
        }
        ress.add(y);
        ress.add(z);
        root.value = null;
        root.value2 = ress;
        //  hasssh1.put(bfName1, ress);
    }
}

where is the problem please.

Are you testing them one after the other in the same JVM? If so, you could be encountering "startup" delays. In other words, the JVM has to "warm-up" for the first method but not for the second method. Read https://stackoverflow.com/questions/504103/how-do-i-write-a-correct-micro-benchmark-in-java — Slaw, Jun 04 '18 at 04:27

score 1 · Answer 1 · answered Jun 04 '18 at 04:28

The run time depends on the critical sections of the code. To determine the critical sections, remember that the are contained in the most deeply nested for or while loops. Other lines of code only execute once!

In the second method you call the helper method from WITHIN the for loop! This means that you are executing ALL the for loops and nested for loops in the helper method tree.root.children.size() times, because the helper method is being called that many times!

When thinking of nested loops, multiply! e.g.,

for (int i= 0; i < 5; i++) {
  for (int j= 0; j < 5; j++) {
    DOTHING();
  }
}

DOTHING will execute 25 times! Why? The outer loop executes 5 times! The nested loop executes 5 times! 5 x 5 = 25 times!

You calling that helper method and all of its nested for loops from within a for loop is like having another nested loop added on. This is the difference between n * n execution and n * n * n or n^2 vs n^3! I hope this helps!

Two methods implement same algorithm one is taking running time more than other in java

1 Answers1