ArrayLists的速度是数组的两倍多吗？

我写了一个试图测试两件事的测试：

• 即使您不使用整个缓冲区，缓冲区数组的大小是否会影响其性能
• 数组和ArrayList的相对性能

我对结果感到惊讶

• 盒装数组（即Integer vs int ）并不比原始版本慢得多
• 底层数组的大小并不重要
• ArrayList的速度是相应数组的两倍多。

问题

1. 为什么ArrayList这么慢？
2. 我的基准写得好吗？ 换句话说，我的结果是否准确？

结果

  0% Scenario{vm=java, trial=0, benchmark=SmallArray} 34.57 ns; ?=0.79 ns @ 10 trials 17% Scenario{vm=java, trial=0, benchmark=SmallBoxed} 40.40 ns; ?=0.21 ns @ 3 trials 33% Scenario{vm=java, trial=0, benchmark=SmallList} 105.78 ns; ?=0.09 ns @ 3 trials 50% Scenario{vm=java, trial=0, benchmark=BigArray} 34.53 ns; ?=0.05 ns @ 3 trials 67% Scenario{vm=java, trial=0, benchmark=BigBoxed} 40.09 ns; ?=0.23 ns @ 3 trials 83% Scenario{vm=java, trial=0, benchmark=BigList} 105.91 ns; ?=0.14 ns @ 3 trials benchmark ns linear runtime SmallArray 34.6 ========= SmallBoxed 40.4 =========== SmallList 105.8 ============================= BigArray 34.5 ========= BigBoxed 40.1 =========== BigList 105.9 ============================== vm: java trial: 0 

代码

此代码是使用Java 7和Google caliper 0.5-rc1在Windows中编写的（因为最后我检查1.0在Windows中不起作用）。

快速概述：在所有6个测试中，在循环的每次迭代中，它都会在数组的前128个单元格中添加值（无论数组有多大），并将其添加到总值中。 Caliper告诉我应该运行多少次测试，所以我将这个添加循环128次。

这6个测试有一个很大的（131072）和一个小的（128）版本的int[] ， Integer[]和ArrayList 。 您可以找出名称中的哪个。

 import java.util.ArrayList; import java.util.List; import java.util.Random; import com.google.caliper.Runner; import com.google.caliper.SimpleBenchmark; public class SpeedTest { public static class TestBenchmark extends SimpleBenchmark { int[] bigArray = new int[131072]; int[] smallArray = new int[128]; Integer[] bigBoxed = new Integer[131072]; Integer[] smallBoxed = new Integer[128]; List bigList = new ArrayList(131072); List smallList = new ArrayList(128); @Override protected void setUp() { Random r = new Random(); for(int i = 0; i < 128; i++) { smallArray[i] = Math.abs(r.nextInt(100)); bigArray[i] = smallArray[i]; smallBoxed[i] = smallArray[i]; bigBoxed[i] = smallArray[i]; smallList.add(smallArray[i]); bigList.add(smallArray[i]); } } public long timeBigArray(int reps) { long result = 0; for(int i = 0; i < reps; i++) { for(int j = 0; j < 128; j++) { result += bigArray[j]; } } return result; } public long timeSmallArray(int reps) { long result = 0; for(int i = 0; i < reps; i++) { for(int j = 0; j < 128; j++) { result += smallArray[j]; } } return result; } public long timeBigBoxed(int reps) { long result = 0; for(int i = 0; i < reps; i++) { for(int j = 0; j < 128; j++) { result += bigBoxed[j]; } } return result; } public long timeSmallBoxed(int reps) { long result = 0; for(int i = 0; i < reps; i++) { for(int j = 0; j < 128; j++) { result += smallBoxed[j]; } } return result; } public long timeBigList(int reps) { long result = 0; for(int i = 0; i < reps; i++) { for(int j = 0; j < 128; j++) { result += bigList.get(j); } } return result; } public long timeSmallList(int reps) { long result = 0; for(int i = 0; i < reps; i++) { for(int j = 0; j < 128; j++) { result += smallList.get(j); } } return result; } } public static void main(String[] args) { Runner.main(TestBenchmark.class, new String[0]); } } 

Answer 1

首先 …

ArrayLists的速度是数组的两倍多吗？

作为概括，没有。 对于可能涉及“更改”列表/数组长度的操作， ArrayList将比数组更快…除非使用单独的变量来表示数组的逻辑大小。

对于其他操作， ArrayList可能会更慢，但性能比很可能取决于操作和JVM实现。 请注意，您只测试了一个操作/模式。

为什么ArrayList这么慢？

因为ArrayList内部有一个不同的数组对象。

• 操作通常涉及额外的间接（例如，获取列表的大小和内部数组），并且还有额外的边界检查（例如，检查列表的size和数组的长度）。 典型的JIT编译器（显然）无法优化这些。 （事实上​​，你不希望优化内部数组，因为这是允许ArrayList增长的原因。）

• 对于数组的基元，相应的列表类型涉及包装的基元类型/对象，这增加了开销。 例如，您的result += ...涉及“列表”案例中的拆箱。

我的基准写得好吗？ 换句话说，我的结果是否准确？

技术上没有任何问题。 但这还不足以certificate你的观点。 首先，您只测量一种操作：数组元素提取及其等价物。 而你只是测量原始类型。

---

最后，这很大程度上忽略了使用List类型的重点。 我们使用它们因为它们几乎总是比普通数组更容易使用 。 （例如）2的性能差异通常对整体应用性能不重要。

Answer 2

请记住，在使用ArrayList时，实际上是在调用一个函数，在get()的情况下，它实际上会调用另外两个函数。 （其中一个是范围检查，我怀疑这可能是延迟的一部分）。

与ArrayList相比，ArrayList的重要之处在于它的访问时间总是不变的（如数组）。 在现实世界中，您几乎总会发现增加的延迟可以忽略不计。 特别是如果您有一个甚至考虑连接到数据库的应用程序。 🙂

简而言之，我认为你的测试（和结果）是合法的。

Answer 3

这些结果并不让我感到惊讶。 List.get(int)涉及一个转换，它很慢。 Java的generics是通过类型擦除实现的，这意味着任何类型的List实际上都是List ，并且你输入类型的唯一原因是由于强制转换。 ArrayList的源代码如下：

 public E get(int index) { rangeCheck(index); return elementData(index); } // snip... private void rangeCheck(int index) { if (index >= size) throw new IndexOutOfBoundsException(outOfBoundsMsg(index)); } // snip... @SuppressWarnings("unchecked") E elementData(int index) { return (E) elementData[index]; } 

rangeCheck和函数调用的开销是微不足道的，它会rangeCheck为E来杀死你。

Answer 4

如果存储数百万个对象，则Add或Contains函数将非常慢。 最好的方法是使用Arrays的hashMap拆分它。 虽然类似的算法可以用于其他类型的对象，但这就是我对1000万个字符串的处理速度提高1000倍（所占用的内存是2-3倍）

 public static class ArrayHashList { private String temp1, temp2; HashMap allKeys = new HashMap(); ArrayList curKeys; private int keySize; public ArrayHashList(int keySize) { this.keySize = keySize; } public ArrayHashList(int keySize, String fromFileName) { this.keySize = keySize; String line; try{ BufferedReader br1 = new BufferedReader(new FileReader(fromFileName)); while ((line = br1.readLine()) != null) addString(line); br1.close(); }catch(Exception e){ e.printStackTrace(); } } public boolean addString(String strToAdd) { if (strToAdd.length() 

初始化并使用它：

 ArrayHashList fullHlist = new ArrayHashList(3, filesPath+"\\allPhrases.txt"); ArrayList pendingList = new ArrayList(); BufferedReader br1 = new BufferedReader(new FileReader(filesPath + "\\processedPhrases.txt")); while ((line = br1.readLine()) != null) { wordEnc = StrUtil.GetFirstToken(line,",~~~,"); if (!fullHlist.haveString(wordEnc)) pendingList.add(wordEnc); } br1.close();