首页 文章

Java中的数组或列表 . 哪个更快?

提问于
浏览
317

我必须在内存中保留数千个字符串,以便在Java中以串行方式访问 . 我应该将它们存储在数组中还是应该使用某种List?

由于数组将所有数据保存在连续的内存块中(与Lists不同),使用数组存储数千个字符串会导致问题吗?

Answer: 共识是,绩效差异很小 . List接口提供更大的灵活性 .

30 回答

  • 5

    没有一个答案有我感兴趣的信息 - 多次重复扫描同一阵列 . 不得不为此创建一个JMH测试 .

    Results (Java 1.8.0_66 x32,迭代普通数组至少比ArrayList快5倍):

    Benchmark                    Mode  Cnt   Score   Error  Units
    MyBenchmark.testArrayForGet  avgt   10   8.121 ? 0.233  ms/op
    MyBenchmark.testListForGet   avgt   10  37.416 ? 0.094  ms/op
    MyBenchmark.testListForEach  avgt   10  75.674 ? 1.897  ms/op
    

    Test

    package my.jmh.test;
    
    import java.util.ArrayList;
    import java.util.List;
    import java.util.concurrent.TimeUnit;
    import org.openjdk.jmh.annotations.Benchmark;
    import org.openjdk.jmh.annotations.BenchmarkMode;
    import org.openjdk.jmh.annotations.Fork;
    import org.openjdk.jmh.annotations.Measurement;
    import org.openjdk.jmh.annotations.Mode;
    import org.openjdk.jmh.annotations.OutputTimeUnit;
    import org.openjdk.jmh.annotations.Scope;
    import org.openjdk.jmh.annotations.State;
    import org.openjdk.jmh.annotations.Warmup;
    
    @State(Scope.Benchmark)
    @Fork(1)
    @Warmup(iterations = 5, timeUnit = TimeUnit.SECONDS)
    @Measurement(iterations = 10)
    @BenchmarkMode(Mode.AverageTime)
    @OutputTimeUnit(TimeUnit.MILLISECONDS)
    public class MyBenchmark {
    
        public final static int ARR_SIZE = 100;
        public final static int ITER_COUNT = 100000;
    
        String arr[] = new String[ARR_SIZE];
        List<String> list = new ArrayList<>(ARR_SIZE);
    
        public MyBenchmark() {
            for( int i = 0; i < ARR_SIZE; i++ ) {
                list.add(null);
            }
        }
    
        @Benchmark
        public void testListForEach() {
            int count = 0;
            for( int i = 0; i < ITER_COUNT; i++ ) {
                for( String str : list ) {
                    if( str != null )
                        count++;
                }
            }
            if( count > 0 )
                System.out.print(count);
        }
    
        @Benchmark
        public void testListForGet() {
            int count = 0;
            for( int i = 0; i < ITER_COUNT; i++ ) {
                for( int j = 0; j < ARR_SIZE; j++ ) {
                    if( list.get(j) != null )
                        count++;
                }
            }
            if( count > 0 )
                System.out.print(count);
        }
    
        @Benchmark
        public void testArrayForGet() {
            int count = 0;
            for( int i = 0; i < ITER_COUNT; i++ ) {
                for( int j = 0; j < ARR_SIZE; j++ ) {
                    if( arr[j] != null )
                        count++;
                }
            }
            if( count > 0 )
                System.out.print(count);
        }
    
    }
    
  • 91

    数组更快 - 所有内存都预先分配 .

  • 82

    如果事先知道数据有多大,那么数组会更快 .

    列表更灵活 . 您可以使用由数组支持的ArrayList .

  • 11

    如果您有数千人,请考虑使用trie . trie是一种树状结构,它合并了存储字符串的公共前缀 .

    例如,如果字符串是

    intern
    international
    internationalize
    internet
    internets
    

    特里会存储:

    intern
     -> \0
     international
     -> \0
     -> ize\0
     net
     ->\0
     ->s\0
    

    字符串需要57个字符(包括空终止符'\ 0')来存储,加上包含它们的String对象的大小 . (实际上,我们可能应该将所有大小四舍五入到16的倍数,但是......)称之为57 5 = 62字节,粗略 .

    trie需要29(包括空终止符,'\ 0')用于存储,加上trie节点的大小,它是对数组的引用和子trie节点的列表 .

    对于这个例子,这可能是相同的;对于成千上万的人来说,只要你有共同的前缀,它就可能会少出来 .

    现在,在其他代码中使用trie时,您必须转换为String,可能使用StringBuffer作为中介 . 如果许多字符串同时作为字符串使用,在特里,这是一个损失 .

    但是,如果你当时只使用一些 - 比如说,在字典中查找东西 - 特里可以为你节省很多空间 . 绝对比将它们存储在HashSet中的空间要小 .

    你说你正在“连续”地访问它们 - 如果这意味着按字母顺序依次访问它们,那么如果你以深度优先的方式迭代它,那么它也显然可以免费提供字母顺序 .

  • 2

    取决于实施 . 原始类型数组可能比ArrayList更小,更有效 . 这是因为数组将直接将值存储在连续的内存块中,而最简单的ArrayList实现将存储指向每个值的指针 . 特别是在64位平台上,这可以产生巨大的差异 .

    当然,对于这种情况,jvm实现可能有一个特殊情况,在这种情况下性能将是相同的 .

  • 2

    尽管建议使用ArrayList的答案在大多数情况下都有意义,但实际的相对性能问题还没有真正得到解答 .

    您可以使用数组执行以下操作:

    • 创造它

    • 设置了一个项目

    • 得到一个项目

    • 克隆/复制它

    总结论

    Although get and set operations are somewhat slower on an ArrayList (在我的机器上每次呼叫分别为1和3纳秒), there is very little overhead of using an ArrayList vs. an array for any non-intensive use. 但是有一些事情要记住:

    • 列表上的调整操作(调用 list.add(...) 时)成本很高,并且应尽可能尝试将初始容量设置在适当的水平(请注意,使用数组时会出现同样的问题)

    • 处理基元时,数组可以明显更快,因为它们可以避免许多装箱/拆箱转换

    • 只在ArrayList中获取/设置值的应用程序(不常见!)通过切换到数组可以看到性能增益超过25%

    详细结果

    以下是我在标准x86台式机上使用JDK 7使用jmh benchmarking library(以纳秒为单位)的三个操作测量的结果 . 请注意,ArrayList永远不会在测试中调整大小以确保结果具有可比性 . Benchmark code available here .

    Array / ArrayList创建

    我运行了4个测试,执行以下语句:

    • createArray1: Integer[] array = new Integer[1];

    • createList1: List<Integer> list = new ArrayList<> (1);

    • createArray10000: Integer[] array = new Integer[10000];

    • createList10000: List<Integer> list = new ArrayList<> (10000);

    结果(每次通话以纳秒为单位,95%置信度):

    a.p.g.a.ArrayVsList.CreateArray1         [10.933, 11.097]
    a.p.g.a.ArrayVsList.CreateList1          [10.799, 11.046]
    a.p.g.a.ArrayVsList.CreateArray10000    [394.899, 404.034]
    a.p.g.a.ArrayVsList.CreateList10000     [396.706, 401.266]
    

    Conclusion: no noticeable difference .

    获取操作

    我运行了2个测试,执行以下语句:

    • getList: return list.get(0);

    • getArray: return array[0];

    结果(每次通话以纳秒为单位,95%置信度):

    a.p.g.a.ArrayVsList.getArray   [2.958, 2.984]
    a.p.g.a.ArrayVsList.getList    [3.841, 3.874]
    

    Conclusion: getting from an array is about 25% faster 比从ArrayList获取,虽然差异只有一纳秒的量级 .

    设置操作

    我运行了2个测试,执行以下语句:

    • setList: list.set(0, value);

    • setArray: array[0] = value;

    结果(每次通话以纳秒为单位):

    a.p.g.a.ArrayVsList.setArray   [4.201, 4.236]
    a.p.g.a.ArrayVsList.setList    [6.783, 6.877]
    

    Conclusion: set operations on arrays are about 40% faster 而不是列表,但是,至于get,每个设置操作需要几纳秒 - 因此差异达到1秒,需要在列表/数组中设置数亿次!

    克隆/复制

    ArrayList的复制构造函数委托给 Arrays.copyOf ,因此性能与数组副本相同(通过 cloneArrays.copyOfSystem.arrayCopy makes no material difference performance-wise复制数组) .

  • 1

    我同意在大多数情况下你应该选择灵活性和优雅阵列上的ArrayLists - 在大多数情况下,对程序性能的影响可以忽略不计 .

    但是,如果你在软件图形渲染或自定义虚拟机上做很少的结构更改(没有添加和删除)的重复迭代,我的顺序访问基准测试显示我的系统上的 ArrayLists are 1.5x slower than arrays (我的Java 1.6)一岁的iMac) .

    一些代码:

    import java.util.*;
    
    public class ArrayVsArrayList {
        static public void main( String[] args ) {
    
            String[] array = new String[300];
            ArrayList<String> list = new ArrayList<String>(300);
    
            for (int i=0; i<300; ++i) {
                if (Math.random() > 0.5) {
                    array[i] = "abc";
                } else {
                    array[i] = "xyz";
                }
    
                list.add( array[i] );
            }
    
            int iterations = 100000000;
            long start_ms;
            int sum;
    
            start_ms = System.currentTimeMillis();
            sum = 0;
    
            for (int i=0; i<iterations; ++i) {
              for (int j=0; j<300; ++j) sum += array[j].length();
            }
    
            System.out.println( (System.currentTimeMillis() - start_ms) + " ms (array)" );
            // Prints ~13,500 ms on my system
    
            start_ms = System.currentTimeMillis();
            sum = 0;
    
            for (int i=0; i<iterations; ++i) {
              for (int j=0; j<300; ++j) sum += list.get(j).length();
            }
    
            System.out.println( (System.currentTimeMillis() - start_ms) + " ms (ArrayList)" );
            // Prints ~20,800 ms on my system - about 1.5x slower than direct array access
        }
    }
    
  • 334

    你可以使用固定大小,阵列将更快,需要更少的内存 .

    如果您需要使用List接口的灵活性来添加和删除元素,那么问题仍然是您应该选择哪种实现 . 建议使用ArrayList并将其用于任何情况,但如果必须删除或插入列表开头或中间的元素,ArrayList也会出现性能问题 .

    因此,您可能需要查看引入GapList的http://java.dzone.com/articles/gaplist-%E2%80%93-lightning-fast-list . 这个新的列表实现结合了ArrayList和LinkedList的优势,几乎可以为所有操作提供非常好的性能 .

  • 3

    我写了一个小基准来比较ArrayLists和Arrays . 在我的旧式笔记本电脑上,遍历5000个元素的arraylist 1000次的时间比等效的数组代码慢大约10毫秒 .

    所以,如果你做了很多事情,那么也许它会使用List,因为当你需要优化代码时它会更容易 .

    注:我注意到使用 for String s: stringsList 比使用旧式for循环访问列表慢了约50% . 去图......这是我定时的两个功能;数组和列表填充了5000个随机(不同)字符串 .

    private static void readArray(String[] strings) {
        long totalchars = 0;
        for (int j = 0; j < ITERATIONS; j++) {
            totalchars = 0;
            for (int i = 0; i < strings.length; i++) {
                totalchars += strings[i].length();
    
            }
        }
    }
    
    private static void readArrayList(List<String> stringsList) {
        long totalchars = 0;
        for (int j = 0; j < ITERATIONS; j++) {
            totalchars = 0;
            for (int i = 0; i < stringsList.size(); i++) {
                totalchars += stringsList.get(i).length();
            }
        }
    }
    
  • 0

    ArrayList在内部使用数组对象来添加(或存储)元素 . 换句话说,ArrayList由Array data -structure支持.ArrayList的数组是可调整大小的(或动态的) .

    Array is faster than Array 因为ArrayList内部使用数组 . 如果我们可以直接在Array中添加元素并通过ArrayList间接地在Array中添加元素,那么直接机制就比间接机制快 .

    ArrayList类中有两个重载的add()方法:

    1. add(Object) :将对象添加到列表的末尾 .
    2. add(int index , Object ) :将指定的对象插入列表中的指定位置 .

    How the size of ArrayList grows dynamically?

    public boolean add(E e)        
    {       
         ensureCapacity(size+1);
         elementData[size++] = e;         
         return true;
    }
    

    从上面的代码中要注意的重点是我们在添加元素之前检查ArrayList的容量 . ensureCapacity()确定占用元素的当前大小是什么,以及数组的最大大小是多少 . 如果填充元素的大小(包括要添加到ArrayList类的新元素)大于数组的最大大小,则增加数组的大小 . 但是数组的大小不能动态增加 . 那么内部发生的是新的数据是用容量创建的

    直到Java 6

    int newCapacity = (oldCapacity * 3)/2 + 1;
    

    (更新)来自Java 7

    int newCapacity = oldCapacity + (oldCapacity >> 1);
    

    此外,旧数组中的数据也会复制到新数组中 .

    在ArrayList中使用开销方法,这就是Array比 ArrayList 更快的原因 .

  • 1

    不,因为从技术上讲,数组只存储对字符串的引用 . 字符串本身分配在不同的位置 . 对于一千个项目,我会说一个列表会更好,它更慢,但它提供了更大的灵活性,它更容易使用,特别是如果你要调整它们 .

  • 1

    由于这里已经有很多好的答案,我想给你一些实用观点的其他信息,这是 insertion and iteration performance comparison : primitive array vs Linked-list in Java.

    这是实际的简单性能检查 .
    因此,结果将取决于机器性能 .

    用于此目的的源代码如下:

    import java.util.Iterator;
    import java.util.LinkedList;
    
    public class Array_vs_LinkedList {
    
        private final static int MAX_SIZE = 40000000;
    
        public static void main(String[] args) {
    
            LinkedList lList = new LinkedList(); 
    
            /* insertion performance check */
    
            long startTime = System.currentTimeMillis();
    
            for (int i=0; i<MAX_SIZE; i++) {
                lList.add(i);
            }
    
            long stopTime = System.currentTimeMillis();
            long elapsedTime = stopTime - startTime;
            System.out.println("[Insert]LinkedList insert operation with " + MAX_SIZE + " number of integer elapsed time is " + elapsedTime + " millisecond.");
    
            int[] arr = new int[MAX_SIZE];
    
            startTime = System.currentTimeMillis();
            for(int i=0; i<MAX_SIZE; i++){
                arr[i] = i; 
            }
    
            stopTime = System.currentTimeMillis();
            elapsedTime = stopTime - startTime;
            System.out.println("[Insert]Array Insert operation with " + MAX_SIZE + " number of integer elapsed time is " + elapsedTime + " millisecond.");
    
    
            /* iteration performance check */
    
            startTime = System.currentTimeMillis();
    
            Iterator itr = lList.iterator();
    
            while(itr.hasNext()) {
                itr.next();
                // System.out.println("Linked list running : " + itr.next());
            }
    
            stopTime = System.currentTimeMillis();
            elapsedTime = stopTime - startTime;
            System.out.println("[Loop]LinkedList iteration with " + MAX_SIZE + " number of integer elapsed time is " + elapsedTime + " millisecond.");
    
    
            startTime = System.currentTimeMillis();
    
            int t = 0;
            for (int i=0; i < MAX_SIZE; i++) {
                t = arr[i];
                // System.out.println("array running : " + i);
            }
    
            stopTime = System.currentTimeMillis();
            elapsedTime = stopTime - startTime;
            System.out.println("[Loop]Array iteration with " + MAX_SIZE + " number of integer elapsed time is " + elapsedTime + " millisecond.");
        }
    }
    

    表现结果如下:

    enter image description here

  • 2

    我来到这里是为了更好地了解使用列表对阵列的性能影响 . 我必须在这里为我的场景调整代码:使用大多数getter的~1000 int的数组/列表,意思是array [j] vs list.get(j)

    最好的7是不科学的(前几个列表,其中2.5倍慢)我得到这个:

    array Integer[] best 643ms iterator
    ArrayList<Integer> best 1014ms iterator
    
    array Integer[] best 635ms getter
    ArrayList<Integer> best 891ms getter (strange though)
    
    • 所以,阵列快了大约30%

    现在发布的第二个原因是,如果您使用嵌套循环执行数学/矩阵/模拟/优化代码,则没有人提到这种影响 .

    假设您有三个嵌套级别,内部循环速度是您查看8次性能命中的两倍 . 现在运行的东西需要一周时间 .

    *编辑在这里非常震惊,因为踢我试图声明int [1000]而不