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

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

Stephen C.. 5

首先 ...

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

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

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

为什么ArrayList这么慢？

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

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

对于数组的基元,相应的列表类型涉及包装的基元类型/对象,这增加了开销.例如,您result += ...需要在"列表"案例中进行拆箱.

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

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

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

撰写答案