如何减少这个循环的执行时间（Java）

Question

我有一段代码，执行时间似乎比较长。我需要尽可能地减少执行时间。

基本上，这段代码执行以下操作。我创建了一个大小为[10][10][10]的对象数组。该对象包含以下数字列表：

class MyClass{
  ArrayList<Integer> numberList;
      public MyClass(){
          numberList= new ArrayList <Integer> ();
      }
   }


      MyClass storage[][][] = new MyClass[10][10][10];

我接下来有以下代码，可以向列表中添加数字。

 for(int i =0; i < 200000;i++){
       for(int j = 0; j < 10; j++){
        for(int k = 0; k < 10; k++){
         for(int l = 0; l < 10; l++){            
                   storage[j][k][l].numberList.add(i);
         }
        }
       }
      }

我相信绝大部分执行时间来自以下代码行：

 storage[j][k][l].numberList.add(i);

更具体地说，它是 .add(i) 方法。 我对Java还不太熟悉，只熟悉C++。如果ArrayList类似于C++中的列表，那么在末尾添加元素肯定需要很少的CPU时间吧？难道仅仅因为我执行了很多次添加操作（可能有一百万次）？ 另外一个我想问的问题是，我能否通过使用线程来加速这个过程？（假设有4个线程的双核处理器）我想创建4个线程，每个线程处理50000个块。然而，我不确定如何进行同步。我想我必须在storage[][][]上进行互斥。我需要写什么呢？

synchronized(storage)

这样可以吗？

synchronized(storage[j][k][l])

非常感谢您的帮助。

祝好！

- James

---

你不是在执行100万次加法操作-你正在执行2亿次加法操作。这需要一些时间。如果你预先分配ArrayList的适当大小，可能会节省一些计算时间。 - Carl Manaster

可能有一百万吗？绝对是 2000001010*10 = 2 亿。 - President James K. Polk

请查看 ensureCapacity - http://www.javafaq.nu/java-article1111.html - sunn0

除了其他人说的之外，你需要大约 1GB 的内存。 - Nikita Rybak

Answer 1

处理数千万内存数据时，绝不要使用默认的Java包装类，而应该使用原始类型进行存储。

这是避免自己犯错的最可靠方法：曾经有过这样的经历。

new ArrayList <Integer>

可以轻松地使用Trove的TIntArrayList替换:

new TIntArrayList

你下载Trove后，只需要改变一个代码行，就能在进行你所需操作时节省大量的内存。 为了更好地说明问题：

    final int n = 10000000;

    final List<Integer> l1 = new ArrayList<Integer>( n );
    for (int i = 0; i < n; i++) {
        l1.add( i );
    }

    final TIntArrayList l2 = new TIntArrayList( n );       
    for (int i = 0; i < n; i++) {
        l2.add( i );
    }

第一个循环使用Java原始类型的非意义默认包装器来保存1000万个整数，需要在我的计算机上执行4320毫秒。

第二个循环只需要41毫秒。

因此，速度快了两个数量级。

幼稚的态度可能是认为："两者都是O(1)"。

事实是：两者都是O(1)，但我会选择运行速度快两个数量级的版本。

- SyntaxT3rr0r

---

请注意，Trove除了使用更少的内存和更快的速度外，还有另一个优点：它们的集合设计得非常好，因此垃圾收集器需要远远不那么频繁地启动。 - SyntaxT3rr0r

@Stephen C：感谢你的点赞，但不要把我的“绝对不”断章取义 :) 我说的是“当在内存中处理数千万数据时，这些数据本来可以作为基元类型存储”的情况下，“绝对不”使用自动装箱。否则，你会很快填满JVM的内存。 - SyntaxT3rr0r

我知道你说的。我的观点是，可能有一些非常好的理由将数千万（比如）double值存储为Double对象。"永远不要"太过绝对。如果你有几个GB的堆，那么数千万就微不足道了，所以，如果你没有能力编写/重新编写整个应用程序来使用（比如）Trove，那么你需要做必要的事情... - Stephen C

Answer 2

请使用new ArrayList(capacity)构造函数。在您的情况下，capacity = 200000。 如果您不用预定义的容量初始化ArrayList，那么它将不时地扩展，这实际上是将支持列表的现有数组复制到一个新的更大的数组中。 如果指定了初始容量，ArrayList将从一开始就由足够大的数组支持，而不会发生复制。 如果您在另一个大小为200000不需要的位置使用该类，则可以在另一个循环中调用ArrayList.ensureCapacity(capacity)，它将执行相同的操作——创建足够大的数组以保存所有数据，而无需反复复制。 最后，我认为您应该能够避免完全填充该结构。如果像您简化的示例一样可预测，您可以按需填充它。

- Bozho

---

是的，我的想法是在MyClass对象中初始化它们。对于ensureCapacity选项，我更新了答案。 - Bozho

Answer 3

基本上，您似乎正在使用数字从0到200000填充1000个数组。我会填充一个ArrayList，然后只使用复制构造函数来填充其余的：

class MyClass{
  List<Integer> numberList;
  public MyClass(){ ... }
  // Copy constructor
  public MyClass(ArrayList<Integer> otherList){
    numberList= new ArrayList<Integer>(otherList);
  }
}

MyClass storage[][][] = new MyClass[10][10][10];
List<Integer> prototypeList= new ArrayList<Integer>(200000);

for(int i =0; i < 200000;i++){
  prototypeList.add(i);
}

for(int j = 0; j < 10; j++){
  for(int k = 0; k < 10; k++){
    for(int l = 0; l < 10; l++){            
      storage[j][k][l] = new MyClass(prototypeList);
    }
  }
}

这样做的好处是消除了列表的调整大小，并且可以使用连续的内存块（这消除了内存缓存命中 - 在您的原始循环中，您快速连续访问不同的列表对象，这些对象肯定不能同时适合同一个内存缓存中）。

- Péter Török

---

抱歉。是的，这可能是一个好的解决方案，但我正在简化代码以抽象出不必要的东西。 - James

@James - 那么你需要提供更多的代码，这样我们才能知道实际发生了什么，以便提供优化建议。 - Brad Mace

@James，你的意思是在实际情况下有额外的复杂性迫使你以这种方式填充列表吗？抱歉，但是你在帖子中提供的信息越少，你收到的答案就越不实用... - Péter Török

Answer 4

首先，学会运行分析器来确定程序的瓶颈在哪里。其中一个可能是Sun 6 JDK中的jvisualvm。 我认为你是对的，认为问题出在add()上。 我认为问题在于ArrayLists()需要增长。尝试使用形式new ArrayList(200)（或任何合理的最终大小），然后再次测量。

- Thorbjørn Ravn Andersen

Answer 5

詹姆斯，

请注意，您提供了简化的代码；

1. 该类需要将数据成员封装在MyClass的方法后面。将“numberList”设置为私有，并添加一个公共void add(int i) {...}方法。这意味着numberList的类型可以自由更改 - 封装是良好OO的黄金法则＃1。

2. 将数据成员设置为私有后，您可以将数据类型从ArrayList<Integer> numberList;更改为int [] numberList。我非常确定数组访问速度比ArrayList快。在构造函数中初始化数组。当然，这仅适用于元素数量始终为200,000或在构造函数中传递的某个固定大小的情况。此外，具有int数组将比ArrayList小得多（在RAM中）-每个整数都是带有来自Object的负担的完整对象。较小的RAM占用空间会（在您的示例情况下）减少可能需要的任何磁盘交换。

3. 不要担心展开任何小的内部循环，JVM将自动执行这些低级优化，更有效地并且不会污染您的代码。

- David Kerr

---

+1 给你... 至少有人理解 Integer/int 的区别，并意识到它在这里的重要性。看看我的答案，如果你不想自己处理低级细节，可以在使用大量基元时使用令人惊叹的 Trove 集合。 - SyntaxT3rr0r

@Webinator；你也加一分。Trove库看起来非常不错，感谢你的建议！但它似乎需要更新——它没有实现Iterable接口，因此无法使用内置的for-each循环结构。 - David Kerr

Answer 6

你可能想要为预期容量分配ArrayList。这样它只会被分配一次。

在你的情况下：

numberList= new ArrayList <Integer> ( 200000 );

- Alexander Pogrebnyak

Answer 7

LinkedList 相当于 C++ 中的 list。

我认为 ArrayList 类似于 std::vector。

- DaVinci