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

a6b3iqyw  于 2021-06-30  发布在  Java
关注(0)|答案(9)|浏览(358)

我必须在内存中保留数千个字符串,以便在java中串行访问。我应该将它们存储在数组中还是使用某种列表?
由于数组将所有数据保存在一个连续的内存块中(与列表不同),使用数组存储数千个字符串会导致问题吗?

dgenwo3n

dgenwo3n1#

尽管建议使用arraylist的答案在大多数情况下都是有意义的,但相对性能的实际问题还没有真正得到回答。
使用数组可以执行以下操作:
创造它
设置项目
获取项目
克隆/复制

一般结论

尽管在arraylist上get和set操作稍微慢一点。在我的机器上,每次调用1到3纳秒),使用arraylist与使用数组进行任何非密集型使用相比,开销非常小。不过,有几件事需要记住:
调整列表上的操作大小(调用 list.add(...) )成本很高,应尽可能将初始容量设置为适当的水平(注意,使用阵列时也会出现相同的问题)
在处理原语时,数组可以大大加快速度,因为它们可以避免许多装箱/拆箱转换
仅获取/设置arraylist中的值的应用程序(不太常见!)通过切换到阵列,性能可以提高25%以上

详细结果

下面是我在标准x86桌面机上使用jmh基准库(时间单位为纳秒)和jdk7对这三个操作测量的结果。请注意,在测试中从不调整arraylist的大小,以确保结果具有可比性。这里提供基准代码。

数组/数组列表创建

我运行了4个测试,执行以下语句:
创建阵列1: Integer[] array = new Integer[1]; 创建列表1: 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个测试,执行以下语句:
获取列表: return list.get(0); 获取数组: return array[0]; 结果(每次呼叫的纳秒数,95%置信度):

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

结论:从数组中获取数据的速度比从数组列表中获取数据的速度快25%左右,尽管两者之间的差异只有一纳秒左右。

集合操作

我运行了2个测试,执行以下语句:
集合列表: list.set(0, value); 集合数组: array[0] = value; 结果(每次调用的纳秒数):

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

结论:数组上的set操作比列表上的快40%左右,但是对于get来说,每个set操作都需要几纳秒的时间——因此要使差异达到1秒,就需要在列表/数组中设置数亿次项!

克隆/复制

arraylist的副本构造函数委托给 Arrays.copyOf 因此性能与数组复制(通过 clone , Arrays.copyOf 或者 System.arrayCopy 对性能没有实质性影响)。

wb1gzix0

wb1gzix02#

我编写了一个小基准来比较数组列表和数组。在我的老式ish笔记本电脑上,遍历5000个元素的arraylist的时间是1000次,比等效的数组代码慢了大约10毫秒。
所以,如果你什么也不做,只是重复列表,而且你做了很多,那么也许它值得优化。否则我会使用这个列表,因为当您确实需要优化代码时,它会让您更容易。
n、 我注意到使用 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();
        }
    }
}
eiee3dmh

eiee3dmh3#

我同意,在大多数情况下,您应该选择ArrayList而不是ArrayList的灵活性和优雅性—在大多数情况下,对程序性能的影响可以忽略不计。
然而,如果你在做持续的、繁重的迭代,而结构变化很小(没有添加和删除),比如说,软件图形渲染或定制虚拟机,我的顺序访问基准测试表明,ArrayList比我系统上的数组慢1.5倍(我一年前的imac上的Java1.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
    }
}
nwlqm0z1

nwlqm0z14#

您应该更喜欢泛型类型而不是数组。正如其他人提到的,数组是不灵活的,没有泛型类型的表达能力(不过,它们确实支持运行时类型检查,但这与泛型类型混合得很差。)
但是,像往常一样,在优化时,您应该始终遵循以下步骤:
不要优化,直到你有一个好的,干净的,工作版本的代码。在这一步中,可以很好地鼓励更改为泛型类型。
当你有一个版本是好的和干净的,决定它是否足够快。
如果速度不够快,请测量其性能。这一步之所以重要有两个原因。如果你不去衡量,你就不会(1)知道你所做的任何优化的影响,(2)知道在哪里进行优化。
优化代码中最热门的部分。
再测量一次。这和以前的测量一样重要。如果优化没有改善情况,请还原它。请记住,没有优化的代码是干净的、漂亮的、有效的。

sigwle7e

sigwle7e5#

我猜原来的海报是来自一个c++/stl的背景,这引起了一些混乱。在cstd::list 是一个双链表。
在java中 [java.util.]List 是一个无需实现的接口(c
术语中的纯抽象类)。 List 可以是双链接列表- java.util.LinkedList 提供。但是,如果你想做一个新的,100次中有99次 List ,您要使用 java.util.ArrayList 相反,它大致相当于c++ std::vector . 还有其他标准实现,例如 java.util.Collections.emptyList() 以及 java.util.Arrays.asList() .
从性能的Angular 来看,必须通过一个接口和一个额外的对象只会带来很小的影响,但是运行时内联意味着这很少有任何意义。还记得吗 String 通常是对象加数组。因此,对于每个条目,可能还有两个其他对象。在c++中 std::vector<std::string> ,尽管按值复制而不使用指针,但字符数组将形成字符串的对象(通常不会共享这些对象)。
如果这段代码对性能非常敏感,您可以创建一个 char[] 数组(或偶数) byte[] )所有字符串的所有字符,然后是偏移量数组。iirc,javac就是这样实现的。

oyt4ldly

oyt4ldly6#

不,因为从技术上讲,数组只存储对字符串的引用。字符串本身被分配到不同的位置。对于一千个项目,我会说一个列表会更好,它会更慢,但它提供了更大的灵活性和更容易操作

t8e9dugd

t8e9dugd7#

我建议您使用探查器来测试哪个更快。
我个人的意见是你应该使用列表。
我在一个大型的代码库上工作,以前的一组开发人员在任何地方都使用数组。这使得代码非常不灵活。把它的大块内容改成列表后,我们没有注意到速度上的差别。

polhcujo

polhcujo8#

java的方式是您应该考虑哪些数据抽象最适合您的需要。请记住,在java中,列表是一种抽象的数据类型,而不是具体的数据类型。您应该将字符串声明为列表,然后使用arraylist实现对其进行初始化。

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

这种抽象数据类型和具体实现的分离是面向对象编程的一个关键方面。
arraylist使用数组作为其底层实现来实现列表抽象数据类型。访问速度实际上与数组相同,还有一个额外的优点,即可以向列表中添加和减去元素(尽管这是一个带有arraylist的o(n)操作),而且如果您决定稍后更改底层实现,则可以。例如,如果意识到需要同步访问,可以将实现更改为向量,而无需重写所有代码。
事实上,arraylist是专门为在大多数上下文中替换低级数组构造而设计的。如果java是在今天设计的,那么完全有可能数组会被完全排除在外,取而代之的是arraylist结构。
由于数组将所有数据保存在一个连续的内存块中(与列表不同),使用数组存储数千个字符串会导致问题吗?
在java中,所有集合只存储对对象的引用,而不是对象本身。arrays和arraylist都将在一个连续的数组中存储几千个引用,因此它们本质上是相同的。您可以认为,在现代硬件上,几千个32位引用的连续块始终是可用的。当然,这并不能保证您不会完全耗尽内存,只是连续的内存块需求不难满足。

rjjhvcjd

rjjhvcjd9#

首先,有必要澄清一下,您是指经典comp-sci数据结构意义上的“列表”(即链表)还是指java.util.list?如果您指的是java.util.list,那么它就是一个接口。如果您想使用数组,只需使用arraylist实现,就会得到类似数组的行为和语义。问题解决了。
如果你指的是一个数组和一个链表,这是一个稍微不同的参数,我们回到big o(如果这是一个不熟悉的术语,这里有一个简单的英语解释)。
阵列;
随机存取:o(1);
插入:o(n);
删除:o(n)。
链表:
随机存取:o(n);
插入:o(1);
删除:o(1)。
因此,您可以选择最适合调整数组大小的方法。如果你调整大小,插入和删除很多那么也许一个链表是一个更好的选择。如果随机存取很少,情况也是如此。你提到串行访问。如果你主要做的是串行访问,修改很少,那么你选择哪一个可能无关紧要。
链表的开销稍高,因为正如您所说的,您要处理的是潜在的非连续内存块和(有效地)指向下一个元素的指针。这可能不是一个重要的因素,除非你正在处理数以百万计的条目。

相关问题