blocks|key|357351|text|如果事先知道ArrayList的大小，那么指定初始容量会更有效率。如果不这样做，内部数组将不得不随着列表的增长而重复重新分配。|type|unstyled|depth|inlineStyleRanges|offset|length|style|CODE|entityRanges|data|357352|最终列表越大，通过避免重新分配节省的时间就越多。|357353|也就是说，即使没有预分配，在ArrayList后面插入n元素也会占用总的O(n)时间。换句话说，追加一个元素是一个分期的常量时间操作。这是通过使每次重新分配以指数方式增加数组的大小来实现的，通常是以1.5的倍数增加。使用这种方法，操作的总数为can+be+shown+to+be+O(n)。|357354|entityMap|0|LINK|mutability|MUTABLE|url|http://www.wolframalpha.com/input/?i=sum%25281.5%252a%252ak%2529%2520for%2520k=1,log%25281.5,n%2529^0|6|9|0|0|E|9|R|1|10|4|2R|3|3W|4|3D|N|0|0^^$0|@$1|2|3|4|5|6|7|R|8|@$9|S|A|T|B|C]]|D|@]|E|$]]|$1|F|3|G|5|6|7|U|8|@]|D|@]|E|$]]|$1|H|3|I|5|6|7|V|8|@$9|W|A|X|B|C]|$9|Y|A|Z|B|C]|$9|10|A|11|B|C]|$9|12|A|13|B|C]|$9|14|A|15|B|C]]|D|@$9|16|A|17|1|18]]|E|$]]|$1|J|3|-4|5|6|7|19|8|@]|D|@]|E|$]]]|K|$L|$5|M|N|O|E|$P|Q]]]]

If you know in advance what the size of the <code>ArrayList</code> is going to be, it is more efficient to specify the initial capacity. If you don't do this, the internal array will have to be repeatedly reallocated as the list grows.

The larger the final list, the more time you save by avoiding the reallocations.

That said, even without pre-allocation, inserting <code>n</code> elements at the back of an <code>ArrayList</code> is guaranteed to take total <code>O(n)</code> time. In other words, appending an element is an amortized constant-time operation. This is achieved by having each reallocation increase the size of the array exponentially, typically by a factor of <code>1.5</code>. With this approach, the total number of operations <a href="http://www.wolframalpha.com/input/?i=sum%281.5%2a%2ak%29%20for%20k=1,log%281.5,n%29">can be shown to be <code>O(n)</code></a>.

blocks|key|139433|text|我认为每个ArrayList都是使用初始容量值"10“创建的。所以不管怎样，如果你创建了一个没有在构造函数中设置容量的ArrayList，它将被创建为一个缺省值。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|139434|entityMap^0|0^^$0|@$1|2|3|4|5|6|7|D|8|@]|9|@]|A|$]]|$1|B|3|-4|5|6|7|E|8|@]|9|@]|A|$]]]|C|$]]

I think each ArrayList is created with an init capacity value of "10". So anyway, if you create an ArrayList without setting capacity within constructor it will be created with a default value.

blocks|key|357421|text|CPU可以包含很多值，在进行大型初始插入时，您可以告诉ArrayList从一开始就分配更大的存储空间，以免在尝试为下一项分配更多空间时浪费ArrayList周期。因此，在开始时分配一些空间是更有效的。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|357422|entityMap^0|0^^$0|@$1|2|3|4|5|6|7|D|8|@]|9|@]|A|$]]|$1|B|3|-4|5|6|7|E|8|@]|9|@]|A|$]]]|C|$]]

ArrayList can contain many values and when doing large initial insertions you can tell ArrayList to allocate a larger storage to begin with as to not waste CPU cycles when it tries to allocate more space for the next item. Thus to allocate some space at the beginning is more effiecient.

blocks|key|139479|text|我会说这是一个优化。没有初始容量的ArrayList将有大约10个空行，并将在您进行添加时扩展。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|139480|要获得一个列表，其中包含您需要调用trimToSize()的项目的确切数量|offset|length|139481|entityMap|0|LINK|mutability|MUTABLE|url|http://docs.oracle.com/javase/1.5.0/docs/api/java/util/ArrayList.html#trimToSize%2528%2529^0|0|H|C|0|0^^$0|@$1|2|3|4|5|6|7|N|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|O|8|@]|9|@$D|P|E|Q|1|R]]|A|$]]|$1|F|3|-4|5|6|7|S|8|@]|9|@]|A|$]]]|G|$H|$5|I|J|K|A|$L|M]]]]

I'd say its an optimization. ArrayList without initial capacity will have ~10 empty rows and will expand when you are doing an add.

To have a list with exactly the number of items you need to call <a href="http://docs.oracle.com/javase/1.5.0/docs/api/java/util/ArrayList.html#trimToSize%28%29" rel="nofollow">trimToSize()</a>

blocks|key|357506|text|因为ArrayList是一个dynamically+resizing+array数据结构，这意味着它是作为一个具有初始(默认)固定大小的数组实现的。当这个数组被填满时，数组将被扩展为双倍大小的数组。此操作的成本很高，因此您需要尽可能少的操作。|type|unstyled|depth|inlineStyleRanges|offset|length|style|CODE|entityRanges|data|357507|因此，如果您知道上限是20项，那么创建初始长度为20的数组比使用默认值15要好，然后将其大小调整为15*2+=+30，只使用20，同时浪费扩展周期。|357508|附注-正如AmitG所说，扩展因子是特定于实现的(在本例中为(oldCapacity+*+3)/2+%2B+1)|357509|entityMap|0|LINK|mutability|MUTABLE|url|http://en.wikipedia.org/wiki/Dynamic_array^0|2|9|E|Q|0|0|1D|9|0|U|N|0^^$0|@$1|2|3|4|5|6|7|R|8|@$9|S|A|T|B|C]]|D|@$9|U|A|V|1|W]]|E|$]]|$1|F|3|G|5|6|7|X|8|@$9|Y|A|Z|B|C]]|D|@]|E|$]]|$1|H|3|I|5|6|7|10|8|@$9|11|A|12|B|C]]|D|@]|E|$]]|$1|J|3|-4|5|6|7|13|8|@]|D|@]|E|$]]]|K|$L|$5|M|N|O|E|$P|Q]]]]

Because <code>ArrayList</code> is a <a href="http://en.wikipedia.org/wiki/Dynamic_array" rel="nofollow noreferrer">dynamically resizing array</a> data structure, which means it is implemented as an array with an initial (default) fixed size. When this gets filled up, the array will be extended to a double sized one. This operation is costly, so you want as few as possible.

So, if you know your upper bound is 20 items, then creating the array with initial length of 20 is better than using a default of, say, 15 and then resize it to <code>15*2 = 30</code> and use only 20 while wasting the cycles for the expansion.

P.S. - As AmitG says, the expansion factor is implementation specific (in this case <code>(oldCapacity * 3)/2 + 1</code>)

blocks|key|139545|text|这是为了避免为每个单独的对象重新分配可能的工作。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|139546|int+newCapacity+=+(oldCapacity+*+3)/2+%2B+1;|code-block|syntax|javascript|139547|在内部创建new+Object[]。|offset|length|style|CODE|139548|当您在arraylist中添加元素时，JVM需要努力创建new+Object[]。如果你没有上面的代码(任何你认为的算法)来重新分配，那么每次当你调用arraylist.add()时，就必须创建new+Object[]，这是没有意义的，我们正在浪费时间为每个要添加的对象增加1的大小。所以最好用下面的公式来增加Object[]的大小。|139549|(JSL使用了下面给出的预测公式来动态增长arraylist，而不是每次都增长1。因为它的增长需要JVM的努力)|139550|int+newCapacity+=+(oldCapacity+*+3)/2+%2B+1;|139551|entityMap^0|0|0|5|C|0|S|C|23|F|2P|C|4B|8|0|0|0^^$0|@$1|2|3|4|5|6|7|U|8|@]|9|@]|A|$]]|$1|B|3|C|5|D|7|V|8|@]|9|@]|A|$E|F]]|$1|G|3|H|5|6|7|W|8|@$I|X|J|Y|K|L]]|9|@]|A|$]]|$1|M|3|N|5|6|7|Z|8|@$I|10|J|11|K|L]|$I|12|J|13|K|L]|$I|14|J|15|K|L]|$I|16|J|17|K|L]]|9|@]|A|$]]|$1|O|3|P|5|6|7|18|8|@]|9|@]|A|$]]|$1|Q|3|R|5|D|7|19|8|@]|9|@]|A|$E|F]]|$1|S|3|-4|5|6|7|1A|8|@]|9|@]|A|$]]]|T|$]]

This is to avoid possible efforts for reallocation for every single object. 

<pre><code>int newCapacity = (oldCapacity * 3)/2 + 1;
</code></pre>

internally <code>new Object[]</code> is created. JVM needs effort to create <code>new Object[]</code> when you add element in the arraylist. If you don't have above code(any algo you think) for reallocation then every time when you invoke <code>arraylist.add()</code> then <code>new Object[]</code> has to be created which is pointless and we are loosing time for increasing size by 1 for each and every objects to be added. So it is better to increase size of <code>Object[]</code> with following formula. 
(JSL has used forcasting formula given below for dynamically growing arraylist instead of growing by 1 every time. Because to grow it takes effort by JVM)

<pre><code>int newCapacity = (oldCapacity * 3)/2 + 1;
</code></pre>

blocks|key|139570|text|根据我使用ArrayList的经验，给出初始容量是避免重新分配成本的好方法。但它有一个警告。上面提到的所有建议都表明，只有在粗略估计元素的数量时，才应该提供初始容量。但是，当我们在没有任何概念的情况下尝试给出初始容量时，保留和未使用的内存量将是一种浪费，因为一旦列表填满所需的元素数量，就可能永远不会需要这些内存。我想说的是，我们可以在一开始分配容量时采取务实的态度，然后找到一种聪明的方法来了解运行时所需的最小容量。ArrayList提供了一个名为ensureCapacity(int+minCapacity)的方法。但是，人们必须找到一种聪明的方法。|type|unstyled|depth|inlineStyleRanges|offset|length|style|CODE|entityRanges|data|139571|entityMap^0|5|9|69|V|0^^$0|@$1|2|3|4|5|6|7|H|8|@$9|I|A|J|B|C]|$9|K|A|L|B|C]]|D|@]|E|$]]|$1|F|3|-4|5|6|7|M|8|@]|D|@]|E|$]]]|G|$]]

As per my experience with <code>ArrayList</code>, giving an initial capacity is a nice way to avoid reallocation costs. But it bears a caveat. All suggestions mentioned above say that one should provide initial capacity only when a rough estimate of the number of elements is known. But when we try to give an initial capacity without any idea, the amount of memory reserved and unused will be a waste as it may never be required once the list is filled to required number of elements. What i am saying is, we can be pragmatic at the beginning while allocating capacity, and then find a smart way of knowing required minimal capacity at runtime. ArrayList provides a method called <code>ensureCapacity(int minCapacity)</code>. But then, one has find a smart way...

blocks|key|357631|text|我测试了使用和不使用initialCapacity的ArrayList，得到了令人惊讶的结果|type|unstyled|depth|inlineStyleRanges|entityRanges|data|357632|当我将LOOP_NUMBER设置为100,000或更小时，结果是设置initialCapacity是有效的。|357633|list1Sttop-list1Start+=+14
list2Sttop-list2Start+=+10|code-block|syntax|javascript|357634|但是当我将LOOP_NUMBER设置为1,000,000时，结果更改为：|357635|list1Stop-list1Start+=+40
list2Stop-list2Start+=+66|357636|最后，我不知道它是怎么工作的？！|357637|示例代码：|357638|+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%2B%2B)+{
++++++++list1.add(i);
++++}
++++long+list1Stop+=+System.currentTimeMillis();
++++System.out.println("list1Stop-list1Start+=+"+%2B+String.valueOf(list1Stop+-+list1Start));

++++long+list2Start+=+System.currentTimeMillis();
++++List<Integer>+list2+=+new+ArrayList(LOOP_NUMBER);
++++for+(int+i+=+0;+i+<+LOOP_NUMBER;+i%2B%2B)+{
++++++++list2.add(i);
++++}
++++long+list2Stop+=+System.currentTimeMillis();
++++System.out.println("list2Stop-list2Start+=+"+%2B+String.valueOf(list2Stop+-+list2Start));
}|357639|我已经在windows8.1和jdk1.7.0_80上测试过了|357640|entityMap^0|0|0|0|0|0|0|0|0|0^^$0|@$1|2|3|4|5|6|7|W|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|X|8|@]|9|@]|A|$]]|$1|D|3|E|5|F|7|Y|8|@]|9|@]|A|$G|H]]|$1|I|3|J|5|6|7|Z|8|@]|9|@]|A|$]]|$1|K|3|L|5|F|7|10|8|@]|9|@]|A|$G|H]]|$1|M|3|N|5|6|7|11|8|@]|9|@]|A|$]]|$1|O|3|P|5|6|7|12|8|@]|9|@]|A|$]]|$1|Q|3|R|5|F|7|13|8|@]|9|@]|A|$G|H]]|$1|S|3|T|5|6|7|14|8|@]|9|@]|A|$]]|$1|U|3|-4|5|6|7|15|8|@]|9|@]|A|$]]]|V|$]]

I have tested ArrayList with and without initialCapacity and I got suprising result 
 
When I set LOOP_NUMBER to 100,000 or less the result is that setting initialCapacity is efficient.
 

<pre><code>list1Sttop-list1Start = 14
list2Sttop-list2Start = 10
</code></pre>

 
But when I set LOOP_NUMBER to 1,000,000 the result changes to:
 

<pre><code>list1Stop-list1Start = 40
list2Stop-list2Start = 66
</code></pre>

 
Finally, I couldn't figure out how does it works?!
 
Sample code:

<pre><code> public static final int LOOP_NUMBER = 100000;

public static void main(String[] args) {

 long list1Start = System.currentTimeMillis();
 List&lt;Integer&gt; list1 = new ArrayList();
 for (int i = 0; i &lt; LOOP_NUMBER; i++) {
 list1.add(i);
 }
 long list1Stop = System.currentTimeMillis();
 System.out.println("list1Stop-list1Start = " + String.valueOf(list1Stop - list1Start));

 long list2Start = System.currentTimeMillis();
 List&lt;Integer&gt; list2 = new ArrayList(LOOP_NUMBER);
 for (int i = 0; i &lt; LOOP_NUMBER; i++) {
 list2.add(i);
 }
 long list2Stop = System.currentTimeMillis();
 System.out.println("list2Stop-list2Start = " + String.valueOf(list2Stop - list2Start));
}
</code></pre>

I have tested on windows8.1 and jdk1.7.0_80

The usual constructor of <code>ArrayList</code> is:

<pre><code>ArrayList&lt;?&gt; list = new ArrayList&lt;&gt;();
</code></pre>

But there is also an overloaded constructor with a parameter for its initial capacity:

<pre><code>ArrayList&lt;?&gt; list = new ArrayList&lt;&gt;(20);
</code></pre>

Why is it useful to create an <code>ArrayList</code> with an initial capacity when we can append to it as we please?

Why start an ArrayList with an initial capacity?

数据结构

ArrayList的常用构造函数是：ArrayList<?> list = new ArrayList<>();但是还有一个重载的构造器，它有一个初始容量的参数：ArrayList<?> list = new ArrayList<>(20);当我们可以随心所欲地添加ArrayList时，为什么创建一个具有初始容量的as...

问为什么要启动具有初始容量的ArrayList？
EN

社区

活动

资源

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问为什么要启动具有初始容量的ArrayList？EN

社区

活动

资源

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问为什么要启动具有初始容量的ArrayList？
EN