2

假设一个对象数组：元素 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添加新元素，并循环为每个元素增加变量x，如下所示：

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

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

}

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

公共类TAD {

公共静态 ArrayList <elemt> T = new ArrayList <elemt> ();

公共静态 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);



 }

// - - - - 结果：

无增量时间：15 ms

增量时间：156 毫秒

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

（有增量的时间 < 没有增量的时间 * 2 ）

因为实际上

有增量的时间 (156 ms) = 没有增量的时间 (15 ms)* 10

我注意到我可以在任何位置添加一个新元素，但我选择了最坏的情况（在第一个位置添加一个元素，需要增加arraylist的所有x元素）

4

3 回答 3

2

只是一个建议（一些“开箱即用”的想法）：

如果您没有其他要求并且仅T通过数组访问对象，那么您实际上不必增加对的第一个元素。

当你今天这样做时（你正在增加第一个值）......

given T[i] = (firstElement, secondElement);
x = firstElement;
y = secondElement;
// work with x and y now...

...您可以这样做（并且永远不需要增加firstElement）：

given T[i] = (firstElement, secondElement);
x = firstElement + i; // add the index!
y = secondElement;
// work with x and y now...

这会将您的 O(n) 插入复杂度变成 O(1)。但是，当然，这在很大程度上取决于您的场景以及您如何使用T对象的值。

于 2013-05-02T20:41:46.857 回答
2

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

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

  deque.addFirst(new);
}

或者其他的东西。

于 2013-05-02T19:52:08.753 回答
2

如果您经常进行插入，我建议您使用 List（例如 LinkedList）。

它使您可以轻松地在任何位置插入元素。还可以轻松地遍历 List 以对每个元素进行一些工作。

如果您想尝试第 3 方库，例如番石榴，您可以尝试番石榴：

Lists.transform(List, Function) http://docs.guava-libraries.googlecode.com/git-history/release/javadoc/com/google/common/collect/Lists.html#transform(java.util.List , com.google.common.base.Function)

它具有map(list, function)类似的功能。所以你不必自己做迭代，只要让transform方法知道，你想对每个元素做什么。然后它会为你做。

PS如何写带有标签的markdown http链接，当链接包含brackets？

于 2013-05-02T20:20:50.690 回答