time performance, array of 10 000 elements, simple app

Question

When I run this code I got time like 0.25s, I want to improve this code to get time better than 0.16s - this is the limit. I know it depends on the hardware. Time is compute without filling array. I must work on array. How can I improve this ?

Update: I want to get the index of first element of slice which avg is minimal.

    public static void main(String[] args) {
    int[] A = new int[10000] ;
    double randomNum ;
    for(int i= 0 ; i<A.length ; i++)
    {
        randomNum = 0 + (double)(Math.random()*1); 
        if(randomNum>0.5)
            A[i]=-1;
        else
            A[i]=1;
    }

  System.out.println("Compute");   


    long start_time = System.nanoTime();
    int result = 0;
    double minavg = 100000 ;
    double avg;
    double suma = 0;
    int count = 0;

    for(int i=0 ; i<A.length-1 ; i++)
    {
        for(int k=i ; k<A.length ; k++)
        {
            suma+=A[k];
            count++;


            if(count>1)
            {
                 if(A[k]<A[k-1]) {
                avg=suma/count;
                if(minavg>avg)
                {
                    minavg=avg;
                    result =  i;
                }
                 }
            }


        } 
        suma=0;
        count=0;

    }

    long end_time = System.nanoTime();
    double difference = (end_time - start_time)/1e9;
    System.out.println(difference);
}

Will you explain what you are trying to do with this algorithm? — Damien Black, Feb 24 '14 at 20:47
Two suggestions: (1) learn to use a profiler; (2) read http://stackoverflow.com/questions/504103/how-do-i-write-a-correct-micro-benchmark-in-java — NPE, Feb 24 '14 at 20:48
Nano-, a prefix in the SI and other systems of units denoting a factor of 10−9 (one billionth). You divide difference by `1e6`, getting `seconds * 10^3` or `milliseconds`. — C.B., Feb 24 '14 at 20:49
You are right, I updated main post with correct values of time and dividing by nano. — kxyz, Feb 24 '14 at 20:57
-1 and 1 is one of part of data, others parts are [-100000,100000] — kxyz, Feb 24 '14 at 21:36
Is the code correct? I do not know if I misunderstood the problem, but for A = int[]{10,10,1,2} the expected result is 3 but 1 is found. — Crferreira, Feb 24 '14 at 21:57

score 0 · Answer 1 · answered Feb 24 '14 at 21:13

I tried to look into that in javascript. I started with an average time of 0.101 and get down to 0.076 with those small modifications:

function main() {
    var A = new Array() ;
    var randomNum ;
    for(var i= 0 ; i<1000 ; i++)
    {
        randomNum = 0 + Math.random(); 
        if(randomNum>0.5)
            A[i]=-1;
        else
            A[i]=1;
    }

  console.log("Compute");   


    var start_time = new Date().getTime();;
    var result = 0;
    var minavg = 100000 ;

    for(var i=0 ; i<A.length-1 ; i++)
    {
        var suma= A[i];
        var count=1;
        for(var k=i+1 ; k<A.length ; k++)
        {
            suma+=A[k];
            count++;
            if(A[k]<A[k-1]) {
                var avg=suma/count;
                if(minavg>avg)
                {
                    minavg=avg;
                    result =  i;
                }
            }
        } 
     }

    var end_time = new Date().getTime();
    var difference = (end_time - start_time)*1e-3;

    console.log(difference);

}

main();

My point was to limit the number or tests and allocate local variable at the very last time in order to maximum CPU register and context. On a compile java version you might have even better results than me.

Try on 10 000 elements, time doesnt increase linearly on this, On my code I dont see difference, but thanks — kxyz, Feb 24 '14 at 21:35
With 10K, I've got now 8.096s versus 9.533 with the original code (16% quicker). @kxyz — Stéphane de Luca, Feb 24 '14 at 22:23

endriu_l · Accepted Answer · 2014-02-24T22:29:55.547

One thing that you can do is changing the datatype of suma to int, but remember to cast it back to double in avg computation . This will avoid a lot of datatype conversions in incrementations, in my case it took the time down by about 1/7th.

Secondly, I'm not sure about this condition:

if (A[k] < A[k - 1])

Imho it should be like this (and it takes the time down by 1/2):

if (A[k] < minavg)

but I'm not sure if the final result is correct then, but it fixes issue mentioned by @Crferreira

I'm still not sure about Your original algorithm and the task. here is my rewrite of it. on average it takes the time further down to 1/3rd of last measurement

private static void calculateB(int[] A) {
    if (A == null || A.length < 2) {
        return;
    }
    long start_time = System.nanoTime();
    int result = 0;
    double minavg = 100000;
    double avg;
    int suma = A[A.length - 1];
    int count = 1;

    for (int i = A.length - 2; i >= 0; i--) {
        count += 1;
        int previous = A[i];
        suma += previous;

        if (previous < minavg) {
            avg = (double) suma / count;
            if (minavg > avg) {
                minavg = avg;
                result = i;
            }
        }
    }

    long end_time = System.nanoTime();
    double difference = (end_time - start_time) / 1e6;
    System.out.println(result + " " + minavg + " " + difference);
}

BUT the results from this one are different from original, you have to check if it validates against assignment. I did make the calculations manually and it seems to be OK. This one, iterates the table from the end. Thanks to this, we have a base for sum that we reuse in further iterations.

As for the general rule - I'm not sure what you are calculating - from the code, it looks like it is index of item with lowest avg of following items including the one on index - is this correct ?

sorry, I change the double sum to int, and its improve to 1.7s ^^ thanks — kxyz, Feb 24 '14 at 22:11

score 0 · Answer 3 · answered Feb 24 '14 at 21:56

0

One optimization is removing the count > 1 test by rearranging the code like this

for(int i=0 ; i<A.length-1 ; i++) {
    suma=A[i];
    for(int k=i+1 ; k<A.length ; k++) {
        suma+=A[k];
        count++;
        if(A[k]<A[k-1]) {

answered Feb 24 '14 at 21:56

Ted Bigham

4,237
1
26
31

time performance, array of 10 000 elements, simple app

3 Answers3

BUT the results from this one are different from original, you have to check if it validates against assignment. I did make the calculations manually and it seems to be OK. This one, iterates the table from the end. Thanks to this, we have a base for sum that we reuse in further iterations.