Thread: add and increment array elements by arraycopy

suppose an array of object: Element T[ ] , each object contains two integer variables (x,y).

T = (1,1) (2,2) (3,3) (4,4)
I want to increment the value of the variable x of object each time a new element is added to array with the faster way possible . The new element can be added in any position and we increment all x element after the insertion position (position +1)

Before add (6,6) :

T = (1,1) (2,2) (3,3) (4,4)

After add (6,6) in different positions:

1) T = (6,6) (2,1) (3,2) (4,3) (5,4)

or

2) T = (1,1) (2,2) (6,6) (4,3) (5,4)

or

3) T = (1,1) (2,2) (3,3) (6,6) (5,4)

I used the method arraycopy to add the new element, and loop for to increment the variable x for each element, as follow:

increment all x of object elements with loop for

Ta[0] = (6,6)

araycopy(T, 0, Ta, 1, T.size-1 );

because it is faster than

While (i< T.length){

T[i] = T[i+1]

T[i].x ++;

i++;
}
I need to add the new element and increment the other objects of array simultaneously with a faster time.

//-------------------

public class elemt {
 
public int x;
public int y;
 
public elemt(int a, int b){
    this.x= a;
    this.y= b;
}
 
 
public void inc(){
 x++;
}
 
int getX(){
    return x;
}
 
int getY(){
    return y;
}
}

//----------------

public class TAD {
 
public static ArrayList < elemt > T = new ArrayList < elemt > ( );
 
public static ArrayList < elemt > T1 = new ArrayList < elemt > ( );
 
 public static void main(String[] args){
 
 
 
    for(int i=0; i<10000000; i++){
       T1.add(new elemt(i, i));
      }
 
 
     long t0 = System.currentTimeMillis();
 
      T1.add(0, new elemt(1, 1));
 
     long t1= System.currentTimeMillis()- t0;
 
     System.out.println("Time without Incrementation : "+t1);
 
 
 //--------------
 
     for(int i=0; i<10000000; i++){
       T.add(new elemt(i, i));
      }
 
 
    long t2 = System.currentTimeMillis();
 
       T.add(0, new elemt(1, 1));
 
        for(int i=1; i<T.size(); i++){
          T.get(i).inc();
        }
 
    long t3= System.currentTimeMillis()- t2;
 
  System.out.println("Time with Incrementation: "+t3);
 
 }

//------- The results:

Time without Incrementation : 15 ms

Time with Incrementation: 156 ms

My objective is to minimize as possible the time of incrementation process

(Time with Incrementation < Time without Incrementation * 2 )

because actually

Time with Incrementation (156 ms) = Time without Incrementation (15 ms )* 10

I notes that i can added a new element in any position, but i chose the worst case (adding an element in the first position that requires the incrementation of all x element of the arraylist)

I need to add the new element and increment the other objects of an array of objects (elemt) simultaneously with a faster time.

 public class elemt {
 
        public int x;
        public int y;
 
        public elemt(int a, int b){
            this.x= a;
            this.y= b;
        }
 
 
        public void inc(){
         x++;
        }
 
        int getX(){
            return x;
        }
 
        int getY(){
            return y;
        }
 
 
    }

//----------------

   public class TAD {
 
       public static ArrayList < elemt >  A1 = new ArrayList < elemt > ( ); // first array
 
       public static ArrayList < elemt > A2 = new ArrayList < elemt > ( ); // second array
 
         public static void main(String[] args){
 
       //------- first test -------------- 
 
            for(int i=0; i<10000000; i++){
               A1.add(new elemt(i, i));    // fill array A1 
              }
 
 
             long t0 = System.currentTimeMillis();
 
              T1.add(0, new elemt(1, 1));  // calculate te time of adding one element in filled array A1
 
             long t1= System.currentTimeMillis()- t0;
 
             System.out.println("Time first test : "+t1);
 
 
 
 
       //----------- Second Test ------------
 
             for(int i=0; i<10000000; i++){
               A2.add(new elemt(i, i));     // fill array A2
              }
 
 
            long t2 = System.currentTimeMillis();
 
               A2.add(0, new elemt(1, 1)); // adding one element in filled array A2
 
                for(int i=1; i<T.size(); i++){
                  A2.get(i).inc();     // Increment all element of A2 from position 1.
                }
 
            long t3= System.currentTimeMillis()- t2;
 
          System.out.println("Time second test: "+t3);
 
 
 
         }

//------- The results:

Time without Incrementation : 15 ms

Time with Incrementation: 156 ms


My objective is to minimize as possible the time of incrementation process

(Time second test < Time first test * 2 )

because actually

Time second test (156 ms) = Time first test (15 ms )* 10

I notes that i can added a new element in any position, but i chose the worst case (adding an element in the first position that requires the incrementation of all **x** element of the arraylist)

I tried many data structure as vector, hashmap ,... but I could not minimize the time of incrementation

Originally Posted by Norm

Try rewriting the code in machine language.

I tried with JNI (Java Native Interface) but no improvement !!!!!

You could probably drastically cut that time down by using an iterator to loop through the array list rather than get(<index>).

Also may I see your JNI Implementation?

After that you are pretty much bound by the fact the algorithm is always going to be O(n).

Regards,

Chris