通常的构造函数ArrayList
是:
ArrayList<?> list = new ArrayList<>();
但也有一个重载的构造函数与它的初始容量参数:
ArrayList<?> list = new ArrayList<>(20);
为什么是有用的创建一个ArrayList
有,当我们可以追加到它,因为我们请的初始容量?
通常的构造函数ArrayList
是:
ArrayList<?> list = new ArrayList<>();
但也有一个重载的构造函数与它的初始容量参数:
ArrayList<?> list = new ArrayList<>(20);
为什么是有用的创建一个ArrayList
有,当我们可以追加到它,因为我们请的初始容量?
如果事先知道是什么的大小ArrayList
将是,它是更有效的指定初始容量。 如果你不这样做,内部阵列将作为列表的增长被反复重新分配。
在最终名单越大,时间越长,你通过避免重新分配存储。
这就是说,即使不预分配,插入n
在背面元件ArrayList
是保证采取总O(n)
时间。 换句话说,附加一个元件是分期常量时间的操作。 这是通过使每个再分配增加数组的大小按指数,典型地通过一个因子来实现1.5
。 通过这种方法,操作的总数目可以被示出为O(n)
因为ArrayList
是一个动态调整阵列的数据结构,这意味着它是与初始(默认)固定大小的阵列来实现。 当该被填满,该数组将被扩展到两倍大小的一个。 这种操作是昂贵的,所以你要尽可能少。
所以,如果你知道你的上限是20个项目,然后创建与20的初始长度数组比使用的,比方说,15默认,然后将其调整到更好的15*2 = 30
,虽然浪费周期只用20为扩展。
PS -作为AmitG说,膨胀因子是特定于实现(在这种情况下(oldCapacity * 3)/2 + 1
)
的ArrayList默认大小为10。
/**
* Constructs an empty list with an initial capacity of ten.
*/
public ArrayList() {
this(10);
}
所以,如果你要添加100分或更多的记录,你可以看到内存重新分配的开销。
ArrayList<?> list = new ArrayList<>();
// same as new ArrayList<>(10);
所以,如果你有关于将被存储在ArrayList中它能够更好地创造与大小,而不是与10开始,然后去上增加它的ArrayList元素数量的任何想法。
其实,我写了一篇博客文章的话题2个月前。 这篇文章是针对C#的List<T>
但Java的ArrayList
有一个非常类似的实现。 由于ArrayList
使用动态阵列实现,它增加了在按需大小。 所以对于容量的构造函数的原因是为了优化的目的。
当这些resizings之一操作时,该ArrayList复制数组的内容到一个新的数组,它是旧的容量的两倍。 此操作在O(n)的时间运行。
下面是如何的一个例子ArrayList
会增加大小:
10
16
25
38
58
... 17 resizes ...
198578
297868
446803
670205
1005308
所以列表容量为启动10
,当第11项中添加它是由增加50% + 1
到16
。 在17个项目中ArrayList
再增加到25
等。 现在考虑的例子我们创建其中所需的容量已经被称为列表1000000
。 创建ArrayList
而不尺寸构造函数会调用ArrayList.add
1000000
倍这需要O(1)正常或为O(n)在调整大小。
百万+ 16 + 25 + ... + 670205 + 1005308 = 4015851个操作
此使用构造,然后调用比较ArrayList.add
这是保证在O(1)运行。
百万+百万= 2000000个操作
Java是如上述,起始于10
和增加每个调整在50% + 1
。 C#开始于4
,并增加更多的积极,在每个倍增调整大小。 的1000000
从上方增加了例如用于C#使用3097084
的操作。
设置一个ArrayList的初始大小,例如,以ArrayList<>(100)
减少的次内部存储器的重新分配必须发生的数目。
例:
ArrayList example = new ArrayList<Integer>(3);
example.add(1); // size() == 1
example.add(2); // size() == 2,
example.add(2); // size() == 3, example has been 'filled'
example.add(3); // size() == 4, example has been 'expanded' so that the fourth element can be added.
正如你在上面的例子中看到-一个ArrayList
,如果需要的是可以扩大。 什么这不告诉你的是,ArrayList中的大小通常一倍(但请注意新的大小取决于具体的实现)。 下面是引自甲骨文 :
“每个ArrayList实例都有一个容量。容量是用于存储在列表中的元件的阵列的大小。它总是至少与列表大小一样大。作为元素被添加到一个ArrayList,其容量自动增长。增长政策的细节无法超越的事实,添加元素具有恒定的摊余成本时指定“。
很显然,如果你不知道以什么样的范围内,你会拿着,设置大小可能不会是一个好主意 - 但是,如果你心里有一个特定的范围,设置初始容量将提高内存效率。
ArrayList中可以包含很多的价值观和做大量的初始插入时,你可以告诉ArrayList的分配更大的存储开始与当它试图为下一个项目分配更多的空间不浪费CPU周期。 因此,在一开始是比较effiecient分配一些空间。
这是为了避免重新分配可能的努力,为每一个对象。
int newCapacity = (oldCapacity * 3)/2 + 1;
内部new Object[]
被创建。
JVM需要努力创建new Object[]
当你在ArrayList中添加元素。 如果没有上面的代码(任何算法中你认为)的重新分配,然后每次当你调用时间arraylist.add()
然后new Object[]
必须创建这是没有意义的,我们正在失去的时间由1增加大小要被添加的每一个对象。 因此,最好是增加的大小Object[]
用下面的公式。
(JSL已经用于动态生长数组列表,而不是通过每次1生长下面给出测报式,因为生长需要花费功夫由JVM)
int newCapacity = (oldCapacity * 3)/2 + 1;
我想每一个ArrayList中与“10”的初始化容量值创建。 所以无论如何,如果你没有构造函数中设置容量创建一个ArrayList将用默认值创建。
我想说的优化。 没有初始容量的ArrayList将有10〜空行,当你正在做的一个附加将扩大。
为了有一个清单,你需要调用的项目数完全trimToSize()
按我有经验ArrayList
,给人的初始容量为避免重新分配成本的好方法。 但是,它担负着警告。 上面提到的所有的建议说应该提供仅当元件的数量的粗略估计,已知的初始容量。 但是,当我们试图给出一个初始容量没有任何想法,内存量保留的和未使用的将是一种浪费,因为它可能永远不会被要求一旦名单被填充到所需数目的元素。 我想说的是,我们可以在一开始务实,同时,分配容量,然后找到在运行时知道所需的最小容量的一个聪明的办法。 ArrayList中提供了一个名为方法ensureCapacity(int minCapacity)
但后来,一个有找到一个巧妙的方法...
我测试的ArrayList使用和不使用参数:initialCapacity和我suprising结果
当我设置LOOP_NUMBER 10万以下的结果是,设置参数:initialCapacity是有效的。
list1Sttop-list1Start = 14
list2Sttop-list2Start = 10
但是,当我设置LOOP_NUMBER至1000000结果的变化:
list1Stop-list1Start = 40
list2Stop-list2Start = 66
最后,我无法弄清楚它是如何工作的?
示例代码:
public static final int LOOP_NUMBER = 100000;
public static void main(String[] args) {
long list1Start = System.currentTimeMillis();
List<Integer> list1 = new ArrayList();
for (int i = 0; i < LOOP_NUMBER; i++) {
list1.add(i);
}
long list1Stop = System.currentTimeMillis();
System.out.println("list1Stop-list1Start = " + String.valueOf(list1Stop - list1Start));
long list2Start = System.currentTimeMillis();
List<Integer> list2 = new ArrayList(LOOP_NUMBER);
for (int i = 0; i < LOOP_NUMBER; i++) {
list2.add(i);
}
long list2Stop = System.currentTimeMillis();
System.out.println("list2Stop-list2Start = " + String.valueOf(list2Stop - list2Start));
}
我已经在windows8.1和jdk1.7.0_80测试