Java:ArrayList add() 和 remove() 性能、实现? [英] Java: ArrayList add() and remove() performance, implementation?
问题描述
我在某处读到 ArrayList 的 add() 和 remove() 操作在摊销常量"时间内运行.这究竟是什么意思?
I have read somewhere that ArrayList's add() and remove() operations run in "amortized constant" time. What does this mean exactly?
在add(item)的实现中可以看到ArrayList使用了一个数组缓冲区，最多是list't大小的3/2，如果满了，System.arraycopy() 被调用，它应该在 O(n) 内执行，而不是 O(1) 时间.那么 System.arraycopy 是否会尝试做一些比将元素一个一个地复制到新创建的数组中更聪明的事情，因为时间实际上是 O(1)?
In the implementation of add(item) I can see that it ArrayList uses an array buffer, which is at most 3/2 of the list't size, and if it is full, System.arraycopy() is called, which should execute in O(n), not O(1) time. Is it then that System.arraycopy attempts to do something smarter than copying elements one by one into newly created array, since the time is actually O(1)?
结论:add(item) 以摊销的常数时间运行，但 add(item, index) 和 remove(index) 不't，它们以线性时间运行(如答案中所述).
Conclusion: add(item) runs in amortized constant time, but add(item, index) and remove(index) don't, they run in linear time (as explained in answers).
推荐答案
我在某处读到 ArrayList 的 add() 和 remove() 操作在摊销常量"时间内运行.
I have read somewhere that ArrayList's add() and remove() operations run in "amortized constant" time.
我认为 remove() 不是这样，除非是在不寻常的情况下.
I don't think that is true for remove() except under unusual conditions.
对随机元素的
remove(Object)调用平均必须对列表中的一半条目调用equals，然后复制引用另一半.
A
remove(Object)call for a random element on average has to callequalson half of entries in the list, and then copy the references for the other half.
对随机元素的 remove(int) 调用平均必须复制一半元素的引用.
A remove(int) call for a random element on average has to copy the references for half of the elements.
remove(...) 平均为 O(1) 的唯一情况(例如摊销)是当您使用 remove(int) 从列表的末尾删除一些常量偏移量的元素.
The only cases where remove(...) is going to be O(1) on average (e.g. amortized) is when you are using remove(int) to remove elements some constant offset from the end of the list.
这篇关于Java:ArrayList add() 和 remove() 性能、实现?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
