java - StringBuffer 和摊销

Question

在ArrayList中，添加操作是摊销操作。因此，在阅读 StringBuffer 时，我想到了为什么 StringBuffer 不进行摊销。假设我对字符串缓冲区对象使用追加操作，那么它应该能够在其底层数组实现中添加那么多字符。但我在源代码中发现我们有

System.arraycopy(chars, 0, value, count, chars.length);

字符串缓冲区的附加操作。所以我的问题是 StringBuffer 不能被摊销，这样它就能给我们带来更少的 O(N) 复杂性吗？

Answer 1

最终，您仍然将 N 个引用从某个内存位置 A 移动到其他内存位置 B。但是，我相信 System.arraycopy 的速度足够快这样就可以从 StringBuffer 获得摊销性能。但是，这取决于您是追加还是插入。

回想一下，ArrayList 可以通过两种方式执行 add:使用单个对象，或者通过将元素从特定索引位置向下移动。两者的性能不同。

为了解决这个问题，(最终)StringBuffer 将调用 System.arraycopy()。此实现实际上依赖于 JVM(它是 native 调用)，但很可能它非常快。除此之外，除了要复制的非常大的非连续内存区域之外，没有太多因素会真正降低 StringBuffer.append() 的性能。

ArrayList.add(E element) 将花费 O(1) 时间，但可能会更改为 O(N)，因为它可能必须增加支持数组以适应更多其中的元素；但是，如果不必这样做，则插入时间约为 O(1)(它将元素添加到数组末尾)。

ArrayList.add(int index, E element) 在最好的情况下可能是 O(1)，但在平均和最坏的情况下是 O(N - index)，因为它必须向下移动才能放置 E 的元素。

总结一下:

• StringBuffer.append() 的代码可以被视为摊销 O(N)，因为它确实复制了数组。但是，此操作仍然很快，并且仅真正取决于您要移动的数据有多大。

• StringBuffer.insert() 的代码不同，在最好的情况下很容易成为摊销 O(1)，而 O(N )在最坏的情况下(因为它对 System.arraycopy() 进行了两次调用)。在给定点插入元素意味着您必须将其他所有内容向下移动，无论您的代码有多快，这都不是一个便宜的操作。

我相信，根据您使用的方法，您确实具有摊销性能。您只需确定正在执行的操作即可知道性能如何。