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

Question

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

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

Answer 1

我建议您使用分析器来测试哪个更快.

我个人认为你应该使用列表.

我在一个大型代码库上工作,而前一组开发人员在任何地方使用数组.它使代码非常不灵活.在将大块的大块改为Lists后,我们注意到速度没有差异.

Answer 2

Java的方式是你应该考虑哪种数据抽象最适合你的需求.请记住,在Java中,List是一个抽象,而不是具体的数据类型.您应该将字符串声明为List,然后使用ArrayList实现对其进行初始化.

List<String> strings = new ArrayList<String>();

抽象数据类型和具体实现的这种分离是面向对象编程的关键方面之一.

ArrayList使用数组作为其底层实现来实现List Abstract Data Type.访问速度几乎与数组相同,还有一个额外的优点,即能够向List添加和减去元素(尽管这是一个带有ArrayList的O(n)操作),如果您决定稍后更改底层实现您可以.例如,如果您意识到需要同步访问,则可以将实现更改为Vector,而无需重写所有代码.

实际上,ArrayList是专门为在大多数情况下替换低级数组构造而设计的.如果今天设计Java,完全有可能完全省略数组以支持ArrayList结构.

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

在Java中,所有集合仅存储对象的引用,而不存储对象本身.数组和ArrayList都会在连续数组中存储几千个引用,因此它们基本相同.您可以考虑在现代硬件上始终可以使用几千个32位引用的连续块.这并不能保证你不会完全耗尽内存,当然,只是内存需求的连续块不难实现.

Answer 3

您应该更喜欢泛型类型而不是数组.正如其他人所提到的,数组是不灵活的,并且没有泛型类型的表达能力.(但它们确实支持运行时类型检查,但是它与泛型类型混合得很厉害.)

但是,与往常一样,优化时应始终遵循以下步骤:

• 在您拥有一个漂亮,干净且有效的代码版本之前,请不要进行优化.在这一步骤中,很可能会改变通用类型.
• 如果您的版本很干净,请确定它是否足够快.
• 如果速度不够快,请测量其性能.这一步很重要,原因有两个.如果您不衡量,您将不会(1)知道您所做的任何优化的影响,以及(2)知道优化的位置.
• 优化代码中最热门的部分.
• 再次测量.这和以前测量一样重要.如果优化没有改善,恢复它.请记住,没有优化的代码是干净,漂亮和有效的.

Answer 4

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

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

• 创造它
• 设置一个项目
• 得到一个项目
• 克隆/复制它

总结论

虽然在ArrayList上的get和set操作稍慢(在我的机器上每次调用分别为1和3纳秒),但对于任何非密集使用,使用ArrayList与数组的开销很小.但是要记住一些事情:

• 调整列表上的操作(调用时list.add(...))是昂贵的,并且应尽可能尝试将初始容量设置在适当的水平(请注意,使用数组时会出现同样的问题)
• 在处理基元时,数组可以明显更快,因为它们可以避免许多装箱/拆箱转换
• 只在ArrayList中获取/设置值的应用程序(不常见!)通过切换到数组可以看到性能增益超过25%

详细结果

以下是我在标准x86台式机上使用jmh基准测试库(以纳秒为单位)和JDK 7 测量的三个操作的结果.请注意,ArrayList在测试中从不调整大小以确保结果具有可比性.基准代码可在此处获得.

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]

结论:没有明显的差异.

获得运营

我运行了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]

结论:从数组获取数据的速度比从ArrayList获取速度快25%,尽管差异仅在1纳秒的数量级.

设定运作

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

• 设置列表: 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]

结论:对数组的集合操作比列表快40%,但是,对于get,每个集合操作需要几纳秒 - 因此差异达到1秒,需要在列表/数组中设置数百个项目数百万次!

克隆/复制

ArrayList的复制构造函数委托给,Arrays.copyOf因此性能与数组副本相同(通过复制数组clone,Arrays.copyOf或System.arrayCopy 在性能方面没有任何重大差异).

Answer 5

我猜测原始海报来自C++/STL背景,这引起了一些混乱.在C++中std::list是一个双向链表.

Java中[java.util.]List是一个无实现的接口(C++术语中的纯抽象类).List可以是一个双重链表 - java.util.LinkedList提供.但是,当你想要一个新的时候List,你想要使用的是100次中的99次java.util.ArrayList,这是C++的粗略等价物std::vector.还有其他标准实现,例如由java.util.Collections.emptyList()和返回的实现java.util.Arrays.asList().

从性能的角度来看,不得不通过一个接口和一个额外的对象,但是运行时内联意味着这很少有任何意义.还要记住,String它通常是一个对象加数组.因此,对于每个条目,您可能还有另外两个对象.在C++中std::vector<std::string>,尽管没有指针按值复制,但字符数组将形成字符串对象(通常不会共享这些对象).

如果此特定代码对性能非常敏感,则可以为所有字符串的所有字符创建单个char[]数组(或甚至byte[]),然后创建一个偏移数组.IIRC,这就是javac的实施方式.

Answer 6

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

但是,如果你在软件图形渲染或自定义虚拟机上进行持续的重复迭代而几乎没有结构变化(没有添加和删除),我的顺序访问基准测试表明,ArrayLists比我的数组慢1.5倍系统(我一岁的iMac上的Java 1.6).

一些代码:

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

Answer 7

首先,值得澄清的是你在经典的comp sci数据结构意义上的意思是"列表"(即链表)或者你的意思是java.util.List？如果你的意思是java.util.List,那就是一个接口.如果你想使用数组,只需使用ArrayList实现,你将获得类似数组的行为和语义.问题解决了.

如果你的意思是一个数组与一个链表,那就是我们回到Big O的一个稍微不同的论点(如果这是一个不熟悉的术语,这里是一个简单的英语解释.

阵列;

• 随机访问:O(1);
• 插入:O(n);
• 删除:O(n).

链接列表:

• 随机访问:O(n);
• 插入:O(1);
• 删除:O(1).

因此,您可以选择最适合您调整阵列大小的那个.如果您调整大小,插入和删除很多,那么链接列表可能是更好的选择.如果随机访问很少,则同样如此.你提到串行访问.如果你主要是通过很少的修改来进行串行访问,那么你选择哪个并不重要.

链接列表的开销略高,因为就像你说的那样,你正在处理潜在的非连续内存块和(有效地)指向下一个元素的指针.除非你处理数百万条款,否则这可能不是一个重要的因素.

Answer 8

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

所以,如果你只是在迭代列表,而你正在做很多事情,那么也许值得进行优化.否则,我会使用列表中,因为它会更容易,当你做需要优化的代码.

我确实注意到使用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();
        }
    }
}

Answer 9

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

Answer 10

列表比数组慢。如果需要效率，请使用数组。如果需要灵活性，请使用列表。

Answer 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中的空间要小.

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

Answer 12

我来到这里是为了更好地了解在数组上使用列表对性能的影响。我不得不为我的场景修改这里的代码：大约 1000 个整数的数组/列表，主要使用 getter，意思是 array[j] 与 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] 而不是 Integer[1000]

array int[] best 299ms iterator
array int[] best 296ms getter

使用 Integer[] 与 int[] 表示双倍性能命中，带迭代器的 ListArray 比 int[] 慢 3 倍。真的认为 Java 的列表实现类似于本机数组......

参考代码（多次调用）：

    public static void testArray()
    {
        final long MAX_ITERATIONS = 1000000;
        final int MAX_LENGTH = 1000;

        Random r = new Random();

        //Integer[] array = new Integer[MAX_LENGTH];
        int[] array = new int[MAX_LENGTH];

        List<Integer> list = new ArrayList<Integer>()
        {{
            for (int i = 0; i < MAX_LENGTH; ++i)
            {
                int val = r.nextInt();
                add(val);
                array[i] = val;
            }
        }};

        long start = System.currentTimeMillis();
        int test_sum = 0;
        for (int i = 0; i < MAX_ITERATIONS; ++i)
        {
//          for (int e : array)
//          for (int e : list)          
            for (int j = 0; j < MAX_LENGTH; ++j)
            {
                int e = array[j];
//              int e = list.get(j);
                test_sum += e;
            }
        }

        long stop = System.currentTimeMillis();

        long ms = (stop - start);
        System.out.println("Time: " + ms);
    }

Answer 13

如果您事先知道数据有多大，那么数组会更快。

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

Answer 14

更新:

正如Mark所说,在JVM预热(几次测试通过)之后没有显着差异.检查重新创建的数组甚至是新行矩阵开始的新传递.很有可能这标志着具有索引访问权限的简单数组不能用于集合.

仍然是前1-2次传递简单阵列快2-3倍.

原始邮寄:

太多的单词对于主题太简单无法检查.没有任何问题,数组比任何类容器快几倍.我运行这个问题寻找我的性能关键部分的替代品.这是我为检查实际情况而构建的原型代码:

import java.util.List;
import java.util.Arrays;

public class IterationTest {

    private static final long MAX_ITERATIONS = 1000000000;

    public static void main(String [] args) {

        Integer [] array = {1, 5, 3, 5};
        List<Integer> list = Arrays.asList(array);

        long start = System.currentTimeMillis();
        int test_sum = 0;
        for (int i = 0; i < MAX_ITERATIONS; ++i) {
//            for (int e : array) {
            for (int e : list) {
                test_sum += e;
            }
        }
        long stop = System.currentTimeMillis();

        long ms = (stop - start);
        System.out.println("Time: " + ms);
    }
}

这是答案:

基于数组(第16行有效):

Time: 7064

基于列表(第17行有效):

Time: 20950

还有更多关于'更快'的评论？这是很清楚的.问题是当你比List的灵活性更快3倍的时候.但这是另一个问题.顺便说一下,我也基于手工构建了这个ArrayList.几乎相同的结果.

Answer 15

由于这里已经有很多好的答案,我想给你一些实用视图的其他信息,即插入和迭代性能比较:原始数组与Java中的Linked-list.

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

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

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.");
    }
}

绩效结果如下: