ArrayList
的常用构造函数是:
ArrayList<?> list = new ArrayList<>();
但是还有一个重载的构造器,它有一个初始容量的参数:
ArrayList<?> list = new ArrayList<>(20);
当我们可以随心所欲地添加ArrayList
时,为什么创建一个具有初始容量的as会很有用?
发布于 2013-03-15 18:41:57
如果事先知道ArrayList
的大小,那么指定初始容量会更有效率。如果不这样做,内部数组将不得不随着列表的增长而重复重新分配。
最终列表越大,通过避免重新分配节省的时间就越多。
也就是说,即使没有预分配,在ArrayList
后面插入n
元素也会占用总的O(n)
时间。换句话说,追加一个元素是一个分期的常量时间操作。这是通过使每次重新分配以指数方式增加数组的大小来实现的,通常是以1.5
的倍数增加。使用这种方法,操作的总数为can be shown to be O(n)
。
发布于 2013-03-15 18:47:03
因为ArrayList
是一个dynamically resizing array数据结构,这意味着它是作为一个具有初始(默认)固定大小的数组实现的。当这个数组被填满时,数组将被扩展为双倍大小的数组。此操作的成本很高,因此您需要尽可能少的操作。
因此,如果您知道上限是20项,那么创建初始长度为20的数组比使用默认值15要好,然后将其大小调整为15*2 = 30
,只使用20,同时浪费扩展周期。
附注-正如AmitG所说,扩展因子是特定于实现的(在本例中为(oldCapacity * 3)/2 + 1
)
发布于 2013-03-15 18:45:51
CPU可以包含很多值,在进行大型初始插入时,您可以告诉ArrayList从一开始就分配更大的存储空间,以免在尝试为下一项分配更多空间时浪费ArrayList周期。因此,在开始时分配一些空间是更有效的。
https://stackoverflow.com/questions/15430247
复制相似问题