小开

如果提前知道数据有多大，那么使用数组会更快。

List更加灵活。你可以使用由数组支持的数组列表。

小开

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

小开

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

小开

最佳答案

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

我个人的观点是你应该使用列表。

我在一个大型代码库上工作，以前的一组开发人员使用数组到处都是。这使得代码非常不灵活。在将大块数据转换为列表后，我们发现速度没有变化。

小开

A List更灵活....所以List比array更好

小开

Java的方法是你应该考虑什么数据抽象最适合你的需要。记住，在Java中，List是抽象的数据类型，而不是具体的数据类型。您应该将字符串声明为List，然后使用ArrayList实现初始化它。

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

抽象数据类型和特定实现的分离是面向对象编程的一个关键方面。

数组列表使用数组作为其底层实现来实现列表抽象数据类型。访问速度几乎与数组相同，具有能够向List添加和减去元素的额外优势(尽管这是一个O(n)操作，对于ArrayList)，如果您决定稍后更改底层实现，您可以这样做。例如，如果您意识到需要同步访问，则可以将实现更改为Vector，而无需重写所有代码。

事实上，ArrayList是专门为在大多数情况下替换低级数组构造而设计的。如果Java是今天设计的，那么完全有可能将数组完全排除在外，转而使用数组列表结构。

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

在Java中，所有的集合只存储对对象的引用，而不是对象本身。数组和ArrayList都将在一个连续数组中存储几千个引用，因此它们本质上是相同的。您可以认为，在现代硬件上，由数千个32位引用组成的连续块总是随时可用的。当然，这并不能保证您不会耗尽所有的内存，只是保证连续的内存块需求不难满足。

小开

您应该更喜欢泛型类型而不是数组。正如其他人所提到的，数组是不灵活的，不具有泛型类型的表达能力。(它们确实支持运行时类型检查，但这与泛型类型混在一起很糟糕。)

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

不要优化，直到你有一个漂亮的，干净的，工作版本的代码。转换为泛型类型在这一步已经很有动力了。
当你有了一个漂亮干净的版本时，要判断它是否足够快。
如果它不够快，衡量它的表现。这一步之所以重要，有两个原因。如果你不进行衡量，你就不知道(1)你所做的任何优化的影响，(2)你不知道在哪里优化。
优化代码中最热门的部分。
这和之前的测量一样重要。如果优化没有改善事情，恢复它。记住，代码没有优化是干净，漂亮，工作。

小开

不要在没有适当基准测试的情况下陷入优化的陷阱。正如其他人建议的那样，在做出任何假设之前使用分析器。

您所列举的不同数据结构具有不同的用途。列表在开头和结尾插入元素时非常有效，但在访问随机元素时却很困难。数组具有固定的存储，但提供快速的随机访问。最后，ArrayList通过允许数组增长来改进与数组的接口。通常，要使用的数据结构应该由如何访问或添加存储的数据来决定。

关于内存消耗。你好像把一些东西混在一起了。数组只能为所拥有的数据类型提供连续的内存块。不要忘记java有固定的数据类型:boolean, char, int, long, float和Object(这包括所有对象，甚至数组也是对象)。这意味着如果你声明一个String字符串[1000]或MyObject myObjects[1000]的数组，你只能得到一个1000个足够大的内存盒来存储对象的位置(引用或指针)。你没有1000个足够大的内存盒来容纳这些对象。不要忘记你的对象首先是用“new”创建的。这是当内存分配完成后，一个引用(它们的内存地址)存储在数组中。对象不会被复制到数组中，只复制到它的引用中。

小开

“数千”不是一个很大的数字。几千个段落长度的字符串大小大约是几兆字节。如果你想做的只是连续地访问它们，请使用一个不可变的单链表。

小开

我不认为这对Strings有什么影响。字符串数组中连续的是对字符串的引用，字符串本身存储在内存中的随机位置。

数组与列表的区别在于基本类型，而不是对象。如果你提前知道元素的数量，并且不需要灵活性，一个数百万个整数或双精度数的数组将比列表更有效的内存和略微的速度，因为它们确实是连续存储的，并且可以立即访问。这就是为什么Java仍然使用字符数组表示字符串，使用整数数组表示图像数据，等等。

小开

请记住，ArrayList封装了一个数组，因此与使用原始数组相比没有什么区别(除了在java中使用List更容易)。

选择数组而不是数组列表的唯一有意义的情况是，当你存储基本类型时，比如byte、int等，你需要通过使用基本类型数组获得特定的空间效率。

小开

我猜最初的海报来自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>中，虽然按值复制而没有指针，但字符数组将形成一个string对象(这些对象通常不会共享)。

如果这段代码对性能非常敏感，你可以为所有字符串的所有字符创建一个char[]数组(甚至byte[])，然后创建一个偏移量数组。IIRC，这是javac的实现方式。

小开

首先，有必要澄清一下，您是指经典的compp sci数据结构意义上的“列表”(即链表)，还是指java.util.List?如果你指的是java.util。List，它是一个接口。如果你想使用数组，只要使用数组列表实现，你就会得到类似数组的行为和语义。问题解决了。

如果你指的是数组和链表，它是一个略有不同的参数，我们回到大O(这里是简明英语解释，如果这是一个不熟悉的术语。

数组;

随机存取:O(1);
插入:O (n);
删除:O (n)。

链表:

随机存取:O(n);
插入:O (1);
删除:O(1)。

你可以选择最适合调整数组大小的方法。如果你调整大小，插入和删除很多，那么链表可能是一个更好的选择。如果随机访问很少，情况也是如此。你提到了串行访问。如果你主要做串行访问，很少修改，那么你选择哪一个可能都不重要。

链表的开销略高，因为正如您所说，您正在处理潜在的不连续内存块和(有效地)指向下一个元素的指针。但是，除非您要处理数百万个条目，否则这可能不是一个重要因素。

小开

在存储字符串对象的情况下，数组还是列表的选择并不那么重要(考虑到性能)。因为数组和列表存储的都是字符串对象引用，而不是实际对象。

如果字符串的数量几乎是常数，则使用数组(或ArrayList)。但如果数字变化太大，那么你最好使用LinkedList。
如果有(或将会)需要在中间添加或删除元素，那么你当然必须使用LinkedList。

小开

数组更快-所有内存都是预先分配的。

小开

我写了一个比较数组列表和数组的基准测试。在我的老式笔记本电脑上，遍历5000个元素的数组列表1000次的时间比等效的数组代码慢了大约10毫秒。

所以，如果你什么都不做，只是迭代列表，并且你做了很多，那么也许是值得优化的。否则，我会使用列表，因为它会使它更容易当你做需要优化代码。

n.b.我做了注意到，使用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();
}
}
}

小开

如果你有几千个，考虑使用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节点的sizeof，这些节点是一个数组的引用和一列子trie节点。

在这个例子中，结果可能是一样的;对于成千上万的人来说，只要你有共同的前缀，它可能会更少。

现在，在其他代码中使用trie时，必须转换为String，可能使用StringBuffer作为中介。如果在trie之外，同时使用了许多字符串作为字符串，这是一种损失。

但如果你一次只使用几个——比如，在字典中查找东西——trie可以为你节省很多空间。绝对比存储在HashSet中的空间要小。

你说你是“连续地”访问它们——如果这意味着按字母顺序访问，如果你深度优先迭代，trie显然也会免费给你字母顺序。

小开

这取决于实现。基元类型数组可能比ArrayList更小更高效。这是因为数组将直接将值存储在一个连续的内存块中，而最简单的ArrayList实现将存储指向每个值的指针。特别是在64位平台上，这可能会产生巨大的差异。

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

小开

这取决于你如何访问它。

存储后，如果你主要想做搜索操作，很少或不需要插入/删除，那么就去数组(因为在数组中搜索是在O(1)中完成的，而添加/删除可能需要重新排序元素)。

存储之后，如果你的主要目的是添加/删除字符串，很少或没有搜索操作，那么就去List。

小开

我同意在大多数情况下，您应该选择数组列表的灵活性和优雅性，而不是数组——在大多数情况下，它对程序性能的影响可以忽略不计。

然而，如果你对软件图形渲染或自定义虚拟机进行持续的、很少结构变化(没有添加和删除)的繁重迭代，我的顺序访问基准测试显示，在我的系统上数组列表比数组慢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
}
}

小开

如果你可以使用固定的大小，数组将会更快，需要更少的内存。

如果您需要List接口在添加和删除元素方面的灵活性，那么问题仍然是应该选择哪种实现。通常在任何情况下都推荐使用ArrayList，但如果必须删除或插入列表开头或中间的元素，ArrayList也有其性能问题。

因此，你可能想要看看https://dzone.com/articles/gaplist-lightning-fast-list，它引入了GapList。这个新的列表实现结合了ArrayList和LinkedList的优点，使得几乎所有的操作都有很好的性能。在https://github.com/magicwerk/brownies-collections处获取。

小开

虽然建议使用数组列表的答案在大多数情况下是有意义的，但相对性能的实际问题还没有真正得到答案。

你可以用数组做以下几件事:

创建它
设置一个项目
买一件物品
克隆/复制它

一般的结论

尽管get和set操作在数组列表上比较慢(分别地。在我的机器上每次调用1和3纳秒)，对于任何非密集的用途，使用ArrayList相对于数组的开销非常小。然而有几件事要记住:

在列表上调整大小操作(当调用list.add(...)时)代价很高，应该尽可能将初始容量设置为适当的级别(注意，在使用数组时也会出现同样的问题)
在处理原语时，数组可以明显更快，因为它们可以避免许多装箱/拆箱转换
一个只在数组列表中获取/设置值的应用程序(不是很常见!)通过切换到数组可以看到超过25%的性能增益

详细的结果

下面是我在标准x86桌面机器上使用JDK 7使用JMH基准测试库(以纳秒为单位)测量这三个操作的结果。请注意，ArrayList在测试中从不调整大小，以确保结果具有可比性。此处提供基准代码。。

数组/ 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]

结论:无明显差异。

get操作

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

结论:从数组中获取大约快25%比从数组列表中获得的要多，尽管差异只有一纳秒的量级。

集合操作

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

结论:在数组上的集合操作大约快了40%比列表上的要多，但是，对于get，每个set操作需要几纳秒——所以为了达到1秒的差异，需要在列表/数组中设置项数亿次!

克隆/复制

ArrayList的复制构造函数委托给Arrays.copyOf，因此性能与数组复制相同(通过clone、Arrays.copyOf或System.arrayCopy 在性能方面没有实质性的差异复制数组)。

小开

更新:

正如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

对“更快”有更多评论吗?这是可以理解的。问题是什么时候大约3倍的速度比List的灵活性更好。但这是另一个问题。顺便说一下，我也根据手动构造的ArrayList检查了这一点。

小开

List是java 1.5及以上版本的首选方式，因为它可以使用泛型。数组不能有泛型。数组也有预定义的长度，不能动态增长。初始化一个大数组并不是一个好主意。 ArrayList是用泛型声明数组的方式，它可以动态增长。但如果删除和插入使用得更频繁，那么链表是使用得最快的数据结构

小开

数组建议你在任何地方使用它们而不是列表，特别是在你知道项目的数量和大小不会改变的情况下。

参见Oracle Java最佳实践:http://docs.oracle.com/cd/A97688_16/generic.903/bp/java.htm#1007056

当然，如果需要多次从集合中添加和删除对象，则使用简单列表。

小开

这里给出的许多微基准测试发现，像array/ArrayList读取这样的事情需要几纳秒。如果所有内容都在L1缓存中，这是非常合理的。

更高级别的缓存或主存访问的数量级可能是10nS-100nS，而L1缓存的数量级更接近1nS。访问ArrayList有一个额外的内存间接，在实际的应用程序中，你可以几乎从不或每次都支付这个代价，这取决于你的代码在访问之间所做的事情。当然，如果你有很多小的数组列表，这可能会增加你的内存使用，使你更有可能缓存丢失。

原来的海报似乎只使用一个，在短时间内访问了很多内容，所以应该没有太大的困难。但是对于其他人来说可能有所不同，在解释微基准测试时应该注意。

然而，Java字符串是令人震惊的浪费，特别是如果您存储了许多小字符串(用内存分析器查看它们，对于几个字符的字符串来说，它似乎是> 60字节)。字符串数组有一个指向String对象的间接数组，还有一个从String对象指向包含字符串本身的char[]的间接数组。如果有什么东西会破坏你的L1缓存，那就是这个，加上成千上万的字符串。因此，如果你是认真的——非常认真地——想要尽可能地降低性能，那么你可以考虑采用不同的方法。比如说，你可以保存两个数组，一个是char[]，其中包含所有的字符串，一个是char[]，一个是int[]，其中包含开始的偏移量。这将是一个可以做任何事情的PITA，几乎可以肯定您不需要它。如果你这样做了，你就选择了错误的语言。

小开

ArrayList内部使用数组对象添加(或存储)数组对象元素。换句话说，ArrayList由Array数据支持结构。
.数组列表的数组是可调整大小的(或动态的)

数组比数组列表快因为ArrayList内部使用数组。如果我们可以直接在数组中添加元素，而间接地在数组中添加元素数组通过数组列表的直接机制总是比间接机制快

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

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

数组列表的大小如何动态增长?

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快的原因。

小开

没有一个答案有我感兴趣的信息——重复扫描同一个数组很多很多次。必须为此做一个JMH测试。

结果 (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

测试

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


}

小开

数组-当我们必须实现更快的结果获取时，它总是更好的

列表——执行插入和删除的结果，因为它们可以在O(1)中完成，这也提供了方便地添加、获取和删除数据的方法。更容易使用。

但是始终记住，当数据存储在数组中的索引位置是已知的时，数据的抓取将是快速的。

这可以通过对数组排序很好地实现。因此，这增加了获取数据的时间(即;存储数据+排序数据+寻找数据所在的位置)。因此，这增加了从数组中获取数据的额外延迟，即使它们可能擅长更快地获取数据。

因此，这可以用三元数据结构或三元数据结构来解决。如上所述，树数据结构在搜索数据时非常有效，对特定单词的搜索可以在O(1)量级上完成。当时间紧迫时;如果你必须快速搜索和检索数据，你可以使用三种数据结构。

如果你希望你的内存空间消耗更少，你希望有一个更好的性能，那么使用三元数据结构。这两个都适合存储大量的字符串(例如;比如字典里的单词)。

小开

既然这里已经有很多很好的答案，我想给你一些其他的实际观点的信息，这是插入和迭代性能比较: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.");
}
}

表现结果如下:

小开

我来这里是为了更好地感受使用列表而不是数组对性能的影响。我不得不为我的场景调整代码:数组/列表的~1000个整型，主要使用getter，即数组[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倍。一天就能完成的事情现在需要一个星期。

< p > *编辑这里非常震惊，我试图声明int[1000]而不是Integer[1000]

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

使用Integer[] vs. 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);
}

小开

使用哪一种取决于问题本身。我们得看看大O。

图片来源:https://github.com/egonSchiele/grokking_algorithms