ArrayList vs倍增数组大小

因此，当数组不能容纳我们想要的信息量时，一个常见的编程实践是将数组的大小增加一倍。我们通过创建一个新数组来实现这一点，它的大小是原始数组的两倍，用旧的值填充这个新数组，并将其设置为旧数组。下面是Java中的一个示例:

public int[] doubleArray(int[] old) {
int[] doubled = new int[old.length * 2];
for (int i = 0; i < old.length; i++) {
doubled[i] = old[i];
}
return doubled;
}

所以它是更更好使用标准数组和大小加倍，当需要时，或简单地使用ArrayList(它改变自己的大小基于输入你给它1)?基本上，当您需要存储比数组允许的更多的数据时，是将数组的大小加倍，还是每次将其大小增加1 ?哪一种选择比另一种更好的界限是什么?

如果我必须猜测，使用标准数组应该更快，因为它在java.lang中，所以我制作了以下类来测试我的理论:

public class ArrayTesting {
public static void main(String[] args) {
long startTime1 = System.nanoTime();
int[] ints = new int[10];
for (int i = 0; i < ints.length; i++) {
ints[i] = i * 2;
}
long timeToSetOriginalValues = (System.nanoTime() - startTime1);
long startTime2 = System.nanoTime();
ints = doubleArray(ints);
long timeToDouble = (System.nanoTime() - startTime2);
long startTime3 = System.nanoTime();
for (int i = 9; i < ints.length; i++) {
ints[i] = i * 2;
}
long timeToSetNewValues = (System.nanoTime() - startTime3);
System.out.println("Set Values in " + timeToSetOriginalValues);
System.out.println("Doubled Array in " + timeToDouble);
System.out.println("Finished setting values in " + timeToSetNewValues);
System.out.println("Total time: " + (timeToSetOriginalValues + timeToDouble + timeToSetNewValues));
}
public static int[] doubleArray(int[] old) {
int[] doubled = new int[old.length * 2];
for (int i = 0; i < old.length; i++) {
doubled[i] = old[i];
}
return doubled;
}
}

但是由于未知的原因，我得到了非常不同的结果。总时间在11000到4000之间变化。假设是我做错了什么，有没有更会计时的人能回答我的问题?

好的，我调查了一下，结果如下:

我创建了一个新的类来测试编辑数组的时间，以及编辑ArrayList的时间。让我们从ArrayTesting类开始。

public class ArrayTesting {
private static long totalTotal = 0L;
private static int[] ints = new int[10];
public static void main(String[] args) {
for (int i = 0; i < 5; i++) {
runTest();
}
System.out.println("Final Length of Array: " + ints.length);
System.out.println("Total Time was: " + totalTotal);
}
private static void runTest() {
long startTime = System.nanoTime();
for (int i = 0; i < ints.length; i++) {
ints[i] = i * 2;
}
ints = doubleArray(ints);
for (int i = 9; i < ints.length; i++) {
ints[i] = i * 2;
}
long testTime = System.nanoTime() - startTime;
totalTotal = totalTotal + testTime;
}
private static int[] doubleArray(int[] old) {
int[] doubled = new int[old.length * 2];
for (int i = 0; i < old.length; i++) {
doubled[i] = old[i];
}
return doubled;
}
}

这个类的过程如下:

创建新的整数对象数组(是的，这很重要)，长度为10.
对于5次迭代，将当前数组的所有索引设置为index * 2，然后将数组的大小增加一倍，并用各自的index * 2值填充新的索引。
打印结果

按照同样的过程，然后为ArrayList创建一个测试类:

import java.util.ArrayList;
class ArrayListTester {
public static ArrayList<Integer> arl = new ArrayList<Integer>();
public static long totalTotal = 0L;
public static void main(String[] args) {
//Set initial size for ArrayList to 10
while(arl.size() < 10) arl.add(0);
//Setting the size was not timed.
for (int i = 0; i < 5; i++) {
runTest();
}
System.out.println("Total ArrayList size: " + arl.size());
System.out.println("Total Time: " + totalTotal);
}
public static void runTest() {
long startTime1 = System.nanoTime();
int initialSize = arl.size();
for (int i = 0; i < initialSize * 2; i++) {
if (i < initialSize)
arl.set(i, ((Integer) i * 2));
else
arl.add((Integer) i * 2);
}
long totalForRun = System.nanoTime() - startTime1;
totalTotal = totalTotal + totalForRun;
}
}

如果你通读这个类，你会发现它确实遵循了相同的步骤，但是使用ArrayList可以使代码更加一致。

那么现在让我们来看看我们的结果…

由于每个类在5次迭代中运行大小加倍的事情，因此最后两个数组的大小都是320或10 * (2 ^ 5)(注意两个数组的起始大小都是10)。然而，在快速运行几次测试之后，时间消耗就有了很大的不同。

现在，连续运行ArrayTester类5次，并取每次运行的平均时间(将其相加并除以运行次数)，我得到的平均时间为468,290纳秒，你们中的一些人可能认为这对于简单地将数组加倍来说是一个相当不错的块，但只是等待…

接下来，移动到ArrayListTester类并运行相同的5次以获得平均值，我得到的平均值正好是2,069,230纳秒。

如果你想自己测试一下这些数字，我在一个在线编译器/解释器上运行了这些程序。

最终结果:而ArrayList完成同样的任务所需的时间几乎是前者的4.5倍。

现在回到最初的问题:那么是不是更好是使用标准数组并在需要时将其大小加倍，还是简单地使用ArrayList?"

这个问题的答案取决于你希望你的代码有多高效。对于ArrayList来说，效率实际上已经不存在了，但是代码的美观性和组织性却得到了极大的提高。另一方面，如果您正在寻找一种更有效的处理事物的方法，并且不太关心需要编写的代码，那么使用Array。

如果你看一下ArrayList的实现，即使它有Array对象，当你调用add方法时，它也会确保容量，如果需要，增加数组的大小，就像

elementData = Arrays.copyOf(elementData, newCapacity);

其中elementData为存储数据的内部数组。

关于性能或内存消耗，由于它是一个具有许多功能的包装器，显然与Array对象相比会有一些成本。

一个简单的Array总是会更快，因为ArrayList是一个Array，当它没有空间时创建一个新的Array，当它太大时收缩它。

public boolean add(E e) {
ensureCapacityInternal(size + 1);  // Increments modCount!!
elementData[size++] = e;
return true;
}

代码取自OpenJDK7，在这里您可以清楚地看到，简单的add方法会有很小的开销，它检查array的大小是太小还是太大，将array复制到具有更大大小的数组中，然后设置元素。一个正常的Array只需要。

Arr[index] = value;

但是ArrayLists增加的功能和代码质量的改进，将在大多数非性能优化的场景中远远优于传统的Array。

作为研究，您可以在http://algs4.cs.princeton.edu/home/上找到非常好的实现Arrays大小调整的示例，其中有一个调整Array大小的示例http://algs4.cs.princeton.edu/13stacks/ResizingArrayStack.java.html。

相关内容

最新更新

热门标签：