java - 通过 arraycopy 添加和增加数组元素

Question

这个问题已经有答案了:

adding and incrementing data structure elements simultaneously with a faster time possible [closed] (3 个回答)

已关闭 10 年前。

假设有一个对象数组:元素 T[ ] ，每个对象包含两个整型变量 (x,y)。

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

每次将新元素添加到数组时，我想以尽可能更快的方式增加对象的变量x的值。新元素可以添加到任何位置，我们在插入位置(位置+1)之后增加所有 x 元素

在添加 (6,6) 之前:

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

在不同位置添加(6,6)后:

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

或

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

或

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

我使用arraycopy方法添加新元素，并循环for为每个元素增加变量x，如下所示:

1. 增加所有 x使用 for 循环的对象元素

2. Ta[0] = (6,6)

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

因为它比

快

While (i< T.length){

  T[i] = T[i+1]

  T[i].x ++;

   i++;
}

我需要以更快的时间添加新元素并同时增加数组的其他对象。

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

公共(public)类元素{

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)课 TAD {

public static ArrayList T = new ArrayList ();

public static ArrayList T1 = new ArrayList ();

 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);



 }

//-------- 结果:

无增量时间:15 ms

增量时间:156 毫秒

我的目标是尽可能减少增量过程的时间

(增量时间 < 不增量时间 * 2 )

因为实际上

增量时间 (156 ms) = 无增量时间 (15 ms)* 10

我注意到我可以在任何位置添加一个新元素，但我选择了最坏的情况(在第一个位置添加一个元素，需要递增数组列表的所有x元素)

Answer 1

不要使用数组，使用Deque ，可能是 LinkedList 。这在前面有 O(1) 插入。

public void addAndIncrement(Deque<Point> deque, Point new) {
  for(Point p : deque) {
    p.x++;
  }

  deque.addFirst(new);
}

或者其他什么。